Finding Perfect Matching Cuts Faster⋆

Neeldhara Misra[0000−0003−1727−5388] and Yash More

Indian Institute of Technology, Gandhinagar {neeldhara.m,yash.mh}@iitgn.ac.in

Abstract. A cut (X, Y) is a perfect matching cut if and only if each

vertex in X has exactly one neighbor in Y and each vertex in Y has
exactly one neighbor in X. The computational problem of determining
if a graph admits a perfect matching cut is NP-complete, even when
restricted to the class of bipartite graphs of maximum degree 3 and arbi-
trarily large girth. Assuming ETH, the problem does not admit an algo-
rithm subexponential in n. On the other hand, the problem is known to
be polynomial-time solvable when restricted to interval graphs, permu-
tation graphs, and some other special classes of graphs. It is also known
to be FPT parameterized by treewidth or cliquewidth and in XP when
parameterized by mim-width (maximum induced matching-width) of a
given decomposition of the graph.
The ETH-hardness of the problem has motivated the study of exact
algorithms for PMC, and the best-known running time has complex-
ity1 O∗ (1.2721n ) [Le and Telle, WG 2021]. In this contribution, we de-
sign a mildly improved branching algorithm using an arguably simpler
approach, whose running time is O∗ (1.2599n ). This addresses an open
problem posed by Le and Telle. We also demonstrate an O∗ (1.1938n )
algorithm for graphs of maximum degree 3 that have girth at least six.

Keywords: Perfect Matching Cut · Branch and Bound

1 Introduction

The Perfect Matching Cut problem was introduced by Heggernes and Telle
(1998) in the context of their study of generalized domination problems. Gen-
eralized dominating sets are parameterized by two sets of nonnegative integers
σ and ρ as follows. A set S of vertices of a graph is said to be a (σ, ρ)-set if
∀v ∈ S, |N(v) ∩ S| ∈ σ and Vu ∈ / S, | N(v) ∩ S |∈ ρ. The (k, σ, ρ)-partition problem
asks for the existence of a partition V1 , V2 , . . . , Vh of vertices of a given graph
G such that Vi , i = 1, 2, . . . , k is a (σ, ρ)-set of G. One of the special cases of
this problem that the authors demonstrated to be NP-complete was when k = 2,
σ = N and ρ = 1. Note that this asks if the graph can be partitioned into two
parts, say X and Y, so that every vertex in X has exactly one neighbor in Y and
every vertex in Y has exactly one neighbor in X. This is indeed the definition of
a perfect matching cut.
⋆
Supported by IIT Gandhinagar and the SERB ECR grant MTR/2017/001033.
1
We use the O∗ notation which suppresses polynomial factors.
2 Misra and More

This formulation of the perfect matching cut makes it a specific instance of

what is called a (σ, ρ) 2-partitioning problem (Telle and Proskurowski, 1997),
where the problem is also phrased the following equivalent labelling task: label
the vertices with two labels such that each vertex has exactly one neighbor
labelled differently from itself. Recent developments by Édouard Bonnet et al.
(2023) show that the problem is NP-complete even on 3-connected cubic bipartite
planar graphs.

We note that the Perfect Matching Cut problem can be thought of as a more
demanding variation of the Matching Cut problem (Chvátal, 1984), which asks
if the graph can be partitioned into two parts, say X and Y as before, so that every
vertex in X has at most one neighbor in Y and every vertex in Y has at most one
neighbor in X. This way the edges in the cut induced by (X, Y) form a matching,
but not necessarily one that is perfect. Neither a matching cut nor a perfect
matching cut is guaranteed to exist. The computational question is to determine
if they do. One could also ask for a matching cut that cuts at least k edges, with
the perfect matching cut question being the special case when k = n/2. For a
representative sample of recent developments on the algorithmic aspects of the
Matching Cut problem, we refer the reader to the works of Komusiewicz et al.
(2018); Golovach et al. (2021); Chen et al. (2021).

From results of Bui-Xuan et al. and Telle and Proskurowski, it turns out that
the Perfect Matching Cut problem is FPT in the treewidth or cliquewidth
of the input graph and XP in the maximum induced matching-width (mim-
width) of a given decomposition of the graph. In a more recent development, Le
and Telle (2022) show that the problem can be solved in polynomial time on two
other graph classes as well: the first one includes claw-free graphs and graphs
without an induced path on five vertices, while the second one properly contains
all chordal graphs. Finally, Feghali et al. (2023) obtain a complete complexity
classification of Perfect Matching Cut for H-subgraph-free graphs where H
is any finite set of graphs.

