Efficient Enumeration of Induced Matchings in a Graph
without Cycles with Length Four
Kazuhiro Kurita1 , Kunihiro Wasa2 , Takeaki Uno2 , and Hiroki Arimura1

arXiv:1707.02740v1 [] 10 Jul 2017

1

IST, Hokkaido University, Sapporo, Japan, {k-kurita,
arim}@ist.hokudai.ac.jp
2
National Institute of Informatics, Tokyo, Japan, {wasa, uno}@nii.ac.jp
July 11, 2017
Abstract
We address the induced matching enumeration problem. An edge set M is an induced
matching of a graph G = (V, E). The enumeration of matchings are widely studied in literature, but the induced matching has not been paid much attention. A straightforward
algorithm takes O (|V |) time for each solution, that is coming from the time to generate a
subproblem. We investigated local structures that enables us to generate subproblems in
short time, and proved that the time complexity will be O (1) if the input graph is C4 -free.
A C4 -free graph is a graph any whose subgraph is not a cycle of length four. Finally, we
show the fixed parameter tractability of counting induced matchings for graphs with bounded
tree-width and planar graphs.

1

Introduction

An enumeration problem is to output all solutions to a given problem without duplication. Enumeration problems and their algorithms have been continuously studied in literature, and recently
the studies have got more active from the expansion of the applications, such as data mining, network analysis and computational proofs in mathematics. According to the increase of the activity,
several problems that solved in the past were revisited such as paths, cycles, and trees, and several
structures began to be studied [7, 9, 20, 21]. In this paper, we also revisit an old fashioned problem
of enumerating matchings, but consider its induced version that has not been paid attention much.
The efficiency of enumeration algorithm is often evaluated by output-polynomiality [22]. An
algorithm is said to be output-polynomial time if its total running time is bounded by poly(N, M ),
where N is the input size, M is the output size and poly(N, M ) is a polynomial function on N
and M . The delay of an enumeration algorithm is the maximum computation time between the
output solution and the next solution and time after the last solution until the termination of
the algorithm. An algorithm is polynomial delay if its delay is bounded by polynomial in N . In
particular, we say an algorithm is said to runs in O(poly(N )) time for each if the algorithm runs
in time linear in M poly(N ).
In this paper, we consider the enumeration problem for induced matchings in the given graph
(abbreviated as EIM ). An induced matching of a graph is an edge set such that the endpoints of
any two edges in the set are not adjacent to each other, i.e., the graph induced by the endpoints
of the edge set forms a matching. Uno [21] showed that matchings can be enumerated in a general
1

graph in constant amortized time by using amortization technique, called Push out, to distribute
the cost of each iteration to many descendants. We can also consider a straightforward binary
partition
 algorithm (branch and bound algorithm) for induced matching enumeration that runs in
O ∆2 time per solution, where ∆ is the maximum degree in an input graph. The structure of the
recursion is quite different from the ordinal matching enumeration, thus a direct application of the
technique described in [21] does not work. The push out technique and the other amortization
require some conditions, but it is not easy to develop algorithms satisfying the conditions. The
existence of more efficient algorithms is still open.
In this kind of low-degree polynomial time enumeration algorithm, the most time consuming
part is often typically the generation of the child problems. Particularly, we spend much time
when the local structure of the problem is complicated around the pivot vertex or edge, that is
to be fixed or to be removed from the problem. If the structure is simple, the child problem
generation can be done in short time. For example, if the graph is a tree, there is no cycle around
a vertex, thus we do not have to think about unification of multiple edges when we shrink an edge.
In this paper, we consider C4 -free graphs, and propose an algorithm runs in constant time for
each, where C4 -free graphs are graphs that have no cycles of length equal to four. In an ordinal
binary partition algorithm for induced matching enumeration, we choose an edge e and enumerate
induced matchings including e. This is done by enumerating all induced matching included the
graph obtained
 by removing e, edges adjacent to e, and edges adjacent to edges adjacent to e. This
takes O ∆2 time and this is the bottle neck of the algorithm. We investigated the C4 -free graphs,
and could find that the structural property of C4 -free graphs makes the process of generating the
subproblems light. We introduced new way of branching the problem, so that in each iteration we
select a vertex v with the maximum degree, and partition the problem into ∆ subproblems. The
property together with this branching method lighten the computation of subproblems, and the
computation time of an iteration is bounded by the number of its descendants. This enables us to
use amortization analysis, and can obtain the result.
The organization of the paper is as follows. We show in Sec. 3 that induced matchings are
enumerable in constant amortized time per solution for C4 -free graphs. In Sec. 4, we show that
counting all induced matchings can be solvable in FPT linear time for graphs with bounded degree,
bounded tree-width, and planar graphs by using the results of [1, 11]. These results seem to show
for the first time the complexities of counting and enumeration problems for induced matchings.

1.1

Related works

In Table 1, we show the summary of related work and our results on decision, counting, and enumeration problems for small subgraphs in a graph. The decision problem for matching (maximum
matching, MM) has been extensively studied for more than 50 years [7, 14]. The decision problem
can be solved in polynomial time for matchings (See [7,14]), while the problem (MIM) for induced
matchings is known to be NP-complete [19]. The latter is still NP-hard for graphs with bounded
degree, bipartite graphs, C4 -free, line graphs, and planar graphs [2, 3, 15]. MIM can be solved
in polynomial time for restricted graph classes: interval, chordal, weakly chordal, circular-arc,
trapezoid, and co-comparability graphs [2, 13].
In general, counting of matchings is computational hard. In particular, the counting of matchings is #P-complete (Valiant [24]), while it is #W[1]-complete parameterized with the size k of
a matching in a bipartite graph (Curticapean and Marx [4]). For enumeration, Uno [21] showed
that matchings can be enumerated in constant amortized time per solution. To the best of our
knowledge, there are almost no known results for counting and enumeration of induced matchings.
In this paper, we study the complexity of enumeration problems for graphs without cycles of
length 4. Since any graph with girth at least 5 has no C4 , our algorithm also works for such graphs
with large girth, where the girth of a graph is the length of a shortest cycle in the graph. Recently,
2

Table 1: Summary of our results and related work. This table shows the complexity of path,
cycle, matching, and induced matching for each problems. In each cell, we list the complexities
of ordinary problem first and parameterized problems next, where the parameter k is included
in input in all non-parameterized problems (*), the problem is in FPT for graphs with bounded
degree, bounded tree-width, girth at least 6, line graphs, and planar graphs (∗∗ ), the counting
problem for k-induced matchings is FPT linear for graphs with bounded degree, bounded treewidth, and planar graphs parameterized with an implicit parameter determined by the class (∗∗∗ ),
the complexity of an enumeration problem shows its amortized complexity per solution.
counting problem
#P-complete [24]∗
#W[1]-complete [10]
#P-complete [24]∗
#W[1]-complete [10]
#P-complete [23]∗
#W[1]-complete [4]

