# Finding a Maximum Restricted $t$-Matching
via Boolean Edge-CSP

Yuni Iwamasa Kyoto University. E-mail<EMAIL_ADDRESS>Yusuke
Kobayashi Kyoto University. E-mail<EMAIL_ADDRESS>Kenjiro
Takazawa Hosei University. E-mail<EMAIL_ADDRESS>
###### Abstract

The problem of finding a maximum $2$-matching without short cycles has
received significant attention due to its relevance to the Hamilton cycle
problem. This problem is generalized to finding a maximum $t$-matching which
excludes specified complete $t$-partite subgraphs, where $t$ is a fixed
positive integer. The polynomial solvability of this generalized problem
remains an open question. In this paper, we present polynomial-time algorithms
for the following two cases of this problem: in the first case the forbidden
complete $t$-partite subgraphs are edge-disjoint; and in the second case the
maximum degree of the input graph is at most $2t-1$. Our result for the first
case extends the previous work of Nam (1994) showing the polynomial
solvability of the problem of finding a maximum $2$-matching without cycles of
length four, where the cycles of length four are vertex-disjoint. The second
result expands upon the works of Bérczi and Végh (2010) and Kobayashi and Yin
(2012), which focused on graphs with maximum degree at most $t+1$. Our
algorithms are obtained from exploiting the discrete structure of restricted
$t$-matchings and employing an algorithm for the Boolean edge-CSP.

Keywords

Polynomial algorithm, $C_{k}$-free $2$-matching, Jump system, Boolean edge-CSP

##  1 Introduction

The matching problem and its generalizations have been one of the most primary
topics in combinatorial optimization, and have been the subject of a large
number of studies. A typical generalization of a matching is a $t$-matching
for an arbitrary positive integer $t$: an edge subset $M$ in a graph is a
$t$-matching111Such an edge set is sometimes called a simple $t$-matching in
the literature, but we omit the adjective “simple” because in this article a
$t$-matching is always an edge subset and we never put multiplicities on the
edges. if each vertex is incident to at most $t$ edges in $M$.

While the problem of finding a $t$-matching of maximum cardinality can be
solved in polynomial time by a matching algorithm, the problem becomes much
more difficult, typically NP-hard, when additional constraints are imposed.
The constraints discussed in this paper is to exclude certain subgraphs. Let
$G=(V,E)$ be a graph and let ${\cal K}$ be a family of subgraphs of $G$. For a
subgraph $K$ of $G$, let $V(K)$ and $E(K)$ denote the vertex set and the edge
set of $K$, respectively.

######  Definition 1.1.

An edge subset $M\subseteq E$ is _${\cal K}$ -free_ if $E(K)\not\subseteq M$
for any $K\in{\cal K}$.

The problem formulated below is the central issue in this paper, whose
relevance will be described in detail in Section 1.1.

##### Maximum ${\cal K}$-Free $t$-Matching Problem

Given a graph $G=(V,E)$ and a family $\mathcal{K}$ of subgraphs of $G$, find a
$\mathcal{K}$-free $t$-matching $M\subseteq E$ of maximum cardinality.

Our primary contribution are the following two theorems, showing the
polynomial solvability of certain classes of Maximum ${\cal K}$-Free
$t$-Matching Problem. The first result concerns the case where ${\cal K}$ is
an edge-disjoint family of _$t$ -regular complete partite subgraphs_ of $G$.
While we defer the definition to Section 2.1, here we remark that a complete
graph $K_{t+1}$ and a complete bipartite graph $K_{t,t}$ are examples of a
$t$-regular complete partite graph.

######  Theorem 1.2.

For a fixed positive integer $t$, Maximum ${\cal K}$-Free $t$-Matching Problem
can be solved in polynomial time if all the subgraphs in ${\cal K}$ are
$t$-regular complete partite and pairwise edge-disjoint.

In the second result, instead of the edge-disjointness of the subgraphs in
$\mathcal{K}$, we assume that the maximum degree of the input graph $G$ is
bounded.

######  Theorem 1.3.

For a fixed positive integer $t$, Maximum ${\cal K}$-Free $t$-Matching Problem
can be solved in polynomial time if all the subgraphs in ${\cal K}$ are
$t$-regular complete partite and the maximum degree of $G$ is at most $2t-1$.

Theorems 1.2 and 1.3 offer larger polynomially solvable classes of Maximum
${\cal K}$-Free $t$-Matching Problem than the previous work introduced in
Section 1.1 below. In addition, we will describe the relevance of Theorems 1.2
and 1.3 to the literature, together with their extensions and variants in the
subsequent sections. Here we just remark that the assumption on the complete
partiteness of the forbidden subgraphs in Theorems 1.2 and 1.3 is unavoidable,
because the problem is NP-hard without this assumption (see Proposition 1.4
below).

###  1.1 Previous Work on Restricted $t$-Matchings

Maximum ${\cal K}$-Free $t$-Matching Problem has its origin in the case where
$t=2$ and ${\cal K}$ is composed of short cycles. Let $k$ be a positive
integer. If ${\cal K}$ is the set of all cycles of length at most $k$, then a
$\mathcal{K}$-free $2$-matching is referred to as a _$C_{\leq k}$ -free
$2$-matching_, and Maximum ${\cal K}$-Free $2$-Matching Problem as the
_$C_{\leq k}$ -free $2$-matching problem_. Similarly, if ${\cal K}$ is the set
of all cycles of length exactly $k$, then a $\mathcal{K}$-free $2$-matching is
referred to as a _$C_{k}$ -free $2$-matching_, and Maximum ${\cal K}$-Free
$2$-Matching Problem as the _$C_{k}$ -free $2$-matching problem_. The $C_{\leq
k}$-free and $C_{k}$-free $2$-matching problems have attracted significant
attention because of their relevance to the Hamilton cycle problem; for
$k\geq|V|/2$, a $C_{\leq k}$-free $2$-matching of cardinality $|V|$ is a
Hamilton cycle. When $k$ is small, the $C_{\leq k}$-free $2$-matching problem
is not directly used to find Hamilton cycles, but it can be applied to
designing approximation algorithms for related problems such as the graph-TSP
and the minimum $2$-edge-connected spanning subgraph problem. For example, in
a recent paper [26], an approximation algorithm for the minimum 2-edge-
connected spanning subgraph problem is provided using a maximum $C_{\leq
3}$-free $2$-matching.

The complexity of the $C_{\leq k}$-free $2$-matching problem depends on the
value of $k$. It is straightforward to see that this problem can be solved in
polynomial time for $k\leq 2$. For $k=3$, Hartvigsen [14] gave a polynomial-
time algorithm for the $C_{\leq 3}$-free $2$-matching problem. For $k\geq 5$,
Papadimitriou proved the NP-hardness of the $C_{\leq k}$-free $2$-matching
problem (see [8]).

For the case $k=4$, it is open whether the $C_{\leq 4}$-free and $C_{4}$-free
$2$-matching problems can be solved in polynomial time, and these problems
have rich literature of polynomial-time algorithms for several special cases.
First, for subcubic graphs, i.e., graphs with maximum degree at most three,
polynomial-time algorithms for the $C_{4}$-free and the $C_{\leq 4}$-free
$2$-matching problems were given by Bérczi and Kobayashi [3] and Bérczi and
Végh [4], respectively. Simpler algorithms for both problems in subcubic
graphs (and for some of their weighted variants) were designed by Hartvigsen
and Li [16] and by Paluch and Wasylkiewicz [36]. It is worth noting that a
connection between the $C_{4}$-free matching problem and a connectivity
augmentation problem is highlighted in [3], underscoring the significance of
the $C_{4}$-free matching problem. Second, for the graphs in which the cycles
of length four are vertex-disjoint, Nam [34] gave a polynomial-time algorithm
for the $C_{4}$-free $2$-matching problem. Finally, for bipartite graphs,
several of polynomial-time algorithms are devised; see Section 1.3 for
details.

Let $t$ be an arbitrary positive integer. The $C_{k}$-free $2$-matching
problem is generalized to Maximum ${\cal K}$-Free $t$-Matching Problem for
general $t$ in the following way. Let $K_{t}$ denote the complete graph with
$t$ vertices, and $K_{t,t}$ the complete bipartite graph in which each color
class has $t$ vertices. Here, note that a cycle of length three is isomorphic
to $K_{3}$. Thus, the $C_{3}$-free $2$-matching problem can be naturally
generalized to Maximum ${\cal K}$-Free $t$-Matching Problem, where ${\cal K}$
is the set of all subgraphs that are isormorphic to $K_{t+1}$. We refer to
this special case of Maximum ${\cal K}$-Free $t$-Matching Problem as the
_$K_{t+1}$ -free $t$-matching problem_. Similarly, by noting that a cycle of
length four is isomorphic to $K_{2,2}$, we can generalize the $C_{4}$-free
$2$-matching problem to the _$K_{t,t}$ -free $t$-matching problem_. This is
another special class of Maximum ${\cal K}$-Free $t$-Matching Problem, where
${\cal K}$ is the set of all subgraphs isormorphic to $K_{t,t}$.

The polynomial solvability of these two problems are open. For certain special
cases of Maximum ${\cal K}$-Free $t$-Matching Problem, however, several
polynomial-time algorithms are presented, corresponding to those for the
$C_{\leq k}$-free and $C_{k}$-free $2$-matching problems. First, Bérczi and
Végh [4] gave a polynomial-time algorithm for Maximum ${\cal K}$-Free
$t$-Matching Problem for the case where ${\cal K}$ consists of $K_{t+1}$’s and
$K_{t,t}$’s and the input graph $G$ has maximum degree at most $t+1$. This
extends that for the $C_{\leq 4}$-free $2$-matching problem in subcubic
graphs. Second, Kobayashi and Yin [28] presented a polynomial-time algorithm
for Maximum ${\cal K}$-Free $t$-Matching Problem for the case where ${\cal K}$
consists of all the subgraphs isomorphic to a fixed $t$-regular complete
partite graph and the input graph $G$ has maximum degree at most $t+1$.
Kobayashi and Yin [28] also proved that this assumption on $\mathcal{K}$ is
inevitable.

######  Proposition 1.4 (follows from Kobayashi and Yin [28]).