In contrast with Matching Cut, which is known to be polynomial-time solv-

able when restricted to graphs of maximum degree 3, Le and Telle show that
Perfect Matching Cut is NP-complete in the class of bipartite graphs of
maximum degree 3 and arbitrarily large girth. They also show that the problem
O ∗ o(n)


cannot be solved in 2 time for n-vertex bipartite graphs and cannot
 √ 
be solved in O∗ 2o( n) time for bipartite graphs with maximum degree 3 and
arbitrarily large girth, assuming the Exponential Time Hypothesis. Finally, they
demonstrate the first exact algorithm to solve Perfect Matching Cut on
n-vertex graphs, with a runtime of O∗ (1.2721n ) using a branch-and-bound tech-
nique. In this work, we continue this line work and propose two algorithms with
faster running times for Perfect Matching Cut — one of them works on
general graphs while the other takes advantage of the structure of graphs with
maximum degree 3 and girth at least six.
 Finding Perfect Matching Cuts Faster 3

Specifically, we show that Perfect Matching Cut can be solved in O∗ (1.2599n )

time on n-vertex graphs and in O∗ (1.1938n ) time on n-vertex graphs with max-
imum degree 3 and girth at least six. Our overall approach in both cases follows
the framework introduced by Le and Telle. Given a graph G, we will maintain
and develop a partial matching cut (A, B), where A and B are disjoint subsets
of V(G) with the property that every vertex in A has at most one neighbor in
B and every vertex in B has at most one neighbor in A. We say that a perfect
matching cut (X, Y) extends a partial matching cut (A, B) if A ⊆ X and B ⊆ Y.
We make progress by committing more and more vertices in V(G) \ (A ∪ B) to
either A or B in a manner that is either forced2 or by exhaustive exploration3 . We
do this until we either have evidence that there is no perfect matching cut that
extends the current partial matching cut4 or until we fully develop (A, B) into a
partition of V(G). We report Yes if any of the fully developed partitions induce
a perfect matching cut, and No otherwise. The correctness of this approach
follows from the exhaustiveness of the choices we make for branching.
Both algorithms have the following overall structure. Assuming that the input is
a Yes-instance, guess an edge (uv) in the perfect matching cut. This gives us an
initial partial matching cut (A = {u}, B = {v}) at a cost of O(m) overhead in the
running time. We preprocess instances using some polynomial-time reduction
rules to ensure that the partial matching cut satisfies a few key invariants. If
none of the reduction rules apply to an instance, it is said to be reduced. Given
a reduced instance that is not fully resolved (i.e: V \ (A ∪ B) is non-empty), we
solve the instance according to a collection of specific branching rules.
As is standard for branch-and-bound algorithms (Fomin and Kratsch, 2010), we
have a measure that we track along the branching process, and the running time
is determined by how the measure drops in each branch. For both our algorithms,
our measure will be the number of vertices that are not in the partial cut: so
when we extend the partial matching cut by committing some vertices from
outside (A ∪ B) to one of A or B, our measure decreases by as much as the
number of vertices that were added to the partial matching cut.
While the improvement we achieve in the running time for general graphs com-
pared to the state of the art is incremental, we propose a conceptually simpler
branching routine. For the case of graphs with maximum degree 3 and girth at
least six, we strengthen the base case and maintain a stronger invariant (namely
that there are no isolated vertices in G[A ∪ B]) to achieve a more substantial
improvement in the running time.
2
For example, if a vertex v ∈ A has a neighbor in B, then all of its other neighbors
must belong to A in any perfect matching cut that extends (A, B).
3
For instance, we may have a vertex v ∈ / A ∪ B, but with two neighbors a ∈ A and
b ∈ B: notice that any perfect matching cut that extends (A, B) either has the edge
(v, a) or the edge (v, b). Thus, we may “branch” on the partial cuts (A ∪ {v}, B) and
(A, B ∪ {v}) to explore these two possibilities.
4
A typical scenario of this kind would be when there is a vertex v ∈/ A ∪ B that has
more than one neighbor in both A and B.
4 Misra and More

2 Preliminaries and Notation