enumeration problem
Polynomial [18]∗

k-matching

decision problem
NP-complete [12]∗
FPT [8]
NP-complete [12]∗
FPT [6]
P [7]∗

k-induced
matching

NP-complete [19]∗

Unknown

W[1]-complete [16]
FPT∗∗ [16]

FPT linear∗∗∗ for
bounded tree-width
and planar [Ours]

O (1) for boudneddegree [Ours]∗

k-path
k-cycle

Polynomial [9]∗
O (1) [21]∗

O (1) for C4 -free [Ours]∗

there are a few results showing an interesting interplay between induced matchings and graphs
with large girth as follows. Raman and Saurabh [17] demonstrated that several fixed parameter
intractable problems, such as dominating sets, fall in FPT when input graphs have large girth. As
a most closely related result, Moser and Sikdar [16] show that the W [1]-hard decision problem for
induced matchings becomes in FPT for graphs with bounded degree and with girth 6 or more.

2

Preliminary

In this paper, for disjoint set A and B, we define disjoint union of A and B by A t B. If it is
clearly understood, we denote V (G) = V and E(G) = E.
Let G = (V, E) be an undirected graph with vertex set V and edge set E ⊆ V × V . In this
paper, we assume that graphs have no self-loops or parallel edges. An edge e with vertex u and v
is denoted by e = {u, v}. Two vertices u, v ∈ V are adjacent if there is an edge {u, v} in E. We
say u is a neighbor of v if u ∈ NG (v). Similarly, two edges e, f ∈ E are adjacent if e and f share
the same vertex. Let NG (u) be the set of neighbors of u in G and NG [u] = NG (u) ∪ {u} be the
set of closed neighbor of u. Let dG (u) = |NG (u)| be the degree of u in G. ∆(G) = maxx∈V d(x)
denotes the maximum degree of G. For any vertex subset V 0 ⊆ V , we say G[V 0 ] = (V 0 , E[V 0 ]) an
induced subgraph, where E[V 0 ] = {{u, v} ∈ E(G) | u, v ∈ V 0 }. Since G[V 0 ] is uniquely determined
by V 0 , we identify V 0 with G[V 0 ]. We denote by G \ {e} = (V, E \ {e}) and G \ {v} = G[V \ {v}].
For simplicity, we denote by v ∈ G and e ∈ G if v ∈ V and e ∈ E, respectively.
An alternating sequence π = (v1 , e1 , v2 , . . . , vk−1 , ek , vk ) of vertices and edges is a path if each
edge and vertex in π appears at most once. We also call π an v0 -vn path. Then, An alternating
sequence C = (v1 , e1 , v2 , . . . , vk−1 , ek , vk ) of vertices and edges is a cycle if (v1 , e1 , v2 , . . . , vk−1 ) is
a v0 -vk−1 path and vk = v1 . The length of a path and a cycle is defined by the number of its
edges. Let G be Ck -free graph if G has no cycle with length k as a subgraph. For example, if G
has no 4-cycles then G is a C4 -free graph.

3

A solid edge is included in an edge set:
A dotted edge is not included in an edge set:

3
1

4

3
5

2

10

9

9

6

11

8

13

8

13

7

12

5

2

10

6

11

4

1

12

7

(b)This edge set M’ is matching,
but not induced matching.

(a) This edge set M is induced matching.

Figure 1: An edge set M in (a) is an induced matching, because all distinct two edges e, f ∈ M
hold distG (e, f ) ≥ 2. An edge set M 0 in (b) is not an induced matching, because edge e = {9, 10}
and f = {1, 2} do not hold distG (e, f ) ≥ 2.
M(I) = Ø

I
The 1-branch of P
P
M(X’)

X

The downward
path X from X to Y

Y’

Y

X’

The chain consisted of
0-branches from X’ to Y’

M(Y’) = M(X’)
(a) The downward path X and the chain consisted of 0-branches in T

Figure 2: The solid line from X to Y represents a downward path. Consequently, X  Y holds.
The dotted line represents a chain consisting of 0-branches. X 0 is a top of the chain since X 0 is a
1-child of P . Y 0 is a bottom of the chain since Y 0 does not have a child.
For any vertices u, v ∈ V , the distance between u and v is defined by the length of a shortest
u-v path. The distance between edge e and f is defined by the length of a shortest path, i.e.,
distG (e, f ) = min{distG (u, v) | u ∈ e, v ∈ f }. Similarly, the distance between vertex v and edge e
is defined by distG (v, e) = min{distG (u, v) | u ∈ e}.
A matching in a graph G = (V, E) is an edge subset M ⊆ E of G, if any pair of edges in M
does not share their endpoints. An induced matching in a graph G = (V, E) is a matching M ⊆ E
whose vertex set induces M itself. In other words, an edge set M is an induced matching if and
only if distG (e, e0 ) ≥ 2 for any distinct edges e, e0 ∈ M , i.e., there is no edge f in G connecting e
and e0 . In figure 1, we show an example of an induced matching.
Now, we define the induced matching enumeration problem as follows;
Problem 1 (The induced matching enumeration problem). Enumerate all induced matching in a
given graph G without duplicates.

4

3
3.1

Enumeration of Induced Matchings for C4 -free Graphs
Binary partition