If $H$ is a connected $t$-regular graph which is not complete partite and
${\cal K}$ is the set of all subgraphs isomorphic to $H$, then Maximum ${\cal
K}$-Free $t$-Matching Problem is NP-hard even when the maximum degree of $G$
is at most $t+1$ and the subgraphs in $\mathcal{K}$ are pairwise edge-
disjoint.

As mentioned above, this NP-hardness explains that the assumption on the
complete partiteness of the forbidden subgraphs is also unavoidable in
Theorems 1.2 and 1.3.

Finally, for the $K_{t,t}$-free $t$-matching problem in bipartite graphs, some
polynomial-time algorithms are designed, extending those for the $C_{4}$-free
$2$-matching problem in bipartite graphs (see Section 1.3).

###  1.2 Our Contribution

We have seen that the polynomial solvability of the $K_{t+1}$-free
$t$-matching and $K_{t,t}$-free $t$-matching problems is unkown. As well as
these problems, the polynomial solvability of Maximum ${\cal K}$-Free
$t$-Matching Problem in general graphs for ${\cal K}$ being an arbitrary
family of $t$-regular complete partite subgraphs is unknown. The contribution
of this paper is to present polynomial-time algorithms for several special
cases of this problem.

####  1.2.1 Overview of Our Results

Recall our first result, Theorem 1.2, solving the case where ${\cal K}$ is an
edge-disjoint family of $t$-regular complete partite subgraphs of $G$. By
setting $t=2$ in Theorem 1.2, we immediately obtain the following corollary.

######  Corollary 1.5.

Maximum ${\cal K}$-Free $2$-Matching Problem can be solved in polynomial time
if all the subgraphs in ${\cal K}$ are isomorphic to $C_{3}$ or $C_{4}$, and
are pairwise edge-disjoint.

Corollary 1.5 extends the result by Nam [34], solving the $C_{4}$-free
$2$-matching problem where the cycles of length four are vertex-disjoint.
Namely, Corollary 1.5 extends vertex-disjointness to edge-disjointness, and
allows ${\cal K}$ to include not only $C_{4}$ but also $C_{3}$.

Next, recall our second result, Theorem 1.3, which solves the case where the
maximum degree of the input graph is at most $2t-1$. Theorem 1.3 expands upon
the works of Bérczi and Végh [4] and Kobayashi and Yin [28], which focused
graphs with maximum degree at most $t+1$. That is, Theorem 1.3 improves the
degree bound from $t+1$ to $2t-1$, where $2t-1>t+1$ if $t>2$.

We further present some extensions of Theorems 1.2 and 1.3. Below is one
extension of Theorem 1.2, which will be used in our proof for Theorem 1.3. The
pairwise edge-disjointness of the subgraphs in $\mathcal{K}$ is relaxed to the
following condition:

  1. (RD)

The subgraph family $\mathcal{K}$ is partitioned into subfamilies
$\mathcal{K}_{1},\dots,\mathcal{K}_{\ell}$ such that

     * •

for each subfamily $\mathcal{K}_{i}$ ($i=1,\ldots,\ell$), the number
$\left|\bigcup_{K\in\mathcal{K}_{i}}V(K)\right|$ of its vertices is bounded by
a fixed constant, and

     * •

for distinct subfamilies $\mathcal{K}_{i}$ and $\mathcal{K}_{j}$
($i,j\in\\{1,\dots,\ell\\})$ and for each pair of subgraphs
$K\in\mathcal{K}_{i}$ and $K^{\prime}\in\mathcal{K}_{j}$, it holds that $K$
and $K^{\prime}$ are edge-disjoint.

Here “RD” stands for “Relaxed Disjointness.”

######  Theorem 1.6.

For a fixed positive integer $t$, Maximum ${\cal K}$-Free $t$-Matching Problem
can be solved in polynomial time if $\mathcal{K}$ is a family of $t$-regular
complete partite subgraphs of $G$ satisfying the condition (RD).

Other results include extensions from $t$-matchings to $b$-matchings (Theorems
3.1, 3.4, 3.5, 4.1, and 4.3). For a vector $b\in\mathbb{Z}^{V}$, a _$b$
-matching_ is an edge subset $M\subseteq E$ such that each vertex $v\in V$ is
incident to at most $b(v)$ edges in $M$. Namely, we can deal with
inhomogeneous degree constraints. Moreover, we provide an extension from
forbidding subgraphs to forbidding degree sequences (Theorem 5.1). In
particular, the latter extension offers some new results on restricted
$2$-matchings (Examples 5.2 and 5.3).

####  1.2.2 Technical Ingredients

Technically, our algorithms are established by exploiting two important
previous results, one is on the discrete structure of $\mathcal{K}$-free
$t$-matchings and the other is on the constraint satisfaction problem (CSP).
This is in contrast to the fact that the previous algorithms [4, 28, 34] are
based on graph-theoretical methods.

The first result is outlined as follows. Let $b\in\mathbb{Z}^{V}$ with
$b(v)\leq t$ for each $v\in V$ and let $J\subseteq\mathbb{Z}^{V}$ be the set
of the degree sequences of all $\mathcal{K}$-free $b$-matching in $G$.
Kobayashi, Szabó, and Takazawa [27] proved that $J$ forms a _constant-parity
jump system_ if all the subgraphs in $\mathcal{K}$ are $t$-regular complete
partite (see Theorem 2.3 below). Here a constant-parity jump system is a
subset of $\mathbb{Z}^{V}$, which offer a discrete structure generalizing
matroids; see Section 2.2 for the definition.

The second is on the polynomial-time solvability of a class of the CSP. The
_Boolean edge-CSP_ is the problem of finding an edge subset $M\subseteq E$ of
a given graph $G=(V,E)$ such that the set of edges in $M$ incident to each
vertex $v\in V$ satisfies a certain constraint associated with $v$; see
Section 2.3 for formal description. While the Boolean edge-CSP is NP-hard in
general, Kazda, Kolmogorov, and Rolínek [18] showed that this problem can be
solved in polynomial time if the constraint associated with $v$ is described
by a constant-parity jump system for each $v\in V$ (see Theorem 2.6 below).

The most distinctive part of this paper is a reduction of Maximum ${\cal
K}$-Free $t$-Matching Problem to the Boolean edge-CSP. It appears in the proof
of Theorem 3.1 below, which deals with the problem of finding a
$\mathcal{K}$-free $b$-factor, i.e., a $t$-matching with specified degree
sequence $b\in\mathbb{Z}^{V}$. Here, on the basis of the relationship between
$\mathcal{K}$-free $b$-matchings and jump systems (Theorem 2.3), we construct
a polynomial reduction of the problem of finding a $\mathcal{K}$-free
$b$-factor to the Boolean edge-CSP with constant-parity jump system
constraints.

Theorem 1.2 is then derived from Theorem 3.1. In order to prove Theorem 1.2,
we iteratively solve subproblems of finding a $\mathcal{K}$-free $b$-factor.
We remark that constant-parity jump systems play a key role here, as well as
the reduction mentioned above. The fact that $J$ is a constant-parity jump
system guarantees that the number of the iterations is polynomially bounded by
the input size (see Lemma 2.5 below).

Theorem 1.6 is proved in the same manner. We then derive Theorem 1.3 from
Theorem 1.6 by constructing a subfamily
$\mathcal{K}^{\prime}\subseteq\mathcal{K}$ such that $\mathcal{K}^{\prime}$
satisfies (RD), a $\mathcal{K}^{\prime}$-free $t$-matching exists in $G$ if
and only if a $\mathcal{K}$-free $t$-matching exists in $G$, and we can
construct a $\mathcal{K}$-free $t$-matching from a $\mathcal{K}^{\prime}$-free
$t$-matching in polynomial time.

###  1.3 Further Related Work

The $C_{4}$-free $2$-matching problem has been actively studied in the setting
when the input graph is restricted to be bipartite. Hartvigsen [15], Király
[19, 20], and Frank [13] gave min-max theorems for the $C_{4}$-free
$2$-matching problem in bipartite graphs, and more generally for the
$K_{t,t}$-free $t$-matching problem in bipartite graphs, which implies the
polynomial solvability of the problems. To the best of our knowledge, Frank
[13] is the first work to generalize the restricted $2$-matching in this
context to $t$-matchings. For the $C_{4}$-free $2$-matching problem in
bipartite graphs, Hartvigsen [15] and Pap [37] designed combinatorial
polynomial-time algorithms, Babenko [2] improved the running time, and
Takazawa [45] showed a decomposition theorem. Takazawa [46, 47] extended these
results to more generalized classes of Maximum ${\cal K}$-Free $t$-Matching
Problem.

The weighted variant of Maximum ${\cal K}$-Free $t$-Matching Problem has also
attracted much attention. In the weighted problem, an input consists of a
graph, a family ${\cal K}$ of subgraphs, and a non-negative weight function on
the edge set, and the objective is to find a ${\cal K}$-free $t$-matching with
maximum total weight. It is shown by Király (see [13]) and by Bérczi and
Kobayashi [3] that the weighted $C_{\leq 4}$-free $2$-matching problem is NP-
hard even if the input graph is restricted to be cubic, bipartite, and planar.
For the weighted $C_{4}$-free $2$-matching problem in bipartite graphs, and
more generally for the weighted $K_{t,t}$-free $t$-matching problem in
bipartite graphs, under the assumption that the weight function satisfies a
certain property, Makai [31] gave a polyhedral description, Takazawa [44]
designed a combinatorial polynomial-time algorithm, and Paluch and
Wasylkiewicz [35] presented a faster and simpler algorithm.

It is still open whether the weighted $C_{3}$-free $2$-matching problem can be
solved in polynomial time. For the weighted $C_{3}$-free $2$-matching problem
in subcubic graphs, Hartvigsen and Li [17] gave a polyhedral description and a
polynomial-time algorithm, and faster polynomial-time algorithms were
presented by Kobayashi [21] and by Paluch and Wasylkiewicz [36]. Recently,
Kobayashi [23] designed a polynomial-time algorithm for the weighted
$C_{3}$-free $2$-matching problem in which the cycles of length three are
edge-disjoint.

The relationship between ${\cal K}$-free $t$-matchings and jump systems has
been studied in [3, 9, 27], some of which will be used in this paper. More
generally, the relationship between weighted ${\cal K}$-free $t$-matchings and
discrete convexity has been studied in [3, 21, 22, 27].

###  1.4 Organization