We follow standard graph-theoretic terminology unless mentioned otherwise.
Throughout, G = (V, E) will denote a simple undirected graph, and we use
V(G) and E(G) to denote the vertex and edge sets of G, respectively.
A cut is a partition V(G) = X∪Y of the vertex set into disjoint, non-empty sets X
and Y. The set of all edges in G having an endvertex in X and the other endvertex
in Y, written E(X, Y), is called the edge cut of the cut (X, Y). A matching cut is
an edge cut that is a (possibly empty) matching, while a perfect matching cut
is an edge cut that is a perfect matching. Equivalently, we have the following
definitions:
– a cut (X, Y) is a matching cut if and only if each vertex in X has at most
one neighbor in Y and each vertex in Y has at most one neighbor in X; and
– is a perfect matching cut if and only if each vertex in X has exactly one
neighbor in Y and each vertex in Y has exactly one neighbor in X.
Further, we will typically use the notation in our discussions.
– (A, B) denotes a partial matching cut, where A, B ⊆ V(G), and while A and
B are disjoint, A ∪ B need not be V(G), and each vertex in A has at most
one neighbor in B and each vertex in B has at most one neighbor in A. Note
that G[A ∪ B] need not be a perfect matching cut.
– Given a partial matching cut (A, B), we use F(A,B) to denote V \ (A ∪ B).
When the context is clear, we drop the subscript and just use F. Further, we
use ∂(F) to denote the subset of vertices in F that have at least one neighbor
in A ∪ B, i.e:
∂(F) := {v ∈ F | N(v) ∩ (A ∪ B) ̸= ∅}.

– For a partial matching cut (A, B), we define:

A◦ := {v ∈ A | N(v) ∩ B = ∅} and B◦ := {v ∈ B | N(v) ∩ A = ∅}
and
A⋆ := A \ A◦ and B⋆ := B \ B◦ .
The vertices of A◦ and B◦ are called unsaturated in (A, B) while vertices of
A⋆ and B⋆ are said to be saturated in (A, B).
– We refer to the vertices in F as undetermined.
– We call the vertices in A ∪ B committed.
Given a partial matching cut (A, B), a perfect matching cut (X, Y) is said to
extend (A, B) if A ⊆ X and B ⊆ Y.
We define an instance of the PMC-Extension problem as follows: given a graph
G with a partial matching cut (A, B), determine if G admit a perfect matching
cut that extends (A, B). Note that this generalizes the Perfect Matching
Cut problem, which is the special case when A = B = ∅.
 Finding Perfect Matching Cuts Faster 5

3 Polynomial-Time Reduction Rules

Let (G = (V, E), A, B) be an instance of the PMC-Extension problem where

(A, B) is a partial matching cut of G. Given P, Q ⊆ F(A,B) where P and Q are
disjoint, we use the notation:

GAB [P ⇝ A; Q ⇝ B] := (G, A ∪ P, B ∪ Q).

We slightly abuse this notation in a few ways: if (A, B) is clear from the context
we drop the subscript, if P = ∅, we use the shorter notation G[Q ⇝ B], if P = v
and Q = ∅, we will use G[v ⇝ A], and so on. We now describe some polynomial-
time reduction rules (we borrow and slightly adapt these from Le and Telle).
These will be used to preprocess instances of PMC-Extension.
Reduction Rule 0.[Maintain Valid Cuts] If there is a vertex u ∈ A (resp, B)
that has more than one neighbor in B (repsectively, A), then say No.
Reduction Rule 1.[Neigbors of Saturated Vertices are Determined]
If u ∈ A⋆ (resp, B⋆ ), v ∈ F, and (uv) is an edge; then return G[v ⇝ A] (resp,
G[v ⇝ B]).
Reduction Rule 2.[Last Chance for an Unsaturated Vertex]
If u ∈ A◦ (resp, B◦ ) and N(u) ∩ F = v, then return G[v ⇝ B] (resp, G[v ⇝ A]).
Reduction Rule 3.[No Chance for an Unsaturated Vertex]
If u ∈ A◦ ∪ B◦ and N(u) ∩ F = ∅, then say No.
Reduction Rule 4.[Too Many Neighbors in A ∪ B]
– If u ∈ F with |N(u) ∩ A| ⩾ 2 and |N(u) ∩ B| ⩾ 2 then say No5 .
– If u ∈ F and |N(u) ∩ A| ⩾ 2 (resp, |N(u) ∩ B| ⩾ 2) then return G[u ⇝ A]
(resp, G[u ⇝ B]).
Reduction Rule 5.[Degree One in F]
If u ∈ ∂(F), d(u) = 2, u has one neighbor in A (resp, B), u has one neighbor v
in F, and v has a neighbor in A ∪ B; then return G[v ⇝ B] (resp, G[v ⇝ A]).
Reduction Rule 6.[Degree One in F Extended]
If u ∈ ∂(F), d(u) = 2, u has one neighbor in A (resp, B), u has one neighbor v
in F, and d(v) = 1; then return G[u ⇝ A, v ⇝ B] (resp, G[v ⇝ A, u ⇝ B]).
Reduction Rule 7.[Degree Zero in F]
If u ∈ ∂(F) such that d(u) ∈ {1, 3} and dF (u) = 0, and if u has exactly one
neighbor in A (resp, B), return G[u ⇝ B] (resp, G[u ⇝ A]).
5
Note that this scenario does not arise if the input graph has maximum degree at
most three.
6 Misra and More