A binary partition method is an algorithm which enumerates all solutions by dividing a search space
into two disjoint search spaces recursively. We call a dividing step an iteration. Let G, M(G),
and I be an input graph, the set of solutions for G, and an iteration of the algorithm, respectively.
Let S(I) be the set of solutions included in a search space of I. In the initial state, S(I) = M(G)
holds. At the initial iteration, the algorithm selects an edge e in G such that e satisfies |S0 (I)| ≥ 1
and |S1 (I)| ≥ 1 where S0 (I) = {M ∈ S(I) | e ∈
/ M } and S1 (I) = {M ∈ S(I) | e ∈ M }. Note that
S(I) = S0 (I) t S1 (I) holds. A recursively applies this procedure until all edges are selected.
Next, we introduce a binary enumeration tree T (I) = T = (V, E), for an input I. Here, V is
the set of iterations of A for
T I and E is a subset of V × V. For any iteration X, we define the edge
set EX as follows: EX = M ∈S(X) M . For any iterations X and Y , Y is a child of X if EY ⊂ EX
and |EX \ EY | = 1 hold. We call X is the parent of Y . For any iteration X, we define iterations
X.1 and X.0 with the set of solutions S1 (X) and S0 (X), respectively. That is, X.1 and X.0 are
the children of X. In particular, X.1 is the 1-child of X, and X.0 is the 0-child of X. In addition,
we call edges e = {X, X.0} and f = {X, X.1} in E a 0-branch and a 1-branch, respectively. In the
binary enumeration tree T for I, we call an iteration with children an internal iteration, and an
iteration without children a leaf iteration. Moreover, an iteration X is the root iteration if there is
no iteration that has X as a child, that is, X is the first iteration called by A. For the simplicity,
we call the binary enumeration tree the enumeration tree.
For any iterations X and Y , a downward path (or an upward path) from X to Y in T is a
sequence of iterations L = (X = X0 , . . . , Xk = Y ), where for each i = 1, . . . , k, Xk is a child (or
the parent) of Xk−1 . The length of L is defined as k − 1. For any iterations X and Y , if there is a
downward path L from X to Y , then X is an ancestor of Y and Y is a descendant of X. X  Y
if X is an ancestor of Y . For any iteration Y , the set {X | X  Y } is a chain [5] of Y . When
iterations X and Y belong to a same chain, X and Y are comparable. In a chain L, we call an
iteration X is the minimum element in L and the maximum element in L if X is the head of L
and is the tail of L, respectively. In Figure 2, We show an example of a downward path and a
chain in the enumeration tree T .

3.2

Algorithm for C4 -free graphs

In what follows, suppose that an input graph is a C4 -free graph. We show the algorithm EIM in
Algorithm 1. For any iteration X of RecEIM, let M (X), G(X) and S(X) be the current induced
matching as solution, a graph, and the set of vertices that are selected in the ancestor iterations
of X as the pivot used to partition the problem, respectively. RecEIM outputs M (X) as a solution
if no edge can be added to M (X) from G(X) and quits X. RecEIM skips this step and execute
the following steps if there is an edge that can be added to M (X).
An edge e in G is a safe edge if e satisfies the following condition: For any edge f ∈ M (X),
dist(e, f ) ≥ 2. e is a conflict edge otherwise. Let G(X) = G[V \ (N (V (M (X))) ∪ S(X))]. That is,
G(X) is a graph removed all conflicting edges with M (X) and S(X) from G. RecEIM firstly selects
the vertex v with the maximum degree. We call such a vertex v a pivot on X. Next, RecEIM divides
a solution set S into d(v) + 1 disjoint sets S0 , . . . , S|d(v)| . Let ei be the ith edgeSincident to v for
i ∈ {1, . . . , dG(X) (v)}. Si ⊆ S is the set of solutions including ei , and S0 = S \ i=1,...,dG(X) (v) Si
is the set of solutions not including edges adjacent to v. X.i denotes the ith child iteration of X
that receives M (M (X) ∪ {ei }). Also, we call X.0 type-0 child and X.i type-1 child for i 6= 0. We
call the branch from X to the type-0 child the 0-branch and a branch from X to type-1 child a
1-branch. Let T be an enumeration tree made by EIM. Note that T is not a binary tree but a
5

Algorithm 1: The algorithm enumerating all induced matchings in C4 -free graphs in constant amortized time.
1 Procedure EIM (G = (V, E))
2
RecEIM (∅, G) ;
3
4
5
6

Procedure RecEIM (M, G)
if E(G) = ∅ then
Output M ;
return;

7
8
9
10
11
12
13

The vertex v has the maximum degree in G;
RecEIM (M, G \ {v});
G0 ← G \ N [v];
for e ∈ Dv (0) do
RecEIM (M ∪ {e}, G0 \ Secte (2));

//0-child

//i-child

Restore edges in Dv (0) ∪ Dv (1);
return;

v

X

The current iteration

Y

ei
Z

W

Figure 3
multi-way tree. In Figure 3, we show an example of T . A proof of the next lemma is shown in
Appendix A.
Lemma 1. Let X and Y be any iterations. If X  Y then M (X) ⊆ M (Y ) and E(G(X)) ⊇
E(G(Y )) hold.

3.3

Correctness of the algorithm

For any iteration X on T , it is redundant to process safe and conflict edges independently among
siblings of the same parent. To avoid this, we simultaneously process these edges by using following
concentric structures around the pivot on X. Let k ∈ {0, 1, 2} and ` ∈ {0, 1, 2}. We define the
concentric structure Dv (k, `) as follows:
Dv (k, `) = {{x, y} ∈ E(G(X)) | distG(X) (x, v) = k, distG(X) (y, v) = `}.

(1)