The rest of the paper is organized as follows. In Section 2, we present the
basic definitions and results in a formal manner. In Section 3, we solve the
problem under the assumption that the subgraphs in $\mathcal{K}$ are pairwise
edge-disjoint, and then under the relaxed condition (RD). Section 4 is devoted
to a solution to the graphs with maximum degree at most $2t-1$. Finally, in
Section 5, we deal with a more generalized problem where the forbidden
structure is described in terms of degree sequences.

##  2 Preliminaries

Let $\mathbb{Z}_{+}$ denote the set of nonnegative integers, and ${\bf 0}$
(resp. ${\bf 1}$) denote the all-zero (resp. all-one) vector of appropriate
dimension. For a finite set $V$, its subset $U\subseteq V$, and a vector
$x\in\mathbb{Z}^{V}$, let $x(U)=\sum_{v\in U}x(u)$.

###  2.1 Basic Definitions on Graphs

Throughout this paper, we assume that graphs have no self-loops to simplify
the description, while they may have parallel edges. Let $G=(V,E)$ be a graph.
For a subgraph $H$ of $G$, let $V(H)$ and $E(H)$ denote the vertex set and
edge set of $H$, respectively. For a vertex set $X\subseteq V$, let $G[X]$
denote the subgraph induced by $X$.

Let $F\subseteq E$ be an edge subset and let $v\in V$ be a vertex. The set of
edges in $F$ incident to $v$ is denoted by $\delta_{F}(v)$. If $F=E(H)$ for
some subgraph $H$ of $G$, then $\delta_{E(H)}(v)$ is often abbreviated as
$\delta_{H}(v)$. When no confusion arises, $\delta_{G}(v)$ is further
abbreviated as $\delta(v)$. The number of edges incident to $v$, i.e.,
$|\delta(v)|$, is referred to as the _degree_ of $v$. The _degree sequence_
$d_{F}$ of $F\subseteq E$ is a vector in $\mathbb{Z}_{+}^{V}$ defined by
$d_{F}(u)=|\delta_{F}(u)|$ for each $u\in V$.

For a positive integer $t$, a graph is called _$t$ -regular_ if every vertex
has degree $t$. A graph $G=(V,E)$ is said to be a _complete partite graph_ if
there exists a partition $\\{V_{1},\dots,V_{p}\\}$ of $V$ such that
$E=\\{uv\colon u\in V_{i},v\in V_{j},i\neq j\\}$ for some positive integer
$p$. In other words, a complete partite graph is the complement of the
disjoint union of complete graphs. Each $V_{i}$ is called a _color class_ of
$G$.

As defined in Section 1, for a positive integer $t$, an edge set $M\subseteq
E$ is called a _$t$ -matching_ if $d_{M}(v)\leq t$ for every $v\in V$. In
particular, if $d_{M}(v)=t$ holds for every $v\in V$, then $M$ is called a
_$t$ -factor_. For a vector $b\in\mathbb{Z}_{+}^{V}$, an edge set $M\subseteq
E$ is called a _$b$ -matching_ (resp.  _$b$ -factor_) if $d_{M}(v)\leq b(v)$
(resp. $d_{M}(v)=b(v)$) for every $v\in V$.

In what follows, instead of Maximum ${\cal K}$-Free $t$-Matching Problem, we
deal with the following slightly generalized problems.

##### ${\cal K}$-Free $b$-Factor Problem

Given a graph $G=(V,E)$, $b\in\mathbb{Z}_{+}^{V}$, and a family $\mathcal{K}$
of subgraphs of $G$, find a $\mathcal{K}$-free $b$-factor (if one exists).

##### Maximum ${\cal K}$-Free $b$-Matching Problem

Given a graph $G=(V,E)$, $b\in\mathbb{Z}_{+}^{V}$, and a family ${\cal K}$ of
subgraphs of $G$, find a $\mathcal{K}$-free $b$-matching with maximum
cardinality.

Note that Maximum ${\cal K}$-Free $t$-Matching Problem is a special case of
Maximum ${\cal K}$-Free $b$-Matching Problem, where $b(v)=t$ for each $v\in
V$.

######  Remark 2.1.

In this paper, we only consider the case where ${\cal K}$ consists of
subgraphs of size bounded by a fixed constant (e.g., $t$-regular complete
partite subgraphs for a fixed integer $t$). In such a case, since $|{\cal K}|$
is polynomially bounded by the size of the input graph, the representation of
${\cal K}$ does not affect the polynomial solvability of the problem.
Therefore, in what follows, we suppose that ${\cal K}$ is explicitly given as
the list of its elements.

######  Remark 2.2.

Let $G=(V,E)$ be a graph, $b\in\mathbb{Z}_{+}^{V}$ with $b(v)\leq t$ for each
$v\in V$, and $K$ a connected $t$-regular subgraph of $G$. We can easily
observe that, if a $b$-matching $M\subseteq E$ of $G$ contains $K$, then $K$
forms a connected component of the induced subgraph $(V,M)$ of $G$ by $M$.

###  2.2 Jump System

Let $V$ be a finite set. For a subset $U\subseteq V$, let
$\chi_{U}\in\\{0,1\\}^{V}$ denote the characteristic vector of $U$, that is,
$\chi_{U}(v)=1$ for $v\in U$ and $\chi_{U}(v)=0$ for $v\in V\setminus U$. If
$U=\\{u\\}$ for an element $u\in V$, then $\chi_{\\{u\\}}$ is simply denoted
by $\chi_{u}$.

For two vectors $x,y\in\mathbb{Z}^{V}$, a vector $s\in\mathbb{Z}^{V}$ is
called an _$(x,y)$ -increment_ if $s=\chi_{u}$ and $x(u)<y(u)$ for some $u\in
V$, or $s=-\chi_{u}$ and $x(u)>y(u)$ for some $u\in V$. A nonempty set
$J\subseteq\mathbb{Z}^{V}$ is said to be a _jump system_ if it satisfies the
following exchange axiom (see [5]):

> For any $x,y\in J$ and for any $(x,y)$-increment $s$ with $x+s\not\in J$,
> there exists an $(x+s,y)$-increment $t$ such that $x+s+t\in J$.

In particular, a jump system $J\subseteq\mathbb{Z}^{V}$ is called a _constant-
parity jump system_ if $x(V)-y(V)$ is even for any $x,y\in J$.

Constant-parity jump systems include several discrete structures as special
classes. First, for a matroid with a basis family ${\cal B}$, it follows from
the exchange property of matroid bases that $\\{\chi_{B}\colon B\in{\cal
B}\\}$ is a constant-parity jump system. Second, the characteristic vectors of
all the feasible sets of an even delta-matroid form a constant-parity jump
system (see [5]). Finally, for a graph $G=(V,E)$, the set $\\{d_{F}\colon
F\subseteq E\\}$ of the degree sequences of all the edge subsets is also a
constant-parity jump system. See [5, 30, 32] for details on jump systems.

The following theorem shows a relationship between ${\cal K}$-free
$b$-matchings and jump systems.

######  Theorem 2.3 (follows from [27, Proposition 3.1]).

Let $G=(V,E)$ be a graph, let $t$ be a positive integer, and let
$b\in\mathbb{Z}_{+}^{V}$ be a vector such that $b(v)\leq t$ for each $v\in V$.
For a family ${\cal K}$ of complete partite $t$-regular subgraphs in $G$, the
degree sequences of all ${\cal K}$-free $b$-matchings in $G$ form a constant-
parity jump system.

######  Remark 2.4.

Theorem 2.3 is a modest extension of the original statement [27, Proposition
3.1], in which $b(v)=t$ for each $v\in V$ and ${\cal K}$ is the set of all
subgraphs in $G$ that are isomorphic to a graph in a given list of complete
partite $t$-regular subgraphs. The same proof, however, works for Theorem 2.3
as well.

We here describe a few basic operations on jump systems, which will be used in
the subsequent sections.

##### Intersection with a box.

A _box_ is a set of the form $\\{x\in\mathbb{R}^{V}\colon\underline{b}\leq
x\leq\overline{b}\\}$ for some vectors
$\underline{b}\in(\mathbb{R}\cup\\{-\infty\\})^{V}$ and
$\overline{b}\in(\mathbb{R}\cup\\{+\infty\\})^{V}$. If
$J\subseteq\mathbb{Z}^{V}$ is a constant-parity jump system, then the
intersection

$J\cap\\{x\in\mathbb{R}^{V}\colon\underline{b}\leq x\leq\overline{b}\\}$

of $J$ and a box is also a constant-parity jump system unless it is empty.

##### Minkowski sum.

For two sets $J_{1},J_{2}\subseteq\mathbb{Z}^{V}$, their _Minkowski sum_
$J_{1}+J_{2}$ is a subset of $\mathbb{Z}^{V}$ defined by

$J_{1}+J_{2}=\\{x+y\colon x\in J_{1},\ y\in J_{2}\\}.$

It was shown by Bouchet and Cunningham [5] that the Minkowski sum of two
constant-parity jump systems is also a constant-parity jump system.

##### Splitting.

Let $\\{U_{v}\colon v\in V\\}$ be a family of nonempty disjoint finite sets
indexed by $v\in V$, and let $U=\bigcup_{v\in V}U_{v}$. For a set
$J\subseteq\mathbb{Z}^{V}$, we define the _splitting_ of $J$ to $U$ as

$J^{\prime}=\\{x^{\prime}\in\mathbb{Z}^{U}\colon\mbox{$x^{\prime}(U_{v})=x(v)$
for each $v\in V$ for some $x\in J$}\\}.$

The splitting of a constant-parity jump system is also a constant-parity jump
system; see [33, 25].

If the degree sequences of all the $\mathcal{K}$-free $b$-matchings form a
constant-parity jump system, then Maximum ${\cal K}$-Free $b$-Matching Problem
reduces to ${\cal K}$-Free $b$-Factor Problem which is formally stated as
follows.

######  Lemma 2.5.

Let $G=(V,E)$ be a graph, ${\cal K}$ be a family of subgraphs of $G$, and let
$b\in\mathbb{Z}^{V}_{+}$. If the degree sequences of all the ${\cal K}$-free
$b$-matchings in $G$ form a constant-parity jump system, then a ${\cal
K}$-free $b$-matching in $G$ with maximum cardinality can be computed by
testing the existence of a ${\cal K}$-free $b^{\prime}$-factor in $G$ for
polynomially many vectors $b^{\prime}\in\mathbb{Z}^{V}_{+}$ with
$b^{\prime}\leq b$.