4 Maximum Degree Three and Large Girth

Let (G = (V, E), A, B) be an instance of PMC-Extension, where G is a graph

with maximum degree three and girth at least six6 . Throughout our discussion,
F is used to denote F(A,B) .
We will describe a recursive branching algorithm denoted by A(·) for the prob-
lem. We use P(·) to denote the algorithm that returns an instance after the
exhaustive application of reduction rules 1—7.
We say that an instance (G, A, B) is reduced if P (G, A, B) = (G, A, B), i.e,

none of the reduction rules are applicable on the instance. An instance (G, A, B)
where A = B = ∅ or G[A ∪ B] has isolated vertices is called degenerate. Before
we begin, we specify some useful invariants.

Key Invariants
1. A ∪ B is non-empty.
2. G[A ∪ B] has no isolated vertices.
3. Every vertex in F has at most one neighbor in A and at most one neigh-
bor in B.
4. If (uv) is an edge and u ∈ ∂(F) and v ∈ A ∪ B, then v ∈ A◦ ∪ B◦
5. Every u ∈ A◦ ∪ B◦ has at least two neighbors in F.

We say that an instance clean if it satisfies all the invariants above. Notice that
the reduction rules preserve the invariants, which is to say that if the input sat-
isfies any subset of the invariants above, then so does the output. Further, notice
that a reduced instance is either clean or degenerate. Our branching preserves
invariants: if the input is a clean instance, then so is the output.
Note an instance G of Perfect Matching Cut can be solved by guessing one
edge in the final solution and applying the algorithm for PMC-Extension on
the guess. In particular, we return:

  
_

A P G, A = {u}, B = {v}
e=(u,v)∈E(G)

to determine if G has a perfect matching cut.

We now describe our branching algorithm. We maintain that the input to the
algorithm is clean and reduced with respect to Reduction Rules 1—7. Note that
this holds in the first calls above. The branching rules are executed in the order
in which they are described. The measure is |F|.
6
This implies that G has no triangles or cycles of length four or five.
 Finding Perfect Matching Cuts Faster 7

1. Suppose there is a degree-2 vertex u in ∂(F) with one neighbor (say a) in A

and the other neighbor (say v) in F. Since the instance is reduced, we know
that v has no neighbors in (A ∪ B), and at least one neighbor other than u
in F. We now consider two cases based on the degree of v.
(a) d(v) = 2.
By invariants (2) and (5), we have that a has exactly one neighbor other
than u in F. Further, because of the case we are in, v has exactly one
neighbor other than u in F. Let p be a’s second neighbor in F, and let
q be v’s second neighbor in F. Note that p ̸= q since G has no cycles of
length four. We now branch on whether u is matched to a or v:

   

_
A P G[u ⇝ A, {p, q, v} ⇝ B] A P G[{p, q} ⇝ A, {u, v} ⇝ B] .

Note that p, q, u and v are distinct. Therefore, this is a (4, 4) branch.

(b) d(v) = 3. As in the previous case, by invariants (2) and (5), we have
that a has exactly one neighbor other than u in F. Further, because of
the case we are in, v has exactly two neighbors other than u in F. Let
p be a’s second neighbor in F, and let q and r be v’s second and third
neighbors in F. Note that p ̸= q and p ̸= r since G has no cycles of length
five. We again branch on whether u is matched to a or v:

   