Dv (k) denotes Dv (k, k) t Dv (k, k + 1). We call an edge e ∈ Dv (k, `) a k-` edge of v and an edge
e ∈ Dv (k) a k-∗ edge of v. Figure 4 (a) shows an example of 0-1 edges, 1-∗ edges, and 2-∗ edges.
6

The distance between two vertices is defined by the length of shortest path in not G but G(X).
The next lemma implies that M (X) ∪ {e} is an induced matching in G for any edge e ∈ Dv (0). A
proof of the next lemma is shown in Appendix A.
Lemma 2. Let G be an input graph, X be any iteration in the algorithm EIM in Algorithm 1, and
e be any edge in Dv (0). Then, M (X) ∪ {e} is an induced matching in G.
Since EIM outputs a solution in a leaf iteration and M (X) is induced matching for each iteration
X ∈ T , the following corollary holds from Lemma 2.
Corollary 3. The algorithm EIM in Algorithm 1 outputs only induced matchings.
Next, we consider a method for obtaining G(X.i). For any 0-1 edge ei = {v, ui } of a pivot v,
we define Sectei (k) as follows:
Sectei (k) = {f ∈ Dv (k) | distG(X) (v, f ) = k, distG(X) (ei , f ) = k − 1}.

(2)

We show an example of Sectei (k) in Figure 4. Proofs of the following two lemmas are shown in
Appendix A.
Lemma 4. Let X be an iteration in the algorithm EIM in Algorithm 1. Then, G(X.0) = G(X)\{v}
holds.
Lemma 5. Let X be any iteration in the algorithm EIM in Algorithm 1 and i be positive integer.
Then, G(X.i) = G(X) \ (Dv (0) ∪ Dv (1) ∪ Sectei (2)) holds.
Lemma 4 and Lemma 5 imply that EIM correctly compute G(X.i) in X.
Lemma 6. The algorithm EIM in Algorithm 1 outputs solutions without duplication.
Proof. Let X and Y be two distinct leaf iterations. We proceed by contradiction. Suppose that
M (X) = M (Y ). From the assumption, X and Y are incomparable. Hence, without loss of
generality the lowest common ancestor of X and Y always exists. Let Z be the lowest common
ancestor of X and Y . We consider the following two cases. (1) Suppose that both X and Y are
descendants of the type-0 child Z.0 of Z. This contradicts that Z is the lowest common ancestor of
X and Y . (2) Suppose that at least one of X and Y is a descendant of a type-1 child of Z. Without
loss of generality, X is a descendant of the ith child Z.i of Z. If W is Z.j or is any descendant of
Z.j where j 6= i, then M (W ) does not include ei and this contradicts M (X) = M (Y ). Hence, the
statement holds.
Lemma 7. The algorithm EIM in Algorithm 1 outputs all solutions in M.
Proof. Let T be an enumeration tree, X be any iteration on T , and v be the pivot on X. From
Lemma 4 and Lemma 5, EIM correctly divides a solution set S(X) in X into S0 (X), . . . , Sd(v) (X).
If |S(X)| = 1, then EIM outputs S(X). Hence, EIM outputs all solutions in M.
From corollary 3, Lemma 6, and, Lemma 7, the next theorem holds.
Theorem 8. The algorithm EIM in Algorithm 1 enumerates all solutions without duplication.

7

Sectei(2)

Dv(2)

Dv(2)

Dv(1)

ev

Dv(0, 1)

Dv(1)

g

eei

v

0-1 edge
1-1 edge

Dv(0, 1)

1-2 edge
2-2 edge

2-3 edge

Case (a): calling 0-child.

Case(b): calling 1-child.

Figure 4: An example of dividing edges by the pivot v in the graph G. In case (a), the shaded
area indicates the area of edges to be removed when calling type-0 child. In case (b), the shaded
area indicates the area of edges to be removed when calling type-1 child. The area surrounded by
the solid line represent Sectei (2)

3.4

Amortized analysis of the time complexity

If the degree of the pivot on X is less than three, then EIM obviously runs in the constant amortized
time per solution since the number of steps in each iteration X is constant. Thus, we assume the
degree of pivot is at least three.
We first consider the data structure List(G(X)) to efficiently extract the set of vertices
whose degree is k when we are given k. We define List(G(X)) as follows: List(G(X)) =
{L0 , . . . , L∆(G(X)) }, where for any 0 ≤ i ≤ ∆(G(X)), Li = {v ∈ V (G) | dG(X) (v) = i}. The
lists in List(G(X)) are implemented by doubly-linked lists, and we denote x ∈ List(G(X)) if
List(G(X)) includes x. For any input graph G, we can compute List(G) in O (|V (G)|) time by
using bucket sort. We can implement List(G(X)) such that extracting any vertex from List(G(X))
can be done in constant time. By using List(G(X)), we can see the following lemma. The proof
of Lemma 9 in Appendix A.
Lemma 9. Let X be any iteration in T . Then, we can find the pivot in constant time by using
List(G(X)).
Next, we define the edge set Dv≤ (2) as follows: Dv≤ (2) = Dv (0) ∪ Dv (1) ∪ Dv (2), i.e. Dv≤ (2) is
the edge set consisting of all edges whose distance is less than two from v.
Lemma 10. Let G be a C4 -free graph, v be the pivot on an iteration X, and, u be a vertex
satisfying distG (u, v) = 2. Then, the number of edges whose endpoint is u in the set of 1-2 edges
of v is exactly one.
Proof. We proof by contradiction. Let f1 = {u, w1 } and f2 = {u, w2 } be two distinct 1-2 edges
whose end point is u. We assume w1 6= w2 . Since f1 and f2 are 1-2 edges and distG (u, v) = 2,
distG (v, w1 ) = distG (v, w2 ) = 1 holds. Thus, there exist two edges e1 = {v, w1 } and e2 = {v, w2 }.
8

Hence, there is a cycle (v, e1 , w1 , f1 , u, f2 , w2 , e2 , v) in G. This contradicts that G is a C4 -free
graph. Hence, the statement holds.
Lemma 11. LetP
G be a C4 -free graph and v be the pivot on an iteration. Then, the following
inequality holds:
e∈Dv (0) |Secte (2)| ≤ 2 |Dv (2)|.
S
Proof. We show that e∈Dv (0) Secte (2) = Dv (2). Let f = {x, y} be an edge in Secte (2). By
definition, f ∈ Dv (2) holds. Without loss of generality, we can assume that distG (x, v) = 2. Since
distG (x, v) = 2, there is a vertex
S w satisfying distG (x, w) = distG (w, v) = 1. By definition, f
belongs to Sect{w,v} (2). Hence, e∈Dv (0) Secte (2) = Dv (2) holds.
Next, we assume that for any 2-∗ edge f ∈ Dv (2), f belongs to the following three sets;
Secte1 (2), Secte2 (2), and Secte3 (2) , where e1 , e2 , e3 ∈ Dv (0). Then, by the definition of Sectei (2),
distG (ei , f ) = 1 holds for i ∈ {1, 2, 3}. Hence, there is some gi = {xi , yi } satisfying xi ∈ ei and
yi ∈ f . By the definition of ei , distG (v, xi ) = 1 and distG (v, yi ) = 2 hold. This implies that gi is
a 1-2 edge that shares the end point with f . By the pigeonhole principle, one of the end points of
f has at least two 1-2 edges. This contradicts with Lemma 10, hence the statement holds.
In the remaining of this section, we show that EIM enumerates all solutions in constant amortized time per solution. To show the complexity, we show that the ratio between the number of
1-child iterations and 0-child iterations is constant. If the statement holds, then the number of
iterations on T is linear in the number of leaf iterations of T . Let X be any iteration in T and v
be the pivot on X. Suppose that e = {x, y} is any edge in ∈ Dv≤ (2) and f = {v, x}. We denote
by C(X, e) a descendant iteration of X such that Y = C(X, e) is the top of the chain including X
and receives M (Y ) defined as follows.
(1) If e is a 0-1 edge, then M (Y ) = M (X) ∪ {e}.
(2) If e is a 1-1 edge, then M (Y ) = M (X) ∪ {f }.
(3.a) If e is a 1-2 edge and Sectf (2) = ∅, then M (Y ) = M (X) ∪ {e}.
(3.b) If e is a 1-2 edge and Sectf (2) 6= ∅, then M (Y ) = M (X) ∪ {f 0 , g}, where f 0 ∈ Dv (0) and
g ∈ Sectf (2) such that f 0 6= f and distG (f 0 , g) = 2.
(4) If e is 2-∗ edge, then M (Y ) = M (X) ∪ {e, h}, where h is an edge such that h is adjacent to
v and distG (e, h) = 2.
We call C(X, e) the corresponding iteration to X w.r.t e. The next lemma shows that C(X, e)
satisfying the above conditions always exists.
Lemma 12. For any iteration X and e ∈ Dv≤ (2), there always exists the corresponding iteration
C(X, e) to X w.r.t e.
Proof. Let e = (x, y). From Lemma 7, to proof the lemma, all we have to do is show that
M (C(X, e)) is a solution. If (1) or (3.a) holds, then M (C(X, e)) is obviously an induced matching
since e ∈ Dv≤ (2). Next, we consider condition (2). There are two edges {v, x} = f and {y, v} since
e is a 1-1 edge. Since f ∈ Dv≤ (2), M (C(X, e)) is a solution. Next, we consider condition (3.b).
Let f = {v, x}. Since e is a 1-2 edge, such edge f always exists. Let g be any edge in Sectf (2).
From Lemma 10, at least one of the end points of g connects exactly one 1-2 edge. Hence, there
is an edge f 0 6= f that is adjacent to v and satisfies distG (f 0 , g) = 2 since the degree of v is at
least three. Moreover, {f 0 , g} is an induced matching since distG (f 0 , g) = 2. Hence, M (C(X, e))
is an induced matching. Finally, we consider condition (4). Since dG (v) ≥ 3, there exists an edge
h that is adjacent to v and satisfies distG (e, h). Hence, M (C(X, e)) is an induced matching.
9

In the following lemmas, for any iteration X, we show the number of pairs of an iteration and
an edge whose corresponding iteration is X is constant.
Lemma 13. If a graph G is C4 -free, then the number of 1-1 edges adjacent to 0-1 edges is at most
one.
Proof. We show the lemma by contradiction. Suppose there are two distinct 1-1 edges f = {u, w}
and g = {u, x} that are adjacent to a 0-1 edge e. By the definition of a 1-1 edge, {u, w, x} ⊆ N (v).
Hence, there exist two distinct edges f 0 = {v, w} and g 0 = {v, x}. However, this implies that there
exist a 4-cycle (v, f 0 , w, f, u, g, x, g 0 , v). This contradicts that G is C4 -free. Hence, the statement
holds.
For the proofs of the next lemmas, see Appendix A.
Lemma 14. Let X and e be a pair of an iteration on T and an edge in Dv≤ (2) satisfying condition
(3.a), and Y be any iteration on L from X to C(X, e) such that Y satisfies C(Y, e) = C(X, e).
Then, the number of such Y is at most two.
Lemma 15. Let X be any iteration in T . Then, the number of pairs an iteration Y and an edge
e satisfying C(Y, e) = X is at most six.
From Lemma 13, Lemma 14, and Lemma 15, for any iteration X ∈ T , the number of pairs
of an iteration Y and an edge e such that C(Y, e) = X is constant. Next,
the following lemmas
T
show that total computation time in EIM is O (|T |) time. Let F (X) be i=0,...,∆(G(X)) E(G(X.i)).
That is, F (X) is the set of edges that are shared by all child iterations of X.
Lemma 16. Let v be the pivot on an iteration X in T . Then, E(G(X)) \ F (X) = Dv≤ (2).
Proof. Let {e1 , . . . , edG(X) (v) } be the set of edges that are adjacent to v. We show F (X) =
E(G(X)) \ Dv≤ (2). Firstly, we show F (X) ⊆ E(G(X)) \ Dv≤ (2). For any i = 0, . . . , dG(X) (v),
M (G(X.i)) includes ei = {v, ui } by definition. Hence, F (X) does not include conflicting edges
of ei . In addition, each edge f ∈ F (X) satisfies distG(X) (f, v) ≥ 2 and distG(X) (f, ui ) ≥ 2.
Therefore, f is not included in Dv≤ (2). Secondly, we show F (X) ⊇ E(G(X)) \ Dv≤ (2). Let g be
any edge in E(G(X)) \ Dv≤ (2). By definition, distG(X) (g, ei ) ≥ 2 holds for any ei . Therefore,
g ∈ F (X) since g ∈ E(G(X.i)). Now, Dv≤ (2) ⊆ E(G(X)) and F (X) ∩ Dv≤ (2) = ∅. Hence, the
statement holds.
P
Lemma 17.
X∈V (T ) |E(G(X)) \ F (X)| is bounded by O (|T |).
Proof. Let X be any iteration and v be the pivot on X. The number of iterations Y = C(X, e) is
≤
≤
at most DP
v (2) , where e is an edge in Dv (2). Hence, the number of all corresponding iterations
is equal to X∈V (T ) |E(G(X)) \ F (X)| since E(G(X)) \ F (X) = Dv≤ (2) from Lemma 16 together
with that a pair of an internal iteration X and an edge e ∈ Dv≤ (2) corresponds to exactly one
iteration C(X, e). Next, we consider the number of all corresponding iterations. The number of
pairs of an iteration Y and an edge e such that C(Y, e) = X is at most constant from Lemma 15.
Since the number of internal iteration is |T |, the number of all corresponding iterations is bounded
by O (|T |), Hence, the statement holds.
Theorem 18. The algorithm EIM in Algorithm 1 enumerates all induced matchings in constant
amortized time per solution in a C4 -free graph G after O (|V | + |E |) preprocessing time.

10

Proof. The correctness of EIM is obvious from Lemma 8. Next, we consider the time complexity
of EIM. Let X be an iteration of EIM. In the preprocessing phase, EIM constructs List(G) in
O (|V | + |E |) time by using bucket sort. Next, we consider the total time for deleting edges in
an input graph. Each edge is deleted at most twice from Lemma 10 in each iteration. Moreover,
from Lemma 17, the total number of deleted edges is O (|T |) in EIM. Hence, the total time of
edge deletion is O (|T |) time since each edge can be removed in constant time from the input
graph. Next, we consider the total time of the updating List(G(X)). When EIM removes an edge
e = {u, v} from X, EIM moves u ∈ Li to Li−1 and v ∈ Lj to Lj−1 . Since it can be done in constant
time, the time complexity of EIM is O (|T |). In addition, every iteration X in T has a child at
least two. Hence, the number of solutions is Ω(|T |). Therefore, EIM runs in O (|T | / |T |) = O (1)
time per solution.

4

Counting of Induced Matchings for Other Graph Classes

To complement the result of Sec. 3, in this section, we present some fixed-parameter tractability
results on counting the number of induced matchings in terms of descriptive complexity theory [10].
See Appendix B for omitted definitions and proofs. Recently, Frick [11] introduced the notion of
locally tree-decomposability by generalizing the tree decomposition. He showed the fact that the
classes of graphs of bounded degree, of bounded tree-width, and planar graphs are locally treedecomposable [11].
Proposition 19 (Frick [11]). Let C be any class of locally tree-decomposable structures. For any
structure A ∈ C, a counting problem Π definable in FO can be solved in linear time in ||A||, where
A is given with its underlying nice tree cover T associated with r, `, g.
For any k ≥ 0, a k-induced matching is an induced matching M ⊆ E with |M | = k. From the
above fact and Proposition 31, we show the next theorem.
Theorem 20. For any class G of graphs of bounded degree, graphs of bounded tree-width, or planar
graphs and any k ≥ 0, the counting problem of k-induced matchings in an input graph G in G can
be solved in linear time in ||G||.
In the proof, we built a FO-formula φ describing that an edge subset is a k-induced matching.
Hence, the counting problem of k-induced matchings belongs to FPT when parameterized with
some constants determined by k, φ, and G.

5

Conclusion

In this paper, we presented an efficient algorithm for enumerating all induced matchings in constant
amortized time for C4 -free graphs. Generalization of this result to other graph classes is an
interesting future work. Investigating the other class of induced subgraphs such as induced paths
is also interesting. We also have interests in the independent set enumeration in the square of line
graphs [3] and also counting problems of these structures.
Acknowledgements
This research was supported by Grant-in-Aid for Scientific Research(A) Number 16H01743.

11

References
[1] S. Arnborg, J. Lagergren, and D. Seese. Easy problems for tree-decomposable graphs. Journal
of Algorithms, 12(2):308–340, 1991.
[2] A. Brandstädt and C. T. Hoàng. Maximum induced matchings for chordal graphs in linear
time. Algorithmica, 52(4):440–447, 2008.
[3] K. Cameron. Induced matchings. Discrete Appl. Math., 24(1-3):97–102, 1989.
[4] R. Curticapean and D. Marx. Complexity of counting subgraphs: Only the boundedness of
the vertex-cover number counts. In Proc. FOCS 2014, pages 130–139. IEEE, 2014.
[5] R. Diestel. Graph Theory. Grad. Texts in Math. Springer-Verlag, 4th edition, 2010.
[6] R. G. Downey and M. R. Fellows. Parameterized complexity. Springer Science & Business
Media, 2012.
[7] J. Edmonds. Paths, trees, and flowers. Canad. J. Math., 17:449–467, 1965.
[8] M. R. Fellows and M. A. Langston. On search decision and the efficiency of polynomial-time
algorithms. In Proc. STOC 1989, pages 501–512. ACM, 1989.
[9] R. A. Ferreira, R. Grossi, and R. Rizzi. Output-sensitive listing of bounded-size trees in
undirected graphs. In Proc. ESA 2011, volume 6942 of LNCS, pages 275–286. Springer, 2011.
[10] J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, 2006. pages 493.
[11] M. Frick. Generalized model-checking over locally tree-decomposable classes. Theory of
Computing Systems, 37(1):157–191, 2004.
[12] M. R. Garey and D. S. Johnson. Computers and Intractability; A Guide to the Theory of
NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1990.
[13] M. C. Golumbic and M. Lewenstein. New results on induced matchings. Discrete Appl. Math.,
101(1):157–165, 2000.
[14] J. E. Hopcroft and R. M. Karp. An n5/2 algorithm for maximum matchings in bipartite
graphs. SIAM J. Comput., 2(4):225–231, 1973.
[15] V. V. Lozin. On maximum induced matchings in bipartite graphs. Inf.Process.Lett., 81(1):7–
11, 2002.
[16] H. Moser and S. Sikdar. The parameterized complexity of the induced matching problem.
Discrete Applied Mathematics, 157(4):715–727, 2009.
[17] V. Raman and S. Saurabh. Short cycles make w-hard problems hard: Fpt algorithms for
w-hard problems in graphs with no short cycles. Algorithmica, 52(2):203–225, 2008.
[18] R. C. Read and R. E. Tarjan. Bounds on backtrack algorithms for listing cycles, paths, and
spanning trees. Networks, 3(5):237–252, 1975.
[19] L. J. Stockmeyer and V. V. Vazirani. NP-completeness of some generalizations of the maximum matching problem. Inf. Process. Lett., 15(1):14–19, 1982.
[20] R. E. Tarjan and R. C. Read. Bounds on backtrack algorithms for listing cycles, paths and
spanning trees. Networks, 5:237–252, 1975.
12

[21] T. Uno. Constant time enumeration by amortization. In Proc. WADS 2015, volume 9214 of
LNCS, pages 593–605. Springer, 2015.
[22] T. Uno. Amortized analysis on enumeration algorithms. In Encyclopedia of Algorithms, pages
72–76. 2016.
[23] L. G. Valiant. The complexity of computing the permanent. Theor. Comput. Sci., 8(2):189–
201, 1979.
[24] L. G. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on
Computing, 8(3):410–421, 1979.

13

A

Appendix (Proof of some lemmas)

In this appendix, we show proofs of Lemma 1, Lemma 2, Lemma 4, Lemma 5, and Lemma 9.
Lemma 21. Let X and Y be any iterations. If X  Y then M (X) ⊆ M (Y ) and E(G(X)) ⊇
E(G(Y )) hold. (A proof of Lemma 1. )
Proof. There is a downward path L from X to Y since X  Y . It is obvious that EIM does not
remove any edge in M (X) from M (X 0 ) in X 0 ∈ L. On the other hands, EIM does not add any
edge to E(G(X)) to E(G(X 0 )) in X 0 ∈ L.
Lemma 22. Let G be an input graph, X be any iteration in the alglrithm EIM in Algorithm 1, and
e be any edge in Dv (0). Then, M (X) ∪ {e} is an induced matching in G. (A proof of Lemma 2. )
Proof. We proof by contradiction. Assume that there is a conflicting edge f ∈ M (X) with e.
From Lemma 1, there is an iteration Y  X such that f is added to M (Y ). Since f conflict with
e, either (1) e is adjacent to f or (2) e is not adjacent to f and there is an edge g in G(Y ) that is
adjacent to both e and f . We consider case (1). By the definition of G(Y ), if EIM adds f to M (Y )
in Y , edges adjacent to f are not in G(W ), for any descendant iteration W of Y . This contradicts
the assumption. Next, we consider case (2). If g ∈ G(Y ) holds, then distG(Y ) (e, g) = 1. This
implies that for any descendant iteration W of Y , e ∈
/ G(W ). On the other hands, if g ∈
/ G(Y ),
then G(Y ) is not induced subgraph since e, f ∈ G(Y ) and g ∈
/ G(Y ). This also contradicts the
assumption. Hence the statement holds.
Lemma 23. Let X be an iteration in the algorithm EIM in Algorithm 1. Then, G(X.0) = G(X) \
{v} holds. (A proof of Lemma 4. )
Proof. Since M (X) = M (X.0), there is no edge in G(X.0) such that one of its endpoint is v.
Thus, the statement holds.
Lemma 24. Let X be any iteration in the algorithm EIM in Algorithm 1 and i be positive integer.
Then, G(X.i) = G(X) \ (Dv (0) ∪ Dv (1) ∪ Sectei (2)) holds. (A proof of Lemma 5. )
Proof. For any edge f in G, we show that the following cases are equivalent: (1) f is conflicting
edge of e and (2) f belongs to Dv (0) ∪ Dv (1) ∪ Sectei (2). Let ei = {v, vi } and f = {u, w}. Without
loss of generality, we can assume that distG (u, v) ≤ distG (w, v). If f ∈
/ Dv (0) ∪ Dv (1) ∪ Sectei (2),
then 1 < distG (u, v) ≤ distG (w, v) and 1 < distG (u, v1 ) ≤ distG (w, v1 ) hold. Hence, f does not
conflict with ei . On the other hands, if f ∈
/ Dv (0) ∪ Dv (1) ∪ Sectei (2) then f obviously conflicts
with ei . Hence, the statement holds.
Lemma 25. Let X be any iteration in T . Then, we can find the pivot in constant time by using
List(G(X)). (A proof of Lemma 9. )
F
Proof. It is obvious that Li ∈List(G(X)) = V (G) holds. i∗ =
arg max (Li 6= ∅), that is, Li∗
i∈{0,...,∆(G(X))}

is the non empty list with the maximum index in List(G(X)). Now, the pivot on X is in Li∗ since
∆(G(X)) = i∗ . Hence, EIM can obtain v in constant time by extracting a vertex from the tail of
Li∗ .
Lemma 26. Let X and e be a pair of an iteration on T and an edge in Dv≤ (2) satisfying condition
(3.a), and Y be any iteration on L from X to C(X, e) such that Y satisfies C(Y, e) = C(X, e).
Then, the number of such Y is at most two. (A proof of Lemma 14. )

14

Proof. We first show that L consists of 0-branches except the end of L. By the definition of
C(X, e), the end of L is a 1-branch since C(X, e) is the top of a chain. Next, L includes exactly
one 1-branch since M (C(X, e)) = M (X) ∪ {e}. Hence, L consists of only 0-branch other than the
end of L.
By using the above observation, we proof by contradiction. Suppose that there exists three
distinct iterations Y1 , Y2 , and Y3 such that they satisfy condition (3.a) and C(X, e) = C(Y1 , e) =
C(Y2 , e) = C(Y3 , e). Thus, for any i = 1, 2, 3, e is a 1-2 edge of vi that is the pivot of Yi . Let
e = {x, y} and fi be an edge such that fi shares the end point with e and fi is adjacent to vi .
Without loss of generality, we can assume f1 = {x, v1 } and Y1  Y2 , Y1  Y3 . For j = 2, 3, if
G(Yj ) has the edge fj = {y, vj }, then this contradict with Sectfi (2) = ∅. Hence, vj is a neighbor
of x. In Y1 , the number of 1-1 edges adjacent to f1 is at most one from Lemma 13. Hence, at least
one of f2 and f3 is a 1-2 edge. Without loss of generality, we can assume that f2 is a 1-2 edge.
Since Sectf1 (2) = ∅, DG(Y1 ) (v3 ) = 1. In addition, in Y3 , dG(Y3 ) (x) ≥ 2 since x is adjacent to y and
v3 . However, this contradicts with dG(Y3 ) (v3 ) ≥ dG(Y3 ) (x). Hence, the statement holds.
Lemma 27. Let X be any iteration in T . Then, the number of pairs an iteration Y and an edge
e satisfying C(Y, e) = X is at most six. (A proof of Lemma 15. )
Proof. Let L be the path from the root iteration I on T to X and X 0 be the parent iteration of
X. Without loss of generality, we can assume that X is the top of a chain by the definition of
C(Y, e). Let X 00 be the parent of the top of a chain including X 0 and L0 be the path from X 00 to
X 0 . By the definition of C(Y, e), Y satisfying C(Y, e) = X exists only on L0 . If Y is X 0 , then the
number of edges e0 satisfying C(Y, e0 ) = X is at most two by conditions (1) and (2). If Y is X 00 ,
then the number of edges e0 satisfying C(Y, e0 ) = X is at most two by conditions(3.b) and (4). If
Y is not X 0 and X 00 , then the number of Y satisfying C(Y, e) = X is at most two from Lemma 14.
Hence, the statement holds.

B

Appendix (The descriptive parameterized complexity of
counting problems)

In this section, we will give the proof of Theorem 20 in Sec. 4. See literatures [10] There are
some generic fixed-parameter tractability results for counting problems formulated in terms of
descriptive complexity theory [10]. In 1991, Arnborg and Seese showed that the counting problems definable in monadic second-order logic (MSO) can be solved in linear time when the input
structures have bounded tree-width [10]. By extending these results, Frick [11] showed that the
counting problems definable in first-order logic (FO) can be solved in linear time on locally treedecomposable classes of structures.
Formally, their result is summarized as follows. A parameterized counting problem is formulated
as a problem of, given an instance I and a parameterization k ≥ 0, a parameterization of I,
returning a number F (I) ≥ 0. We say that a counting problem parameterized with k belongs to
FPT if there exist some computable function f and constant c > 0 such that the problem can be
solved in O(f (k) nc ) time, where n is the input size [10].
We introduce the language of first-order logic (FO) as follows [10]. Let τ be the vocabulary
of graphs. For a graph G = (V, E), we assume that the corresponding FO-structure A = (A, . . . )
includes the domain A := V ∪ E for vertices and edges, and the incident relation IND ⊆ E × V × V
defined later.1 We also assume that the vocabulary τ for graphs includes the ternary relation IND
such that IND(e, x, y) ⇐⇒ an edge e has end points x and y. The set F O[τ ] of first-order formulas
1 We can easily see that the structure A = (V ∪ E, IND) is polynomially related to the standard graph structure
A0 = (V, E), and can be computed from A0 in linear time.

15

is built up from countably many sorted first-order variables x, y, x1 , . . . for vertices and e, f, e1 , . . .
for edges, the predicate symbols IND for incidencet relation, = for equality, and P1 , P2 , · · · ∈ τ ,
connectives ∨, ∧, ¬, →, and quantifiers ∃x, ∀x ranging over indivisuals. We assume the standard
semantics of FO-formulas [11].
A decision problem Π is definable in FO on vocabulary τ for a class C of structures 2 if and only
if there exists a FO-formula φ(x̄) ∈ F O[τ ] with some m-vector of free variables x̄ = (x1 , . . . , xm )
such that for all structure A ∈ C, the answer of Π is yes on A ⇐⇒ there exists some m-tuple
ā = (a1 , . . . , am ) ∈ Am such that A |= φ(ā) holds. Similarly, we introduce the FO-definability of
counting problems as follows.
Definition 28 ( [10, 11]). A counting problem Π is definable in FO if there exists a FO-formula
φ(x̄) ∈ F O[τ ] with some x̄ = (x1 , . . . , xm ) such that the answer (the number of solutions in Π) is
given by the number of ā ∈ Am such that A |= φ(ā).
Extending the notion of tree-decomposition [10], Frick [11] gave a sufficient condition, called
locally tree-decomposability, so that a counting problems definable in the first-order logic (FO)
belongs to FPT. Let τ be a vocabulary and A a τ -structure with domain A. The Gaifman graph
of A is the graph G(A) = (A, F ), where the vertex set is A, and for every a, b ∈ A, (a, b) ∈ F
⇐⇒ a and b appear in the same tuple of some relation in A. We denote by dA (a, b) the distance
between a and b in G(A). For any r ≥ 1 and element a ∈ A, we define the r-neighborhood
of a by
S
the set NrA (a) := {b ∈ A | dA (a, b) ≤ r}. For any set X ⊆ A, we define NrA (X) := a∈X NrA (a).
Let A be a structure with domain A. Let r, ` ≥ 1 be any integers and g : N → N be any function.
A nice (r, `, g)-tree cover of a structure A is a class T of subsets of A such that:
(1) For any a ∈ A, there exists some U ∈ T such that NrA (a) ⊆ U .

(2) For any U ∈ T , there are less than ` sets V ∈ T such that U ∩ V 6= ∅.
(3) For all U1 , . . . , Uq ∈ T and q ≥ 1, the tree-width of the induced structure hU1 ∪ · · · ∪ Uq iA
is g(q) or less.
Definition 29 (Frick [11]). A class C of structures is locally tree-decomposable if there is a linear
time algorithm that, given structure A ∈ C and r ≥ 1, computes a nice (r, `, g)-cover of A for
suitable ` = `(r) and g = gr depending only on r.
In the above definition, the parameter r corresponds to the radius of predicates in Gaifman’s
Theorem on the locality of FO-formulas [10].
Lemma 30 (Frick [11]). The classes of graphs of bounded degree, of bounded tree-width, and
planar graphs are locally tree-decomposable.
In the followings, we denote by ||G|| = m + n the size of an input graph G.
Proposition 31 (Frick [11]). Let C be any class of locally tree-decomposable structures. For any
structure A ∈ C, a counting problem Π definable in FO can be solved in linear time in ||A||, where
A is given with its underlying nice (r, `, g)-tree cover T associated with r, `, g.
From the proof of Proposition 31 in [11], we can see that the running time of the algorithm
to solve the the counting problem is O(f (k)nc ) for some function f and constant c, where the
parameter k is determined by on r, `, g, the nice (r, `, g)-tree cover T , and the size ||φ|| of the
formula φ. Note that f is even not elementary in general [11].
For any k ≥ 0, a k-induced matching in a graph G = (V, E) is an induced matching M ⊆ E
with |M | = k. Now, we show the main results of this section.
2 This definition is equivalent to that a Π is definable in FO on τ if there exists a FO-formula φ ∈ F O[τ ] such
that for all structures A, the answer of Π is yes on G if and only if A |= φ.

16

Theorem 32. For any class G of graphs of bounded degree, graphs of bounded tree-width, or planar
graphs and any k ≥ 0, the counting problem of k-induced matchings in an input graph G in G can
be solved in linear time in ||G||. (A proof of Theorem 20. )
Proof. To prove the theorem, it is sufficient to give a FO-formula φ(e1 , . . . , ek ) such that G |=
φ(e1 , . . . , ek ) ⇐⇒ the set M = {e1 , . . . , ek } is an induced matching in G. We give auxiliary
predicates as follows. First, the predicate
^
DISJ(e1 , . . . , ek ) ≡
¬(ei = ej )
1≤i<j≤k

states that edges e1 , . . . , ek are mutually distinct. Secondly, the predicate
CONN(e, f, g) ≡

∃x1 , ∃x2 , ∃y1 , ∃y2 , ∃z1 , ∃z2


x1 , x2 ) ∧ IND(f,
 IND(e,
W y1 , y2 )∧

 
(IND(g, z1 , z2 ) ∧ i,j∈{1,2} (xi = z1 ) ∧ (yj = z2 ) )
.


∨(x1 = y1 ) ∨ (x2 = y2 )

states that given edges e and f are connected by another given edge g. Using CONN, we then
define the predicate
^

SAFE(e1 , . . . , ek ) ≡
¬ ∃g CONN(ei , ej , g)
1≤i<j≤k

which states that there is no edge connecting any pair of distinct edges in {e1 , . . . , ek }. Combining
these predicates, we build the desired predicate
φ(e1 , . . . , ek ) ≡ DISJ(e1 , . . . , ek ) ∧ SAFE(e1 , . . . , ek )
Hence, it follows from Lemma 30 and Proposition 31 that for any G = (V, E), we can compute
the number Nk of k-tuples ē = (e1 , . . . , ek ) ∈ E k with G |= φ(ē) in linear time in ||G|| = m + n.
Since there are exactly k! permutations of {e1 , . . . , ek }, we can obtain the number of k-induced
matchings in G as Nk devided by k!.
From the proof of the above theorem, we see that the counting problem of k-induced matchings
belongs to FPT when parameterized with k and some constants determined by the nice local tree
decomposition for an input class G. It is not hard to see that the formula φ in the proof can be
written in the form φ(ē) ≡ ∀x̄ ψ(ē, x̄) for a quantifier-free FO-formula ψ. Thus, it is in FO-Π1 .

17