###### Proof.

Denote by $J\subseteq\mathbb{Z}^{V}$ the constant-parity jump system
consisting of the degree sequences of all the ${\cal K}$-free $b$-matchings in
$G$. Given an initial vector in $J$, we can maximize a given linear function
over $J$ by using the membership oracle of $J$ at most polynomially many times
[42, 5, 1]. Here, the _membership oracle of $J$_ is an oracle that answers
whether a given vector is in $J$ or not.

Since an empty edge set is a ${\cal K}$-free $b$-matching, it holds that ${\bf
0}\in J$. That is, we can take ${\bf 0}$ as the initial vector in $J$. Now the
lemma follows because accessing the membership oracle of $J$ corresponds to
testing the existence of a ${\cal K}$-free $b^{\prime}$-factor in $G$. ∎

###  2.3 Boolean Edge-CSP

The _constraint satisfaction problem_ (_CSP_) is a fundamental topic in
theoretical computer science and has been intensively studied in various
fields (see, e.g., [38]). In this paper, we focus on the _Boolean edge-CSP_ ,
which is formulated as follows.

An instance of the Boolean CSP is a pair $(E,\mathcal{C})$, where $E$ is the
set of Boolean variables and $\mathcal{C}$ is that of constraints. A
constraint $C\in\mathcal{C}$ is a pair $(\sigma_{C},R_{C})$, where the _scope_
$\sigma_{C}\subseteq E$ is the set of the variables appearing in $C$ and the
_relation_ $R_{C}$ is a subset of $\\{0,1\\}^{\sigma_{C}}$. In general a scope
can be a multi-subset of $E$, but for notational simplicity we define a scope
as a subset of $E$. The objective of the Boolean CSP is to find a mapping
$f\colon E\to\\{0,1\\}$ such that $(f(e))_{e\in\sigma_{C}}\in R_{C}$ for each
constraint $C\in\mathcal{C}$.

A central topic of the CSP is the classification of the computational
complexity according to the relations that can appear in the constraints. Let
$\Gamma$ denote a set of relations, which is referred to as a _language_. The
problem of finding a solution to a Boolean CSP instance in which every
relation appearing in the constraints belongs to $\Gamma$ is denoted by
Boolean CSP$(\Gamma)$.

Schaefer [39] established a dichotomy theorem stating that Boolean
CSP$(\Gamma)$ is in class P if the language $\Gamma$ satisfies one of certain
six conditions, and is NP-hard otherwise. Bulatov [6] and Zhuk [48]
independently established its generalization, i.e., a dichotomy theorem for
the CSP over any finite domain, which affirmatively settled a long-standing
open question posed by Feder and Vardi [12].

By imposing a structural restriction on the set $\mathcal{C}$ of constraints,
we may obtain another class of the Boolean CSP which can be solved in
polynomial time. An example is the _Boolean edge-CSP_ , a class of the Boolean
CSP in which each variable appears in exactly two constraints. An instance
$(E,\mathcal{C})$ of the Boolean edge-CSP over the language $\Gamma$, denoted
by Boolean Edge-CSP($\Gamma$), is interpreted in terms of a graph $G=(V,E)$ in
the following way.

The variable set $E$ coincides with the edge set of the graph $G$. A mapping
$f\colon E\to\\{0,1\\}$ corresponds to a subset $M\subseteq E$ of edges
determined by $\chi_{M}(e)=f(e)$ for each $e\in E$. One constraint
$C=(\sigma_{C},R_{C})\in\mathcal{C}$ is described by one vertex $v\in V$ and
the set $\delta(v)$ of its incident edges: the scope $\sigma_{C}\subseteq E$
is the edge set $\delta(v)\subseteq E$; and the relation
$R_{C}\subseteq\\{0,1\\}^{\delta(v)}$ is described by an edge subset family
$\mathcal{F}_{v}\subseteq 2^{\delta(v)}$ by $R_{C}=\\{\chi_{F}\colon
F\in\mathcal{F}_{v}\\}$. Observe that each variable (edge) appears exactly in
two constraints (vertices).

##### Boolean Edge-CSP$(\Gamma)$

Given a graph $G=(V,E)$ and an edge subset family $\mathcal{F}_{v}\subseteq
2^{\delta(v)}$ whose corresponding relation $\\{\chi_{F}\colon
F\in\mathcal{F}_{v}\\}$ belongs to $\Gamma$ for each vertex $v\in V$, find an
edge set $M\subseteq E$ such that $\delta_{M}(v)\in{\cal F}_{v}$ for each
$v\in V$ (if one exists).

We remark that the relation $\mathcal{F}_{v}\subseteq 2^{\delta(v)}$ ($v\in
V$) is not given by the membership oracles but by the list of the edge
subsets, and hence the input size is $O(|V|+|E|+\sum_{v\in V}|{\cal F}_{v}|)$.

For a language $\Gamma$, if Boolean CSP($\Gamma$) belongs to class P, then so
is Boolean Edge-CSP$(\Gamma)$. We thus focus on Boolean languages $\Gamma$
such that Boolean CSP$(\Gamma)$ is NP-hard. Feder [11] showed that if $\Gamma$
contains the unary relations $\\{(0)\\}$ and $\\{(1)\\}$ and a relation that
is not a delta-matroid, then Boolean Edge-CSP$(\Gamma)$ is NP-hard. On the
other hand, Kazda, Kolmogorov, and Rolínek [18] proved that Boolean Edge-
CSP($\Gamma$) belongs to class P if every relation is an even delta-matroid.
Since an even delta-matroid can be identified with a constant-parity jump
system, with each coordinate in $\\{0,1\\}$, in what follows in this paper, we
refer to an even delta-matroid as a constant-parity jump system for the unity
of terminology. Let $\Gamma_{{\rm cp}\text{-}{\rm jump}}$ denote the set of
all constant-parity jump systems over the Boolean domain.

######  Theorem 2.6 (Kazda, Kolmogorov, and Rolínek [18]).

Boolean Edge-CSP$(\Gamma_{{\rm cp}\text{-}{\rm jump}})$ can be solved in
polynomial time.

##  3 Edge-Disjoint Forbidden Subgraphs

In this section, we consider the case when ${\cal K}$ is an edge-disjoint
family of $t$-regular complete partite subgraphs. We first give a polynomial-
time algorithm for ${\cal K}$-Free $b$-Factor Problem by reducing the problem
to Boolean Edge-CSP$(\Gamma_{{\rm cp}\text{-}{\rm jump}})$ in Theorem 3.1.
Then, by using this algorithm as a subroutine, we present a polynomial-time
algorithm for Maximum ${\cal K}$-Free $b$-Matching Problem (Theorem 3.4),
which implies Theorem 1.2. Finally, we prove the polynomial solvability under
the condition (RD) in Theorem 3.5, which will be used in the next section.

######  Theorem 3.1.

For a fixed positive integer $t$, ${\cal K}$-Free $b$-Factor Problem can be
solved in polynomial time if $b(v)\leq t$ for each $v\in V$ and all the
subgraphs in ${\cal K}$ are $t$-regular complete partite and pairwise edge-
disjoint.

###### Proof.

We prove the theorem by constructing a polynomial reduction to Boolean Edge-
CSP$(\Gamma_{{\rm cp}\text{-}{\rm jump}})$. Let $(G,b,\mathcal{K})$ be an
instance of ${\cal K}$-Free $b$-Factor Problem, where $G=(V,E)$,
$b\in\mathbb{Z}_{+}^{V}$, and $\cal K$ is a family of subgraphs in $G$.

Recall that an input of the Boolean edge-CSP consists of a graph and a
constraint on each vertex. Our input graph
$G^{\prime}=(V^{\prime},E^{\prime})$ of the Boolean edge-CSP is constructed as
follows (see also Figure 1):

Figure 1:  The graph on the left shows the edge set $E(K)$ of the $t$-regular
complete partite graph $K$ by the thick edges, while the thin edges belong to
$E\setminus E(K)$. In this example, $K$ is a $3$-regular complete bipartite
graph. The thick edges in the graph on the right depict the newly added three
parallel edges between $r_{K}$ and each vertex $v\in V(K)$.

  * •

Introduce a new vertex $r_{K}$ for each $K\in\mathcal{K}$, and define the
vertex set $V^{\prime}$ by

$\displaystyle V^{\prime}=V\cup\\{r_{K}\colon K\in{\cal K}\\}.$

  * •

For each $K\in\mathcal{K}$ and $v\in V(\mathcal{K})$, introduce new $t$
parallel edges between $r_{K}$ and $v$, and let $E^{\prime}_{v,K}$ denote the
set of these new $t$ parallel edges. Define the edge set $E^{\prime}$ by

$\displaystyle E^{\prime}=\left(E\cup\bigcup_{K\in\mathcal{K}}\bigcup_{v\in
V(K)}E^{\prime}_{v,K}\right)\setminus\bigcup_{K\in\mathcal{K}}E(K),$

Our input constraint $\mathcal{F}_{v}\subseteq 2^{\delta_{G^{\prime}}(v)}$
($v\in V^{\prime}$) is constructed as follows:

  * •

For each subgraph $K\in\mathcal{K}$, compute a set
$D_{K}\subseteq\mathbb{Z}_{+}^{V(K)}$ of the degree sequences in the $K$-free
$b$-matchings in $K$, i.e.,

$\displaystyle D_{K}$
$\displaystyle=\left\\{d_{F}\in\mathbb{Z}_{+}^{V(K)}\colon\mbox{$F$ is a
$K$-free $b$-matching in $K$}\right\\}$
$\displaystyle=\left\\{d_{F}\in\mathbb{Z}_{+}^{V(K)}\colon\mbox{$F$ is a
$b$-matching in $K$}\right\\}\setminus\\{(t,\dots,t)\\}.$

Then, for each vertex $v\in V^{\prime}$, define ${\cal F}_{v}\subseteq
2^{\delta_{G^{\prime}}(v)}$ by

$\displaystyle{\cal
F}_{v}=\begin{cases}\\{F^{\prime}\subseteq\delta_{G^{\prime}}(v)\colon|F^{\prime}|=b(v)\\}&\mbox{if
$v\in V$},\\\
\\{F^{\prime}\subseteq\delta_{G^{\prime}}(v)\colon\left(d_{F^{\prime}}(u)\right)_{u\in
V(K)}\in D_{K}\\}&\mbox{if $v=r_{K}$ for some $K\in{\cal K}$.}\end{cases}$ (1)