_
A P G[u ⇝ A, {p, q, r, v} ⇝ B] A P G[{p} ⇝ A, {u, v} ⇝ B] .

In the previous case, when u was matched to a, v was matched to q

by lack of choice. This is no longer the situation here, since v has two
neighbors in F. However, in the branch where u is matched to v, we now
have an additional vertex forced into A ∪ B.
Recall that p, q, r, u and v are distinct. Therefore, this is a (5, 3) branch.
The case when there is a degree 2 vertex u in ∂(F) with one neighbor (say
b) in B and the other neighbor (say v) in F is symmetric.
2. Suppose u in ∂(F) is degree three and has one neighbor a in A, one in B
(say b), and one in F (say v). Note that a and b have at least one neighbor
other than v in F, by invariant (5). Let a′ be a’s second neighbor in F and
let b′ be b’s second neighbor in F (c.f. Figure 1). We branch on whether u
is matched to a or b:

   

_
A P G[{v, u} ⇝ A, {a′ , b′ } ⇝ B] A P G[{a′ , b′ } ⇝ A, {v, u} ⇝ B] .


8 Misra and More

Note that we have a′ ̸= v, b′ ̸= v since G has no triangles and a′ ̸= b′ since

G has no cycles of length four.
Therefore, this is a (4, 4) branch.

Fig. 1. A figure describing the setting of Branching Rule 2.

3. Suppose there is a degree-3 vertex v in ∂(F) such that v has one neighbor
a in A and two neighbors p, q in F. Note that a has exactly one neighbor
other than v in F, by invariants (2) and (5), say u. Note that u ∈ ∂(F) and:
– If d(u) = 1 then the instance is not reduced, a contradiction.
– If d(u) = 2 and dF (u) = 1 then we would have branched on u.
– If d(u) = 3 and dF (u) = 1 we would have branched7 on u.
– If d(u) = 3 and dF (u) = 3 then d(u) ⩾ 4, a contradiction.
Therefore, we have that d(u) = 3 and dF (u) = 2 or d(u) = 2 and dF (u) = 0.
We analyze these cases separately.
(a) d(u) = 3 and dF (u) = 2.
7
Indeed, in this scenario u would then be a degree three vertex in ∂(F) with one
neighbor each in a A and B (notice that this is the only possibility because of our
assumption that the instance is reduced).
 Finding Perfect Matching Cuts Faster 9

Let the neighbors of u in F be r and s (c.f. Figure 2). We branch on

whether a is matched to u or v:

   

_
A P G[v ⇝ A, {u, r, s} ⇝ B] A P G[u ⇝ A, {v, p, q} ⇝ B] .

Note that we have {r, s} ∩ {p, q} = ∅ since G has no cycles of length four.
Therefore, this is a (4, 4) branch.

Fig. 2. A figure describing the setting of Case (a) within Branching Rule 3.

(b) d(u) = 2 and dF (u) = 0.

By invariant (3), we know that u’s second neighbor (say b) belongs to
B. Note that by invariants (2) and (5), b must have exactly one more
neighbor in F other than u: let this neighbor be w. Here we branch on
whether u is matched to a or b:

   

_
A P G[{w, v} ⇝ A, u ⇝ B] A P G[u ⇝ A, {v, p, q, w} ⇝ B] .


10 Misra and More

Note that w ̸= p and w ̸= q, since G has no cycles of length five.

Therefore, this is a (3, 5) branch.

Fig. 3. A figure describing the setting of Case (b) within Branching Rule 3.

The case when there is a degree 3 vertex v in ∂(F) such that v has one
neighbor b in B and two neighbors p, q in F is symmetric and analogously
handled.
This completes the description of the branching rules.
 Finding Perfect Matching Cuts Faster 11