Note that each $D_{K}$ and each ${\cal F}_{v}$ can be computed efficiently in
a brute force way: $|V(K)|=O(t)$ and hence $D_{K}$ has $t^{O(t)}$ elements for
the fixed integer $t$; and ${\cal F}_{v}$ has a polynomial size.

Now we have constructed an instance of the Boolean edge-CSP consisting of
$G^{\prime}=(V^{\prime},E^{\prime})$ and $(\mathcal{F}_{v})_{v\in
V^{\prime}}$. We first show the following claim, which implies that this
instance actually belongs to Boolean Edge-CSP$(\Gamma_{{\rm cp}\text{-}{\rm
jump}})$.

######  Claim 3.2.

For each $v\in V^{\prime}$, the set
$\\{\chi_{F^{\prime}}\in\mathbb{Z}^{\delta_{G^{\prime}}(v)}\colon
F^{\prime}\in{\cal F}_{v}\\}$ of the characteristic vectors of the edge sets
in ${\cal F}_{v}$ is a constant-parity jump system.

###### Proof of Claim 3.2.

If $v\in V$, then the claim follows from the fact that ${\cal F}_{v}$ is the
basis family of a uniform matroid. Suppose that $v=r_{K}$ for $K\in{\cal K}$.
By applying Theorem 2.3 with $G=K$ and ${\cal K}=\\{K\\}$, we obtain that
$D_{K}$ is a constant-parity jump system. Now,
$\\{\chi_{F^{\prime}}\in\mathbb{Z}^{\delta_{G^{\prime}}(v)}\colon
F^{\prime}\in{\cal F}_{v}\\}$ is obtained from splitting $D_{K}$ to
$\bigcup_{u\in V(K)}E^{\prime}_{u,K}$ and then taking the intersection with a
box $\\{x\in\mathbb{R}^{\delta_{G^{\prime}}(v)}\colon{\bf 0}\leq x\leq{\bf
1}\\}$, and thus is a constant-parity jump system; see Section 2.2. ∎

It follows from Claim 3.2 and Theorem 2.6 that the instance
$(G^{\prime},(\mathcal{F}_{v})_{v\in V^{\prime}})$ belongs to Boolean Edge-
CSP$(\Gamma_{{\rm cp}\text{-}{\rm jump}})$ and can be solved in polynomial
time, respectively. Namely, we can find an edge set $M^{\prime}\subseteq
E^{\prime}$ such that

$\delta_{M^{\prime}}(v)\in{\cal F}_{v}\mbox{ for each $v\in V^{\prime}$}$ (2)

or conclude that such $M^{\prime}$ does not exist in polynomial time. In what
follows, we show that the existence of such an edge set $M^{\prime}\subseteq
E^{\prime}$ is equivalent to the existence of a ${\cal K}$-free $b$-factor in
the original graph $G$.

######  Claim 3.3.

The graph $G^{\prime}$ has an edge set $M^{\prime}\subseteq E^{\prime}$
satisfying (2) if and only if the original graph $G$ has a ${\cal K}$-free
$b$-factor $M\subseteq E$.

###### Proof of Claim 3.3.

We first show the sufficiency (“if” part). Let $M\subseteq E$ be a ${\cal
K}$-free $b$-factor in $G$. We construct an edge set $M^{\prime}\subseteq
E^{\prime}$ satisfying (2) in the following way. For each subgraph $K\in{\cal
K}$, let $F_{K}\subseteq\delta_{G^{\prime}}(r_{K})$ be an edge set in
$G^{\prime}$ composed of exactly $d_{M\cap E(K)}(u)$ parallel edges between
$u$ and $r_{K}$ for each vertex $u\in V(K)$. Note that such an edge set
$F_{K}$ must exist, because $M$ is a $b$-factor, $b(u)\leq t$, and
$G^{\prime}$ has $t$ parallel edges between $u$ and $r_{K}$. Now define
$M^{\prime}\subseteq E^{\prime}$ by

$M^{\prime}=\left(M\setminus\bigcup_{K\in{\cal
K}}E(K)\right)\cup\bigcup_{K\in{\cal K}}F_{K}.$

Here we show that this edge set $M^{\prime}$ satisfies (2). If $v\in V$, it
holds that $\delta_{M^{\prime}}(v)\in{\cal F}_{v}$, since
$|\delta_{M^{\prime}}(v)|=|\delta_{M}(v)|=b(v)$. Let $K\in{\cal K}$ and
$v=r_{K}$. The fact that $M$ is $\mathcal{K}$-free implies

$(d_{M\cap E(K)}(u))_{u\in V(K)}\in D_{K}.$

Since $d_{F_{K}}(u)=d_{M\cap E(K)}(u)$ for each vertex $u\in V(K)$, it follows
from the definition (1) of $\mathcal{F}_{r_{K}}$ that $F_{K}\in{\cal
F}_{r_{K}}$, and hence $\delta_{M^{\prime}}(r_{K})=F_{K}\in{\cal F}_{r_{K}}$.
We thus conclude that $M^{\prime}$ satisfies (2).

We next show the necessity (“only if” part). Let $M^{\prime}\subseteq
E^{\prime}$ be an edge set satisfying (2). We construct a $\mathcal{K}$-free
$b$-factor $M$ in $G$ in the following manner. For each subgraph $K\in{\cal
K}$, let $F_{K}:=\delta_{M^{\prime}}(r_{K})$. It follows from (2) that
$F_{K}\in{\cal F}_{r_{K}}$, namely, there exists a $b$-matching
$N_{K}\subsetneq E(K)$ such that $d_{N_{K}}(u)=d_{F_{K}}(u)$ for each vertex
$u\in V(K)$. Now define $M\subseteq E$ by

$M=\left(M^{\prime}\setminus\bigcup_{K\in{\cal
K}}F_{K}\right)\cup\bigcup_{K\in{\cal K}}N_{K}.$

We complete the proof by showing that $M$ is a ${\cal K}$-free $b$-factor in
$G$. Let $v\in V$ be an arbitrary vertex in $G$. Since
$d_{F_{K}}(u)=d_{N_{K}}(u)$ for each $K\in{\cal K}$ and each $u\in V(K)$, it
holds that $d_{M}(v)=d_{M^{\prime}}(v)=b(v)$, where the last equality follows
from $\delta_{M^{\prime}}(v)\in{\cal F}_{v}$. We thus have that $M$ is a
$b$-factor. Furthermore, since $N_{K}\subsetneq E(K)$ for each $K\in{\cal K}$,
we conclude that $M$ is ${\cal K}$-free. ∎

The proof of Claim 3.3 provides a polynomial-time construction of a ${\cal
K}$-free $b$-factor $M$ in $G$ from an edge set $M^{\prime}\subseteq
E^{\prime}$ satisfying (2). We thus conclude that the original instance
$(G,b,\mathcal{K})$ of ${\cal K}$-Free $b$-Factor Problem can be solved in
polynomial time. ∎

By using Theorem 3.1, we can give a polynomial-time algorithm for Maximum
${\cal K}$-Free $b$-Matching Problem under the same assumptions.

######  Theorem 3.4.

For a fixed positive integer $t$, Maximum ${\cal K}$-Free $b$-Matching Problem
can be solved in polynomial time if $b(v)\leq t$ for each $v\in V$ and all the
subgraphs in ${\cal K}$ are $t$-regular complete partite and pairwise edge-
disjoint.

###### Proof.

It follows from Theorem 2.3 that the set of the degree sequences of all ${\cal
K}$-free $b$-matchings in $G$ is a constant-parity jump system. Therefore, by
Lemma 2.5 and Theorem 3.1, we can solve Maximum ${\cal K}$-Free $b$-Matching
Problem in polynomial time. ∎

We remark that Theorem 1.2 is immediately derived from Theorem 3.4 by setting
$b(v)=t$ for every $v\in V$.

As described in Section 1, the edge-disjointness of the subgraphs in
$\mathcal{K}$ is relaxed to the condition (RD), which we restate here:

  1. (RD)

The subgraph family $\mathcal{K}$ is partitioned into subfamilies
$\mathcal{K}_{1},\dots,\mathcal{K}_{\ell}$ such that

     * •

for each subfamily $\mathcal{K}_{i}$ ($i=1,\ldots,\ell$), the number
$\left|\bigcup_{K\in\mathcal{K}_{i}}V(K)\right|$ of vertices is bounded by a
fixed constant, and

     * •

for distinct subfamilies $\mathcal{K}_{i}$ and $\mathcal{K}_{j}$
($i,j\in\\{1,\dots,\ell\\})$ and for each pair of subgraphs
$K\in\mathcal{K}_{i}$ and $K^{\prime}\in\mathcal{K}_{j}$, it holds that $K$
and $K^{\prime}$ are edge-disjoint.

######  Theorem 3.5.

For a fixed positive integer $t$, ${\cal K}$-Free $b$-Factor Problem and
Maximum ${\cal K}$-Free $b$-Matching Problem can be solved in polynomial time
if $b(v)\leq t$ for each $v\in V$ and $\mathcal{K}$ is a family of $t$-regular
complete partite subgraphs of $G$ and satisfies the condition (RD).

###### Proof.

It follows from Theorem 2.3 and Lemma 2.5 that Maximum ${\cal K}$-Free
$b$-Matching Problem can also be solved in polynomial time if ${\cal K}$-Free
$b$-Factor Problem is so. Hence, below we prove that ${\cal K}$-Free
$b$-Factor Problem can be solved in polynomial time in a similar way to
Theorem 3.1.

Let $(G,b,\mathcal{K})$ be an instance of ${\cal K}$-Free $b$-Factor Problem,
where $G=(V,E)$, $b\in\mathbb{Z}_{+}^{V}$, and $\cal K$ is a family of
subgraphs in $G$ satisfying the condition (RD). Let
$\mathcal{K}_{1},\dots,\mathcal{K}_{\ell}$ be the partition of $\mathcal{K}$
in the condition (RD).

For each $i\in\\{1,\dots,\ell\\}$, execute the following procedure. Let
$H_{i}$ be the graph defined as the union of all $K\in\mathcal{K}_{i}$, i.e.,

$\displaystyle
H_{i}:=\left(\bigcup_{K\in\mathcal{K}_{i}}V(K),\bigcup_{K\in\mathcal{K}_{i}}E(K)\right).$

Then,

  * •

add a new vertex $r_{i}$ and $t$ parallel edges between $r_{i}$ and $v$ for
each $v\in V(H_{i})$, and remove the original edges in $E(H_{i})$; and

  * •

compute a set $D_{H_{i}}\subseteq\mathbb{Z}_{+}^{V(H_{i})}$ of the degree
sequences in the $\mathcal{K}_{i}$-free $b$-matchings in $H_{i}$, i.e.,

$\displaystyle
D_{H_{i}}=\left\\{d_{F}\in\mathbb{Z}_{+}^{V(H_{i})}\colon\mbox{$F$ is a
$\mathcal{K}_{i}$-free $b$-matching in $H_{i}$}\right\\}.$

For each $i\in\\{1,\ldots,\ell\\}$, it follows from Theorem 2.3 that the set
$D_{H_{i}}$ is a constant-parity jump system. We also remark that $D_{H_{i}}$
can be computed efficiently in a brute force way, since $|V(H_{i})|$ and $t$
are bounded by a fixed constant.

Now, by the same argument as in the proof of Theorem 3.1, we can solve ${\cal
K}$-Free $b$-Factor Problem in polynomial-time with the aid of Theorem 2.6. ∎

We conclude this section by showing that a subgraph family $\mathcal{K}$ with
a certain laminar structure described below satisfies the condition (RD).

######  Corollary 3.6.

For a fixed positive integer $t$, ${\cal K}$-Free $b$-Factor Problem and
Maximum ${\cal K}$-Free $b$-Matching Problem can be solved in polynomial time
if $b(v)\leq t$ for each $v\in V$ and $\mathcal{K}$ is a family of $t$-regular
complete partite subgraphs of $G$ satisfying $E(K)\cap
E(K^{\prime})=\emptyset$, $V(K)\subseteq V(K^{\prime})$, or $V(K)\supseteq
V(K^{\prime})$ for each pair of subgraphs $K,K^{\prime}\in\mathcal{K}$.

###### Proof.

We construct a partition of $\mathcal{K}$ certifying that $\mathcal{K}$
satisfies the condition (RD). Then the corollary immediately follows from
Theorem 3.5.

Let $\mathcal{X}^{*}$ be the family of all inclusionwise maximal sets in
$\\{V(K)\colon K\in\mathcal{K}\\}$. For each vertex set $X\in\mathcal{X}^{*}$,
define a subfamily $\mathcal{K}_{X}$ of $\mathcal{K}$ by
$\mathcal{K}_{X}:=\\{K\in\mathcal{K}\colon V(K)\subseteq X\\}$. It suffices to
show that $E(K)\cap E(K^{\prime})=\emptyset$ for each pair of distinct vertex
sets $X,X^{\prime}\in\mathcal{X}^{*}$ and for each pair of subgraphs
$K\in\mathcal{K}_{X}$ and $K^{\prime}\in\mathcal{K}_{X^{\prime}}$; this
implies that $\mathcal{K}_{X}$ ($X\in\mathcal{X}^{*}$) form a partition of
$\mathcal{K}$ satisfying the condition (RD).

Suppose to the contrary that $E(K)\cap E(K^{\prime})\neq\emptyset$ for some
distinct vertex sets $X,X^{\prime}\in\mathcal{X}^{*}$ and for some subgraphs
$K\in\mathcal{K}_{X}$ and $K^{\prime}\in\mathcal{K}_{X^{\prime}}$. It follows
from the assumption of $\mathcal{K}$ that $V(K)\subseteq V(K^{\prime})$ or
$V(K)\supseteq V(K^{\prime})$. Without loss of generality, assume
$V(K)\subseteq V(K^{\prime})$. Let $K_{X}\in\mathcal{K}_{X}$ (resp.
$K_{X^{\prime}}\in\mathcal{K}_{X^{\prime}}$) be a $t$-regular complete partite
graph attaining $V(K_{X})=X$ (resp. $V(K_{X^{\prime}})=X^{\prime}$). It
follows from the maximality of $X$ and $X^{\prime}$ that
$V(K_{X})\not\subseteq V(K_{X^{\prime}})$ and $V(K_{X})\not\supseteq
V(K_{X^{\prime}})$.

In the following, we prove that $E(K_{X})\cap E(K_{X^{\prime}})\neq\emptyset$,
which contradicts the assumption of $\mathcal{K}$. Define a vertex set $Y$ by
$Y:=V(K_{X})\cap V(K_{X^{\prime}})$. It is derived from $V(K)\subseteq
X=V(K_{X})$ and $V(K)\subseteq V(K^{\prime})\subseteq
X^{\prime}=V(K_{X^{\prime}})$ that $V(K)\subseteq Y$. It then follows that
$|Y|\geq t+1$, which implies that both of the induced subgraphs $K_{X}[Y]$ and
$K_{X^{\prime}}[Y]$ are complete partite graphs having at least two color
classes. Since the complement of $K_{X}[Y]$ is the disjoint union of (at least
two) complete graphs, it is disconnected. On the other hand,
$K_{X^{\prime}}[Y]$ is connected. Hence we have $E(K_{X}[Y])\cap
E(K_{X^{\prime}}[Y])\neq\emptyset$, implying that $E(K_{X})\cap
E(K_{X^{\prime}})\neq\emptyset$. ∎

##  4 Degree Bounded Graphs

In this section, we consider the case where the maximum degree of $G$ is at
most $2t-1$.

######  Theorem 4.1.

For a fixed positive integer $t$, ${\cal K}$-Free $b$-Factor Problem can be
solved in polynomial time if the maximum degree of $G$ is at most $2t-1$,
$b(v)\leq t$ for each $v\in V$, and all the subgraphs in ${\cal K}$ are
$t$-regular complete partite.

###### Proof.

If $t=1$, then the problem is trivial, because the maximum degree is one and a
$t$-regular complete partite subgraph must be composed of a single edge.
Therefore, it suffices to consider the case where $t\geq 2$.

Without loss of generality, we may assume that each subgraph $K\in{\cal K}$
satisfies

$b(v)=t\mbox{ for each vertex }v\in V(K),$ (3)

since otherwise we can remove $K$ from ${\cal K}$.

Define a vertex subset family $\mathcal{X}\subseteq 2^{V}$ by ${\cal
X}=\\{V(K)\colon K\in{\cal K}\\}$. Construct a subfamily ${\cal
X}^{*}\subseteq{\cal X}$ of disjoint vertex subsets in $\mathcal{X}$ in the
following manner: start with ${\cal X}^{*}=\emptyset$; and while there exists
a set in ${\cal X}$ disjoint from every set in ${\cal X}^{*}$, add an
inclusionwise maximal one to ${\cal X}^{*}$. We denote ${\cal
X}^{*}=\\{X_{1},X_{2},\dots,X_{\ell}\\}$. It follows from the construction
that ${\cal X}^{*}\subseteq{\cal X}$ satisfies the following property:

for each $X\in{\cal X}\setminus{\cal X}^{*}$, there exists
$X_{i}\in\mathcal{X}^{*}$ such that $X\cap X_{i}\neq\emptyset$ and
$X_{i}\not\subseteq X$. (4)

For each $X_{i}\in\mathcal{X}^{*}$, let ${\cal K}_{i}=\\{K\in{\cal K}\colon
V(K)\subseteq X_{i}\\}$ and let $H_{i}$ be the union of all subgraphs in
${\cal K}_{i}$, i.e.,

$H_{i}=\left(X_{i},\bigcup_{K\in{\cal K}_{i}}E(K)\right).$

Let ${\cal K}^{*}=\bigcup_{i=1}^{\ell}{\cal K}_{i}$. Note that ${\cal
K}_{1},\dots,{\cal K}_{\ell}$ form a partition of $\mathcal{K}^{*}$, and they
satisfy the condition (RD).

By using Theorem 3.5, in polynomial time, we can find a ${\cal K}^{*}$-free
$b$-factor $M$ in $G$ or conclude that $G$ has no ${\cal K}^{*}$-free
$b$-factor. In the latter case, we can conclude that $G$ has no ${\cal
K}$-free $b$-factor, because $\mathcal{K}^{*}$ is a subfamily of
$\mathcal{K}$. In the former case, we transform $M$ into a ${\cal K}$-free
$b$-factor as shown in the following claim.

######  Claim 4.2.

Given a ${\cal K}^{*}$-free $b$-factor $M$ in $G$, we can construct a ${\cal
K}$-free $b$-factor in polynomial time.

###### Proof of 4.2.

For a $b$-factor $M$ in $G$, define a subgraph family $\mathcal{K}(M)$ by

$\mathcal{K}(M)=\\{K\in{\cal K}\colon E(K)\subseteq M\\},$

the set of forbidden subgraphs included in $M$. Obviously, $M$ is ${\cal
K}$-free if and only if $\mathcal{K}(M)=\emptyset$. In what follows, given a
$\mathcal{K}^{*}$-free $b$-factor $M$, we modify $M$ so that $\mathcal{K}(M)$
becomes smaller.

Let $M$ be a ${\cal K}^{*}$-free $b$-factor and suppose that
$\mathcal{K}(M)\neq\emptyset$. Then, there exists a subgraph $K\in{\cal
K}\setminus{\cal K}^{*}$ such that $K\in\mathcal{K}(M)$, i.e., $E(K)\subseteq
M$. It follows from $K\in{\cal K}\setminus{\cal K}^{*}$ that $V(K)\in{\cal
X}\setminus{\cal X}^{*}$. Then, (4) implies that there exists
$X_{i}\in\mathcal{X}^{*}$ such that

$V(K)\cap X_{i}\neq\emptyset\quad\mbox{and}\quad X_{i}\not\subseteq V(K).$

It holds that $X_{i}=V(K^{*})$ for some $K^{*}\in{\cal K}_{i}$, which follows
from the construction of ${\cal X}^{*}$ and the definition of ${\cal K}_{i}$.
We thus obtain

$V(K)\cap V(K^{*})\neq\emptyset\quad\mbox{and}\quad V(K^{*})\not\subseteq
V(K).$

Take a vertex $u$ in $V(K)\cap V(K^{*})$. Since
$|\delta_{K}(u)|=|\delta_{K^{*}}(u)|=t$ and $|\delta_{G}(u)|\leq 2t-1$, there
exists an edge $e\in\delta_{K}(u)\cap\delta_{K^{*}}(u)$, in particular $e\in
E(K)\cap E(K^{*})$. We denote $e=uu^{\prime}$. Note that $e\in M$ since
$E(K)\subseteq M$.