Observe that if none of the branching rules are applicable on a clean and reduced
instance, then note that we have the following:
1. Every vertex in ∂(F) has degree two in G: indeed, if we have a degree three
vertex in ∂(F), then we would have branched according to branching rules
2 or 3; and if we have a degree one vertex in ∂(F), then the instance is not
reduced. Combined with invariant (3), we have that every vertex in ∂(F) has
exactly one neighbor in A and exactly one neighbor in B.
2. Every vertex in A◦ ∪ B◦ has exactly two neighbors in F: this follows from
the assumption about the maximum degree of the graph being three, and
invariants (2) and (5). Therefore, we have that everyvertex has degree two
in the graph G[∂(F) ∪ A◦ ∪ B◦ ] \ E[G[A]] ∪ E[G[B]] , which is to say that
this subgraph is a disjoint union of cycles. Further, note that F \ ∂(F) = ∅,
since G is connected.
Observe that this instance can be solved in polynomial time by checking the
parity of the cycles. This concludes our handling of the base case of the algorithm.
It can be verified that all the branching and reduction rules preserve the invari-
ants, and this can be used to establish that the branching rules are exhaustive
and correct. These arguments are implicit in the description of the branching
rules.

Running Time Analysis. Recall that an algorithm branches on an instance of size

n into r subproblems of sizes at most n−t1 , n−t2 , . . . , n−tr , then (t1 , t2 , . . . , tr )
is called the branching vector of this branching, and the unique positive root of
xn − xn t1 − xnt2 − · · · − xn tr = 0, denoted by τ (t1 , t2 , . . . , tr ), is called its
branching factor. The running time of a branching algorithm is O∗ (αn ), where
α = maxi αi and αi is the branching factor of branching rule i, and the maximum
is taken over all branching rules (c.f. the book by Fomin and Kratsch). Since
τ(3, 5) = 1.1938 and τ(4, 4) = 1.1892, and therefore we have the following.

Theorem 1. The Perfect Matching Cut problem admits an algorithm with

running time O∗ (1.1938n ) on graphs of maximum degree 3 and girth at least six.

5 Concluding Remarks
We show improved algorithms for Perfect Matching Cut on general graphs
and graphs of maximum degree 3 and girth at least six. A natural question is if
we can achieve a comparable running time without the assumption of excluding
short cycles. We believe this can be done with a more careful case analysis.
Obtaining a sub-exponential running time for bipartite graphs with maximum
degree three and girth g, matching the ETH-based lower bound from Le and
Telle is also a natural open problem.
Due to lack of space, we defer our second result about a O∗ (1.2599n )-algorithm
applicable to all n-vertex graphs to a full version of this paper.
 Bibliography

Bui-Xuan, B.-M., Telle, J. A., and Vatshelle, M. (2013). Fast dynamic pro-
gramming for locally checkable vertex subset and vertex partitioning problems.
Theoretical Computer Science, 511:66–76.
Chen, C.-Y., Hsieh, S.-Y., Le, H.-O., Le, V. B., and Peng, S.-L. (2021). Matching
cut in graphs with large minimum degree. Algorithmica, 83(5):1238–1255.
Chvátal, V. (1984). Recognizing decomposable graphs. Journal of Graph Theory,
8(1):51–53.
Feghali, C., Lucke, F., Paulusma, D., and Ries, B. (2023). Matching cuts in
graphs of high girth and h-free graphs.
Fomin, F. V. and Kratsch, D. (2010). Exact Exponential Algorithms. Texts in
Theoretical Computer Science. An EATCS Series. Springer.
Golovach, P. A., Komusiewicz, C., Kratsch, D., and Le, V. B. (2021). Refined
Notions of Parameterized Enumeration Kernels with Applications to Matching
Cut Enumeration. In 38th International Symposium on Theoretical Aspects of
Computer Science (STACS 2021), volume 187, pages 37:1–37:18.
Heggernes, P. and Telle, J. A. (1998). Partitioning graphs into generalized dom-
inating sets. Nordic J. of Computing, 5(2):128–142.
Komusiewicz, C., Kratsch, D., and Le, V. B. (2018). Matching Cut: Kernel-
ization, Single-Exponential Time FPT, and Exact Exponential Algorithms. In
13th International Symposium on Parameterized and Exact Computation (IPEC
2018), pages 19:1–19:13.
Le, V. B. and Telle, J. A. (2022). The perfect matching cut problem revisited.
Theor. Comput. Sci., 931:117–130.
Telle, J. A. and Proskurowski, A. (1997). Algorithms for vertex partitioning
problems on partial k-trees. SIAM Journal on Discrete Mathematics, 10(4):529–
550.
Édouard Bonnet, Chakraborty, D., and Duron, J. (2023). Cutting barnette
graphs perfectly is hard.