Since $V(K^{*})\not\subseteq V(K)$, there exists a vertex $v\in
V(K^{*})\setminus V(K)$. From (3) and $K^{*}\in\mathcal{K}$, we obtain
$|\delta_{M}(v)|=b(v)=t$. It then follows from $|\delta_{G}(v)|\leq 2t-1$ and
$|\delta_{K^{*}}(v)|=t$ that
$\delta_{M}(v)\cap\delta_{K^{*}}(v)\neq\emptyset$, that is, there exists an
edge $e^{*}\in\delta_{K^{*}}(v)$ contained in $M$. We denote
$e^{*}=vv^{\prime}$. Since $K$ is a connected component of the subgraph
induced by $M$ (see Remark 2.2), it holds that $v^{\prime}\in
V(K^{*})\setminus V(K)$; see Figure 2.

Figure 2: All of the edges are in $E(K^{*})$ and, particularly, all of the
solid edges are in $M$. The solid bold edge is in $E(K^{*})\cap E(K)$ and the
other thin edges are in $E(K^{*})\setminus E(K)$.

Since $e,e^{*}\in E(K^{*})$ and $K^{*}$ is a complete partite graph, $u$ and
$u^{\prime}$ are contained in different color classes of $K^{*}$, and so are
$v$ and $v^{\prime}$. This shows that $K^{*}$ contains two edges: $uv$ and
$u^{\prime}v^{\prime}$; or $uv^{\prime}$ and $u^{\prime}v$. By symmetry,
assume that $f=uv$ and $f^{\prime}=u^{\prime}v^{\prime}$ are contained in
$K^{*}$; see Figure 2 again. Note that $f$ and $f^{\prime}$ are not contained
in $M$, because $\delta_{M}(u)=\delta_{K}(u)$ and
$\delta_{M}(u^{\prime})=\delta_{K}(u^{\prime})$ hold.

Define $M^{\prime}=(M\setminus\\{e,e^{*}\\})\cup\\{f,f^{\prime}\\}$, which is
also a $b$-factor. In what follows, we prove that $M^{\prime}$ is the desired
$\mathcal{K}^{*}$-free $b$-factor, i.e.,
$\mathcal{K}(M^{\prime})\subsetneq\mathcal{K}(M)$. Since
$K\not\in\mathcal{K}(M^{\prime})$, it suffices to show that
$\mathcal{K}(M^{\prime})\subseteq\mathcal{K}(M)$.

Assume to the contrary that there exists a subgraph
$K^{\prime}\in\mathcal{K}(M^{\prime})\setminus\mathcal{K}(M)$. Then,
$K^{\prime}$ must contain at least one of $f$ and $f^{\prime}$, and without
loss of generality assume that $f\in E(K^{\prime})$. Since $K-e$ is connected
by $t\geq 2$ and $M^{\prime}$ contains $(E(K)\setminus\\{e\\})\cup\\{f\\}$ by
$e^{*}\notin E(K)$, it follows from Remark 2.2 that $V(K)\cup\\{v\\}$ is
contained in $K^{\prime}$, in particular $u,u^{\prime},v\in V(K^{\prime})$.

Since all the edges in $\delta_{M}(u^{\prime})$ are contained in $K$ and
$v\not\in V(K)$, $M$ has no edge connecting $u^{\prime}$ and $v$, and neither
does $M^{\prime}$. It then follows from
$K^{\prime}\in\mathcal{K}(M^{\prime})$, i.e., $E(K^{\prime})\subseteq
M^{\prime}$, that $u^{\prime}v\not\in E(K^{\prime})$. Since $e$ is the only
edge in $M$ connecting $u$ and $u^{\prime}$, we have $uu^{\prime}\not\in
M^{\prime}$, which implies that $uu^{\prime}\not\in E(K^{\prime})$. It now
follows from $u^{\prime}v,uu^{\prime}\not\in E(K^{\prime})$ that
$u,u^{\prime}$ and $v$ are contained in the same color class of $K^{\prime}$,
since $K^{\prime}$ is complete partite. This contradicts the fact that
$K^{\prime}$ contains $f=uv$, and thus we conclude that
$\mathcal{K}(M^{\prime})\subsetneq\mathcal{K}(M)$.

By repeating the above procedure, we obtain a $b$-factor $M$ with
$\mathcal{K}(M)=\emptyset$, i.e., $M$ is $\mathcal{K}$-free. It is
straightforward to see that this procedure can be executed in polynomial time,
which completes the proof. ∎

Therefore, we conclude that ${\cal K}$-Free $b$-Factor Problem can be solved
in polynomial time. ∎

From Theorem 4.1, we can derive the following theorem by applying the same
argument as Theorem 3.4.

######  Theorem 4.3.

For a fixed positive integer $t$, Maximum ${\cal K}$-Free $b$-Matching Problem
can be solved in polynomial time if the maximum degree of $G$ is at most
$2t-1$, $b(v)\leq t$ for each $v\in V$, and all the subgraphs in ${\cal K}$
are $t$-regular complete partite.

From Theorem 4.3, we immediately obtain Theorem 1.3 by setting $b(v)=t$ for
every $v\in V$.

##  5 Generalization: Forbidden Degree Sequences

In this section, we extend Theorems 3.1, 3.4, and 3.5 so that the forbidden
structure is not an edge-disjoint family of $t$-regular subgraphs but that of
the subgraphs with specified degree sequences. A similar problem of _general
factors_ is of classical and recent interest [7, 10, 24, 29, 40, 41].

Let $G=(V,E)$ be a graph and $\mathcal{H}$ be a family of subgraphs of $G$.
Each subgraph $H\in\mathcal{H}$ is associated with a set of degree sequences
$\overline{D}_{H}\subseteq\mathbb{Z}_{+}^{V(H)}$. Define an edge subset family
$\mathcal{F}_{H}\subseteq 2^{E(H)}$ by

$\mathcal{F}_{H}=\\{F\subseteq E(H)\colon d_{F}\in\overline{D}_{H}\\},$

and subgraph families

$\displaystyle{\cal K}_{H}=\\{(V(H),F)\colon F\in\mathcal{F}_{H}\\},\quad{\cal
K}_{\cal H}=\bigcup_{H\in{\cal H}}{\cal K}_{H}.$

We are interested in $\mathcal{K}_{\mathcal{H}}$-free $b$-matchings. Namely,
for a subgraph $H\in\mathcal{H}$, $\overline{D}_{H}$ represents the set of
forbidden degree sequences on $V(H)$, and $\mathcal{K}_{H}$ represents the
family of the forbidden subgraphs of $H$, i.e., those attaining the degree
sequences in $\overline{D}_{H}$.

We now extend Theorems 3.1, 3.4, and 3.5 in the following way.

######  Theorem 5.1.

${\cal K}$-Free $b$-Factor Problem and Maximum ${\cal K}$-Free $b$-Matching
Problem can be solved in polynomial time if the following conditions are
satisfied:

  1. 1.

$b(v)$ is bounded by a fixed constant for each $v\in V$; and

  2. 2.

${\cal K}={\cal K}_{\cal H}$ for an edge-disjoint family ${\cal H}$ of
subgraphs of $G$ such that, for each $H\in{\cal H}$,

    1. (a)

$|V(H)|$ is bounded by a fixed constant, and

    2. (b)

$D_{H}:=\\{d_{F}\colon\mbox{$F$ is a $b$-matching in
$H$}\\}\setminus\overline{D}_{H}$ is a constant-parity jump system.

###### Proof.

Suppose that the conditions 1 and 2 are satisfied. By following the proof of
Theorem 3.1, we see that ${\cal K}$-Free $b$-Factor Problem can be solved in
polynomial time.

We now prove that Maximum ${\cal K}$-Free $b$-Matching Problem can be solved
in polynomial time. Define $J\subseteq\mathbb{Z}_{+}^{V}$ as the set of the
degree sequences of all ${\cal K}$-free $b$-matchings in $G$. In order to
apply Lemma 2.5, we show that $J$ is a constant-parity jump system.

Define $J_{0}\subseteq\mathbb{Z}_{+}^{V}$ by

$J_{0}=\left\\{d_{F}\in\mathbb{Z}_{+}^{V}\colon F\subseteq
E\setminus\bigcup_{H\in{\cal H}}E(H)\right\\},$

which is a constant-parity jump system. For each subgraph $H\in{\cal H}$,
regard $D_{H}\subseteq\mathbb{Z}_{+}^{V(H)}$ as a subset of
$\mathbb{Z}_{+}^{V}$ by setting $x(v)=0$ for each $x\in D_{H}$ and $v\in
V\setminus V(H)$. Then, $J$ is obtained from $J_{0}$ by taking the Minkowski
sum with $D_{H}$ for all $H\in{\cal H}$, and then taking the intersection with
a box $\\{x\in\mathbb{R}^{V}\colon{\bf 0}\leq x\leq b\\}$. This shows that $J$
is a constant-parity jump system.

Thus, by applying Lemma 2.5, we conclude that Maximum ${\cal K}$-Free
$b$-Matching Problem can be solved in polynomial time. ∎

Observe that Theorems 3.1 and 3.4 are exactly special cases of Theorem 5.1,
where $H$ is a $t$-regular complete partite graph and
$\overline{D}_{H}=\\{(t,t,\dots,t)\\}$ for each $H\in\mathcal{H}$. Observe
also that Theorem 3.5 is a special case of Theorem 5.1, where
$\mathcal{H}=\\{H_{1},\dots,H_{\ell}\\}$.

We conclude this paper with a few applications of Theorem 5.1.

######  Example 5.2.

Suppose that each subgraph $H\in{\cal H}$ is obtained from $K_{5}$ by removing
a matching of size two (which is unique up to isomorphism). Let
$\overline{D}_{H}=\\{(2,\dots,2)\\}$ for each $H\in{\cal H}$ and let $b(v)=2$
for each $v\in V$. It then follows that $D_{H}=\\{d_{F}\colon\mbox{$F$ is a
$2$-matching in $H$}\\}\setminus\\{(2,\dots,2)\\}$ is a constant-parity jump
system. It also follows that the subgraph family ${\cal K}_{H}$ consists of
cycles of length five in $H$. Now Theorem 5.1 shows that we can find a maximum
$2$-matching which does not contain the cycles of length five in $H$ for each
subgraph $H\in\mathcal{H}$. This is an interesting contrast to the fact that
finding a maximum $C_{5}$-free $2$-matching in graphs is NP-hard (see [8]). To
the best of our knowledge, this is the first polynomially solvable class of
the restricted $2$-matching problem excluding cycles of length five.

######  Example 5.3.

Suppose that each subgraph $H\in{\cal H}$ is obtained from $K_{3,3}$ by
removing an edge (which is unique up to isomorphism). Let
$\overline{D}_{H}=\\{(2,\dots,2)\\}$ for each $H\in{\cal H}$ and let $b(v)=2$
for each $v\in V$. It then follows that $D_{H}=\\{d_{F}\colon\mbox{$F$ is a
$2$-matching in $H$}\\}\setminus\\{(2,\dots,2)\\}$ is a constant-parity jump
system. It also follows that the subgraph family ${\cal K}_{H}$ consists of
the cycles of length six in $H$. Now Theorem 5.1 shows that we can find a
maximum $2$-matching which does not contain the cycles of length six in $H$
for each subgraph $H\in\mathcal{H}$. This is an interesting contrast to the
fact that finding a maximum $C_{6}$-free $2$-matching in bipartite graphs is
NP-hard (Geelen, see [13, 20]). Note also that such a graph $H$ (i.e.,
$K_{3,3}-e$) is discussed by Takazawa [46] as an example of so called
_Hamilton-laceable graphs_ [43].

## Acknowledgments

The first author was supported by JSPS KAKENHI Grant Numbers JP20K23323,
JP20H05795, JP22K17854. The second author was supported by JSPS KAKENHI Grant
Numbers JP20K11692, JP20H05795, JP22H05001. The third author was supported by
JSPS KAKENHI Grant Number JP20K11699.

## References

  * [1] K. Ando, S. Fujishige, and T. Naitoh.  A greedy algorithm for minimizing a separable convex function over a finite jump system.  Journal of the Operations Research Society of Japan, 38(3):362–375, 1995.
  * [2] M. A. Babenko.  Improved algorithms for even factors and square-free simple $b$-matchings.  Algorithmica, 64:362–383, 2012.
  * [3] K. Bérczi and Y. Kobayashi.  An algorithm for $(n-3)$-connectivity augmentation problem: Jump system approach.  Journal of Combinatorial Theory, Series B, 102:565–587, 2012.
  * [4] K. Bérczi and L. A. Végh.  Restricted $b$-matchings in degree-bounded graphs.  In F. Eisenbrand and B. Shepherd, editors, Integer Programming and Combinatorial Optimization: Proceedings of the 14th IPCO, LNCS 6080, pages 43–56. Springer, 2010.
  * [5] A. Bouchet and W. H. Cunningham.  Delta-matroids, jump systems, and bisubmodular polyhedra.  SIAM Journal on Discrete Mathematics, 8:17–32, 1995.
  * [6] A. A. Bulatov.  A dichotomy theorem for nonuniform CSPs.  In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, pages 319–330, 2017.
  * [7] G. Cornuéjols.  General factors of graphs.  Journal of Combinatorial Theory, Series B, 45(2):185–198, 1988\.
  * [8] G. Cornuéjols and W. Pulleyblank.  A matching problem with side conditions.  Discrete Mathematics, 29:135–159, 1980.
  * [9] W. H. Cunningham.  Matching, matroids, and extensions.  Mathematical Programming, 91(3):515–542, 2002.
  * [10] S. Dudycz and K. E. Paluch.  Optimal general matchings.  In Graph-Theoretic Concepts in Computer Science, LNCS 11159, pages 176–189, 2018.  ArXiv version is available at http://arxiv.org/abs/1706.07418.
  * [11] T. Feder.  Fanout limitations on constraint systems.  Theoretical Computer Science, 255:281–293, 2001.
  * [12] T. Feder and M. Y. Vardi.  The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory.  SIAM Journal on Computing, 28(1):57–104, 1998.
  * [13] A. Frank.  Restricted $t$-matchings in bipartite graphs.  Discrete Applied Mathematics, 131:337–346, 2003.
  * [14] D. Hartvigsen.  Extensions of Matching Theory.  PhD thesis, Carnegie Mellon University, 1984.
  * [15] D. Hartvigsen.  Finding maximum square-free 2-matchings in bipartite graphs.  Journal of Combinatorial Theory, Series B, 96:693–705, 2006\.
  * [16] D. Hartvigsen and Y. Li.  Maximum cardinality simple $2$-matchings in subcubic graphs.  SIAM Journal on Optimization, 21:1027–1045, 2011.
  * [17] D. Hartvigsen and Y. Li.  Polyhedron of triangle-free simple $2$-matchings in subcubic graphs.  Mathematical Programming, 138:43–82, 2013.
  * [18] A. Kazda, V. Kolmogorov, and M. Rolínek.  Even delta-matroids and the complexity of planar boolean CSPs.  ACM Transactions on Algorithms, 15(2):22:1–22:33, 2019.
  * [19] Z. Király.  $C_{4}$-free $2$-factors in bipartite graphs.  Technical Report TR-2001-13, Egerváry Research Group, 1999.  www.cs.elte.hu/egres.
  * [20] Z. Király.  Restricted $t$-matchings in bipartite graphs.  Technical Report QP-2009-04, Egerváry Research Group, 2009.  www.cs.elte.hu/egres.
  * [21] Y. Kobayashi.  A simple algorithm for finding a maximum triangle-free $2$-matching in subcubic graphs.  Discrete Optimization, 7:197–202, 2010.
  * [22] Y. Kobayashi.  Triangle-free $2$-matchings and M-concave functions on jump systems.  Discrete Applied Mathematics, 175:35–42, 2014.
  * [23] Y. Kobayashi.  Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles.  Mathematical Programming, 192(1):675–702, 2022.
  * [24] Y. Kobayashi.  Optimal general factor problem and jump system intersection.  In A. Del Pia and V. Kaibel, editors, Integer Programming and Combinatorial Optimization, pages 291–305. Springer, 2023.
  * [25] Y. Kobayashi, K. Murota, and K. Tanaka.  Operations on M-convex functions on jump systems.  SIAM Journal on Discrete Mathematics, 21(1):107–129, 2007.
  * [26] Y. Kobayashi and T. Noguchi.  An approximation algorithm for two-edge-connected subgraph problem via triangle-free two-edge-cover.  CoRR, abs/2304.13228, 2023.
  * [27] Y. Kobayashi, J. Szabó, and K. Takazawa.  A proof of Cunningham’s conjecture on restricted subgraphs and jump systems.  Journal of Combinatorial Theory, Series B, 102:948–966, 2012.
  * [28] Y. Kobayashi and X. Yin.  An algorithm for finding a maximum $t$-matching excluding complete partite subgraphs.  Discrete Optimization, 9:98–108, 2012.
  * [29] L. Lovász.  Antifactors of graphs.  Periodica Mathematica Hungarica, 4:121–123, 1973.
  * [30] L. Lovász.  The membership problem in jump systems.  Journal of Combinatorial Theory, Series B, 70(1):45–66, 1997.
  * [31] M. Makai.  On maximum cost $K_{t,t}$-free $t$-matchings of bipartite graphs.  SIAM Journal on Discrete Mathematics, 21:349–360, 2007.
  * [32] K. Murota.  M-convex functions on jump systems: A general framework for minsquare graph factor problem.  SIAM Journal on Discrete Mathematics, 20(1):213–226, 2006.
  * [33] K. Murota.  On basic operations related to network induction of discrete convex functions.  Optimization Methods and Software, 36(2-3):519–559, 2021.
  * [34] Y. Nam.  Matching Theory: Subgraphs with Degree Constraints and Other Properties.  PhD thesis, University of British Columbia, 1994.
  * [35] K. Paluch and M. Wasylkiewicz.  Restricted $t$-matchings via half-edges.  In P. Mutzel, R. Pagh, and G. Herman, editors, 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), volume 204 of LIPIcs, pages 73:1–73:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [36] K. Paluch and M. Wasylkiewicz.  A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs - via half-edges.  Information Processing Letters, 171:106146, 2021.
  * [37] G. Pap.  Combinatorial algorithms for matchings, even factors and square-free 2-factors.  Mathematical Programming, 110:57–69, 2007.
  * [38] F. Rossi, P. van Beek, and T. Walsh, editors.  Handbook of Constraint Programming, volume 2 of Foundations of Artificial Intelligence.  Elsevier, 2006.
  * [39] T. J. Schaefer.  The complexity of satisfiability problems.  In Proceedings of the tenth annual ACM Symposium on Theory of Computing, pages 216–226, 1978.
  * [40] A. Sebő.  General antifactors of graphs.  Journal of Combinatorial Theory, Series B, 58(2):174–184, 1993\.
  * [41] S. Shao and S. Živný.  A strongly polynomial-time algorithm for weighted general factors with three feasible degrees.  CoRR, abs/2301.11761, 2023.
  * [42] A. Shioura and K. Tanaka.  Polynomial-time algorithms for linear and convex optimization on jump systems.  SIAM Journal on Discrete Mathematics, 21(2):504–522, 2007.
  * [43] G. J. Simmons.  Almost all $n$-dimensional rectangular lattices are Hamilton laceable.  In Proceedings of the 9th Southeastern Conference on Combinatorics, Graph Theory, and Computing, pages 649–661. Congressus Numerantium 21, 1978.
  * [44] K. Takazawa.  A weighted $K_{t,t}$-free $t$-factor algorithm for bipartite graphs.  Mathematics of Operations Research, 34:351–362, 2009.
  * [45] K. Takazawa.  Decomposition theorems for square-free 2-matchings in bipartite graphs.  Discrete Applied Mathematics, 233:215–223, 2017.
  * [46] K. Takazawa.  Finding a maximum $2$-matching excluding prescribed cycles in bipartite graphs.  Discrete Optimization, 26:26–40, 2017.
  * [47] K. Takazawa.  Excluded $t$-factors in bipartite graphs: Unified framework for nonbipartite matchings, restricted 2-matchings, and matroids.  SIAM Journal on Discrete Mathematics, 36(1):702–727, 2022.
  * [48] D. Zhuk.  A proof of the CSP dichotomy conjecture.  Journal of the ACM, 67(5):30:1–30:78, 2020.