arXiv:1704.07279v1 [] 24 Apr 2017

Finding, Hitting and Packing Cycles in Subexponential Time on
Unit Disk Graphs∗
Fedor V. Fomin1 , Daniel Lokshtanov1 , Fahad Panolan1 , Saket Saurabh1,2 , and Meirav
Zehavi1
1

Department of Informatics, University of Bergen, Norway,
{fomin,daniello,fahadn.panolan,meirav.zehavi}@ii.uib.no
2
The Institute of Mathematical Sciences, HBNI, Chennai, India, saket@imsc.res.in

Abstract
√

We give algorithms with running time 2O( k log k) · nO(1) for the following problems. Given
an n-vertex unit disk graph G and an integer k, decide whether G contains
•
•
•
•
•

a
a
a
a
a

path on exactly/at least k vertices,
cycle on exactly k vertices,
cycle on at least k vertices,
feedback vertex set of size at most k, and
set of k pairwise vertex-disjoint cycles.

For the ﬁrst three problems, no subexponential time parameterized algorithms were previously
known. For the remaining two problems, our algorithms signiﬁcantly outperform the previously
0.75
best known parameterized algorithms that run in time 2O(k log k) · nO(1) . Our algorithms are
based on a new kind of tree decompositions of unit disk graphs where the separators√can have
size up to k O(1) and there exists a solution that crosses every separator at most O( k) times.
The running times of our algorithms are optimal up to the log k factor in the exponent, assuming
the Exponential Time Hypothesis.

1

Introduction

Unit disk graphs are the intersection graphs of unit circles in the plane. That is, given n-unit circles
in the plane, we have a graph G where each vertex corresponds to a circle such that there is an
edge between two vertices when the corresponding circles intersect. Unit disk graphs form one of
the most well studied graph classes in computational geometry because of their use in modelling
optimal facility location [41] and broadcast networks such as wireless, ad-hoc and sensor networks
[26, 34, 43]. These applications have led to an extensive study of NP-complete problems on unit
disk graphs in the realms of computational complexity and approximation algorithms. We refer the
reader to [12, 20, 30] and the citations therein for these studies. However, these problems remain
hitherto unexplored in the light of parameterized complexity with exceptions that are few and far
between [1, 10, 25, 33, 39].
∗

Supported by Pareto-Optimal Parameterized Algorithms, ERC Starting Grant 715744, Parameterized Approximation, ERC Starting Grant 306992, and Rigorous Theory of Preprocessing, ERC Advanced Investigator Grant
267959.

1

In this paper we consider the following basic problems about ﬁnding, hitting and packing cycles
on unit disk graphs from the viewpoint of parameterized algorithms. For a given graph G and
integer k,
• Exact k-Cycle asks whether G contains a cycle on exactly k vertices,
• Longest Cycle asks whether G contains a cycle on at least k vertices,
• Feedback Vertex Set asks whether G contains a vertex set S of size k such that the graph
G \ S is acyclic, and
• Cycle Packing asks whether G contains a set of k pairwise vertex-disjoint cycles.
Along the way, we also study Longest Path (decide whether G contains a path on exactly/at
least k vertices) and Subgraph Isomorphism (SI). In SI, given connected graphs G and H on
n and k vertices, respectively, the goal is to decide whether there exists a subgraph in G that is
isomorphic to H. T hroughout the paper we assume that a unit disk graph is given by a set of n
points in the Euclidean plane and there is a graph where vertices correspond to these points and
there is an edge between two vertices if and only if the distance between the two points is at most
2.
In parameterized complexity each of these problems serves as a testbed for development of
fundamental algorithmic techniques such as color-coding [2], the polynomial method [35, 36, 42, 4],
matroid based techniques [23] for Longest Path and Longest Cycle, and kernelization techniques for Feedback Vertex Set [40]. We refer to [14] for an extensive overview of the literature
on parameterized algorithms for these problems. For example, the fastest known algorithms solving
Longest Path are the 1.66k · nO(1) time randomized algorithm of Björklund et al. [4], and the
2.597k · nO(1) time deterministic algorithm of Zehavi [44]. Moreover, unless the Exponential Time
Hypothesis (ETH) of Impagliazzo, Paturi and Zane [31] fails, none of the problems above can be
solved in time 2o(k) · nO(1) [31].
While all these problems remain NP-complete on planar graphs, substantially faster—subexponential—
parameterized algorithms are known on planar graphs. In particular, by combining the bidimensionality theory of Demaine et al. [15] with eﬃcient algorithms on graphs of bounded treewidth [19],
Longest Path,
Longest Cycle, Feedback Vertex Set and Cycle Packing are solvable
√
k)
O(1)
O(
n
on planar graphs. The parameterized subexponential “tractability” of such
in time 2
problems can be extended to graphs excluding some ﬁxed graph as a minor [17]. The bidimensionality arguments cannot be applied to Exact k-Cycle and this was one of the motivations for
developing the new pattern-covering √technique, which is used to give a randomized algorithm for
2
Exact k-Cycle running in time 2O( k log k) nO(1) on planar and apex-minor-free graphs [22]. The
bidimensionality theory was also used to design (eﬃcient) polynomial time approximation scheme
((E)PTAS) [16, 24] and polynomial kernelization [21] on planar graphs.
It would be interesting to ﬁnd generic properties of problems, similar to the theory of bidimensionality for planar-graph problems, that could guarantee the existence of subexponential parameterized algorithms or (E)PTAS on geometric classes of graphs, such as unit disk graphs. The
theory of (E)PTAS on geometric classes of graphs is extremely well developed and several methods
have been devised for this purpose. This includes methods such as shifting techniques, geometric
sampling and bidimensionality theory [30, 28, 27, 29, 13, 38, 25]. However, we are still very far from
a satisfactory understanding of the “subexponential” phenomena for problems on geometric graphs.
We know that
√ some problems such as Independent Set and Dominating Set, which are solvable
k) nO(1) on planar graphs, are W[1]-hard on unit disk graphs and thus the existence of
O(
in time 2
2

an algorithm of running time f (k) · nO(1) is highly unlikely for any function f [37]. The existence of
a vertex-linear kernel for some problems on unit disk graphs such as Vertex Cover [11] or Connected Vertex Cover [33] combined with an appropriate separation theorem [1, 10, 39] yields
a parameterized subexponential algorithm. A subset of the authors of this paper used a diﬀerent
approach based on bidimensionality theory to obtain subexponential algorithms of running time
0.75
2O(k log k) · nO(1) on unit disk graphs for Feedback Vertex Set and Cycle Packing in [25].
No parameterized subexponential algorithms on unit disk graphs for Longest Path, Longest
Cycle, and Exact k-Cycle were known prior to our work.
√
Our Results. We design subexponential parameterized algorithms, with running time 2O( k log k) ·
nO(1) , for Exact k-Cycle, Longest Cycle, Longest Path, Feedback Vertex Set and
Cycle Packing on unit disk graphs and unit square graphs. It is also possible to show by known
NP-hardness
reductions for problems on unit disk graphs [12] that an algorithm of running time
√
o(
k)
O(1)
·n
for any of our problems on unit disk graphs would imply that ETH fails. Hence
2
our algorithms are asymptotically almost tight. Along the way we also design Turing kernels (in
fact, many to one) for Exact k-Cycle, Longest Cycle, Longest Path and SI. That is, we
give a polynomial time algorithm that given an instance of Exact k-Cycle or Longest Cycle
or Longest Path or SI, produces polynomially many reduced instances of size polynomial in k
such that the input instance is a Yes-instance if and only if one of the reduced instances is. As a
byproduct of this we obtain a 2O(k log k) · nO(1) time algorithm for SI when G is a unit disk graph
and H is an arbitrary connected graph. It is noteworthy to remark that a simple disjoint union
trick implies that Exact k-Cycle, Longest Cycle, Longest Path, and SI do not admit a
polynomial kernel on unit disk graphs [8]. Finally, we remark that we do not use Turing kernels to
design our subexponential time algorithms except for Exact k-Cycle. The subexponential time
parameterized algorithm for Exact k-Cycle also uses a “double layering” of Baker’s technique [3].
All our subexponential time algorithms have the following theme in common. If an input nvertex unit disk graph G contains a clique of size poly(k) (such a clique can be found in polynomial
time), then we have a trivial Yes-instance or No-instance, depending on the problem. Otherwise,
we show that the unit disk graph G in a Yes-instance of the problem admits, sometimes after a
polynomial time preprocessing, a speciﬁc type of (ω, ∆, τ )-decomposition, where the meaning of ω,
∆ and τ is as follows. The vertex set of G is partitioned into cliques C1 , . . . , Cd , each of size at
most ω = kO(1) . We also require that after contracting each of the cliques Ci to a single vertex,√the
maximum vertex degree ∆ of the obtained graph G̃ is O(1), while the treewidth τ of G̃ is O( k).
Moreover, the corresponding tree decomposition of G̃ can be constructed eﬃciently. We use the
tree decomposition of G̃ to construct a tree decomposition of G by “uncontracting” each of the
contracted cliques Ci . While the width of the obtained tree decomposition of G can be of order
ω · τ = kO(1) , we show that each of our parameterized problems can be solved in time f (∆) · ω f (∆)·τ .
Here we use dynamic programming over the constructed tree decomposition of G, however there
is a twist from the usual way of designing such algorithms. This part of the algorithm is problemspeciﬁc—in order to obtain the claimed running time, we have to establish a very speciﬁc property
for each of the problems. Roughly speaking, the desired property of a problem is that it always
admits an optimal solution such that for every pair of adjacent bags X, Y of the tree
√ decomposition
of G, the number of edges of this solution “crossing” a cut between X and Y is O( k). We remark
that the above decomposition is only given in the introduction to present our ideas for all the
algorithms in a uniﬁed way.

3

2

Preliminaries

For a positive integer t, we use [t] as a shorthand for {1, 2, . . . , t}. Given a function f : A → B
and a subset A′ ⊆ A, let f |A′ denote the restriction of the function f to the domain A′ . For a
function f : A → B and B ′ ⊆ B, f −1 (B ′ ) denote the set {a ∈ A : f (a) ∈ B ′ }. For t, t′ ∈ N, a
set [t] × [t′ ], i ∈ [t] and j ∈ [t′ ] we use (∗, j) and (i, ∗) to denote the sets {(i′ , j) : i′ ∈ [t]} and
{(i, j ′ ) : j ′ ∈ [t′ ]}, respectively. For a set U , we use 2U to denote the power set of U .
Graph Theory. We use standard notation and terminology from the book of Diestel [18]
for graph-related terms which are not explicitly deﬁned here. Given a graph G, V (G) and E(G)
denote its vertex-set and edge-set, respectively. When the graph G is clear from context, we
denote n = |V (G)| and m = |E(G)|. Given U ⊆ V (G), we let G[U ] denote the subgraph of G
induced by U , and we let G \ U denote the graph G[V (G) \ U ]. For an edge subset E, we use
V (E) to denote the set of endpoints of edges in E and G[E] to denote the graph (V (E), E). For
X, Y ⊆ V (G), we use E(X) and E(X, Y ) to denote the edge sets {{u, v} ∈ E(G) : u, v ∈ X}
and {{u, v} ∈ E(G) : u ∈ X, v ∈ Y }, respectively. Moreover, we let N (U ) denote the open
neighborhood of G. In case U = {v}, we denote N (v) = N (U ). Given an edge e = {u, v} ∈ E(G),
we use G/e to denote the graph obtained from G by contracting the edge e. In other words, G/e
denotes the graph on the vertex-set (V (G) \ {u, v}) ∪ {x{u,v} }, where x{u,v} is a new vertex, and the
edge-set E(G) = E(G[V (G) \ {u, v}]) ∪ {{x{u,v} , w} | w ∈ N ({u, v})}. A graph H is called a minor
of G, if H can be obtained from G by a sequence of edge deletion, edge contraction and vertex
deletion. In a graph G, a sequence of vertices [u1 u2 . . . uℓ ] is called a path in G, if for any i, j ∈ [ℓ],
i 6= j, ui 6= uj and {ur , ur+1 } ∈ E(G) for all r ∈ [ℓ − 1]. We also call the path P = [u1 u2 . . . uℓ ]
as u1 -uℓ path. The internal vertices of a path P = [u1 u2 . . . uℓ ] are {u2 , u3 , . . . , uℓ−1 }. For a path
←
−
P = [u1 u2 . . . uℓ ], we use P to denote the path [uℓ uℓ−1 . . . u1 ]. For any two paths P1 = [u1 . . . ui ]
and P2 = [ui . . . uℓ ], we use P1 P2 to denote the path [u1 u2 . . . uℓ ]. A sequence of vertices [u1 u2 . . . uℓ ]
is called a cycle in G, if u1 = uℓ , [u1 u2 . . . uℓ−1 ] is a path and {uℓ−1 , uℓ } ∈ E(G). For a path or a
cycle Q, we use V (Q) to denote the set of vertices in Q. Given k ∈ N, we let Kk denote the compete
graph on k vertices. For a set X, we use K[X] to denote the complete graph on X. Given a, b ∈ N,
an a × b grid is a graph on a · b vertices, vi,j for (i, j) ∈ [a] × [b], such that for all i ∈ [a − 1] and
j ∈ [b], it holds that vi,j and vi+1,j are neighbors, and for all i ∈ [a] and j ∈ [b − 1], it holds that
vi,j and vi,j+1 are neighbors. For ease of presentation, for any function f : D → [a] × [b], i ∈ [a]
and j ∈ [b], we use f −1 (i, j), f −1 (∗, j), and f −1 (i, ∗) to denote the sets f −1 ((i, j)), f −1 ((∗, j)), and
f −1 ((i, ∗)), respectively.
A path decomposition is deﬁned as follows.
Definition 2.1. A path decomposition of a graph G is a sequence P = (X1 , X2 , . . . , Xℓ ), where
each Xi ⊆ V (G) is called a bag, that satisﬁes the following conditions.
S
• i∈[ℓ] Xi = V (G).
• For every edge {u, v} ∈ E(G) there exists i ∈ [ℓ] such that {u, v} ⊆ Xi .

• For every vertex v ∈ V (G), if v ∈ Xi ∩ Xj for some i ≤ j, then v ∈ Xr for all r ∈ {i, . . . , j}.
The width of P is maxi∈[ℓ] |Xi | − 1.
The pathwidth of G is the minimum width of a path decomposition of G, and it is denoted
by pw(G). A tree decomposition is a structure more general than a path decomposition, which is
deﬁned as follows.
4

Definition 2.2. A tree decomposition of a graph G is a pair T = (T, β), where T is a tree and β
is a function from V (T ) to 2V (G) , that satisﬁes the following conditions.
S
• x∈V (T ) β(x) = V (G).
• For every edge {u, v} ∈ E(G) there exists x ∈ V (T ) such that {u, v} ⊆ β(x).

• For every vertex v ∈ V (G), if v ∈ β(x) ∩ β(y) for some x, y ∈ V (T ), then v ∈ β(z) for all z
on the unique path between x and y in T .
The width of T is maxx∈V (T ) |β(x)| − 1. Each β(x) is called a bag. Moreover, we let γ(x) denote
the union of the bags of x and its descendants.
In other words, a path decomposition is a tree decomposition where T is a path, but it will be
convenient for us to think of a path decomposition as a sequence using the syntax in Deﬁnition 2.1.
The treewidth of G is the minimum width of a tree decomposition of G, and it is denoted by tw(G).
Proposition 2.3 ([9]). Given a graph G and an integer k, in time 2O(k) · n, we can either decide
that tw(G) > k or output a tree decomposition of G of width 5k.
A nice tree decomposition is a tree decomposition of a form that simpliﬁes the design of dynamic
programming (DP) algorithms. Formally,
Definition 2.4. A tree decomposition T = (T, β) of a graph G is nice if for the root r of T , it
holds that β(r) = ∅, and each node v ∈ V (T ) is of one of the following types.
• Leaf: v is a leaf in T and β(v) = ∅.
• Forget: v has exactly one child u, and there exists a vertex w ∈ β(u) such that β(v) =
β(u) \ {w}.
• Introduce: v has exactly one child u, and there exists a vertex w ∈ β(v) such that β(v) \
{w} = β(u).
• Join: v has exactly two children, u and w, and β(v) = β(u) = β(w).
Proposition 2.5 ([6]). Given a graph G and a tree decomposition T of G, a nice tree decomposition
T ′ of the same width as T can be computed in linear time.
Geometric Graphs. Given a set of geometric objects, O, we say that a graph G represents
O if each vertex in V (G) represents a distinct geometric object in O, and every geometric object in
O is represented by a distinct vertex in V (G). In this case, we abuse notation and write V (G) = O.
The intersection graph of O is a graph G that represent O and satisﬁes E(G) = {{u, v} : u, v ∈ O,
u ∩ v 6= ∅}.
Let P = {p1 = (x1 , y1 ), p2 = (x2 , y2 ), . . . , pn = (xn , yn )} be a set of points in the Euclidean
plane. In the unit disk graph model, for every i ∈ [n], we let di denote the disk of radius 1 whose
centre is pi . Accordingly, we denote D = {d1 , d2 , . . . , dn }. Then, the unit disk graph of D is the
intersection graph of D. Alternatively, the unit disk graph of Dpis the geometric graph of G such
that E(G) = {{pi = (xi , yi ), pj = (xj , yj )} | pi , pj ∈ D, i 6= j, (xi − xj )2 + (yi − yj )2 ≤ 2}. In
the unit square graph model, for every i ∈ [n], we let si denote the axis-parallel unit square whose
centre is pi . Accordingly, we denote S = {s1 , s2 , . . . , sn }. Then, the unit square graph of S is the
intersection graph of S. Alternatively, the unit square graph of S is the geometric graph of G such
that E(G) = {{pi = (xi , yi ), pj = (xj , yj )} | pi , pj ∈ S, i 6= j, |xi − xj | ≤ 1, |yi − yj | ≤ 1}.
5

3

Clique-Grid Graphs

In this section, we introduce a family of “grid-like” graphs, called clique-grid graphs, that is tailored
to ﬁt our techniques. Given a unit disk/square graph G, we extract the properties of G that we
would like to exploit, and show that they can be captured by an appropriate clique-grid graph.
Let us begin by giving the deﬁnition of a clique-grid graph. Roughly speaking, a graph G is a
clique-grid graph if each of its vertices can be embedded into a single cell of a grid (where multiple
vertices can be embedded into the same cell), ensuring that the subgraph induced by each cell is a
clique, and that each cell can interact (via edges incident to its vertices) only with cells at “distance”
at most 2. Formally,
Definition 3.1 (clique-grid graph). A graph G is a clique-grid graph if there exists a function
f : V (G) → [t] × [t′ ], for some t, t′ ∈ N, such that the following conditions are satisﬁed.
1. For all (i, j) ∈ [t] × [t′ ], it holds that f −1 (i, j) is a clique.
2. For all {u, v} ∈ E(G), it holds that if f (u) = (i, j) and f (v) = (i′ , j ′ ) then
|i − i′ | ≤ 2 and |j − j ′ | ≤ 2.
Such a function f is a representation of G.
We note that a notion similar to clique-grid graph was also used by Ito and Kadoshita [32]. For
the sake of clarity, we say that a pair (i, j) ∈ [t] × [t′ ] is a cell. Moreover, whenever we discuss a
clique-grid graph, we assume that we also have the representation. Next, we show that a unit disk
graph is a clique-grid graph.
Lemma 3.2. Let D be a set of points in the Euclidean plane, and let G be the unit disk graph of
D. Then, a representation f of G can be computed in polynomial time.
Proof. Denote xmin = min{xi | pi = (xi , yi ) ∈ D}, xmax = max{xi | pi = (xi , yi ) ∈ D}, ymin =
min{yi | pi = (xi , yi ) ∈ D} and ymax = max{yi | pi = (xi , yi ) ∈ D}. Accordingly, denote b
t =
y
−
y
xmax − xmin
max
min
√
√
and b
t′ =
. If b
t = ⌈b
t⌉, then denote t = b
t + 1, and otherwise denote
2
2
t=b
t. Similarly, if b
t′ = ⌈b
t′ ⌉, then denote t′ = b
t′ + 1, and otherwise denote t′ = b
t′ . Now, deﬁne
xi − xmin
f : V (G) → [t] × [t′ ] as follows. For all pi = (xi , yi ) ∈ V (G), deﬁne ai = ⌊ √
+ 1⌋,
2
yi − ymin
bi = ⌊ √
+ 1⌋ and f (pi ) = (ai , bi ).
2
First, let us verify that Condition 1 in Deﬁnition 3.1 is satisﬁed. To this end, let pi = (xi , yi )
xi − xmin
+ 1⌋ =
and pj = (xj , yj ) be two distinct vertices in V (G) such that f (pi ) = f (pj ). Then, ⌊ √
2
√
xj − xmin
yi − ymin
yj − ymin
⌊ √
+ 1⌋ and ⌊ √
+ 1⌋ = ⌊ √
+ 1⌋. Thus, we have that |xi − xj | < 2 and
2
2 p
2
√
|yi − yj | < 2. In particular, (xi − xj )2 + (yi − yj )2 < 2, which implies that (pi , pj ) ∈ E(G).
Next, let us verify that Condition 2 in Deﬁnition 3.1 is satisﬁed. To this end, let {pi =
(xi , yi ), pj = (xj , yj )} ∈ E(G). Recall that f (pi ) and f (pj ) are denoted by (ai , bi ) and (aj , bj ),
respectively. Thus, to prove that f (pj ) ∈ {(a′ , b′ ) | |ai − a′ | ≤ 2, |bi − b′ | ≤ 2}, it should be shown
that |ai − aj | ≤ 2 and |bi − bj | ≤ 2. By substituting ai , aj , bi and bj , it should be shown that
• |⌊

xj − xmin
xi − xmin
√
√
⌋−⌊
⌋| ≤ 2, and
2
2
6

• |⌊

yj − ymin
yi − ymin
√
⌋| ≤ 2.
⌋−⌊ √
2
2

We focus on the proof of the ﬁrst item, as the proof of the second item is symmetric. Without loss
xj − xmin
xi − xmin
of generality, suppose that xj ≤ xi . Then, it remains to show that ⌊ √
⌋−⌊ √
⌋ ≤ 2.
2
p 2
Since G is the unit disk graph of D and {pi , pj } ∈ E(G), it holds that (xi − xj )2 + (yi − yj )2 ≤ 2.
√
xj − xmin
xj − xmin
xi − xmin
√
In particular, xi − xj ≤ 2. Denote X =
. Then, ⌊ √
⌋−⌊ √
⌋ ≤ ⌊X + 2⌋ −
2
2
2
⌊X⌋ ≤ 2.
Similarly, we show the following.
Lemma 3.3. Let S be a set of points in the Euclidean plane, and let G be the unit square graph
of S. Then, a representation f of G can be computed in polynomial time.
Proof. Denote xmin = min{xi | pi = (xi , yi ) ∈ D}, xmax = max{xi | pi = (xi , yi ) ∈ D}, ymin =
min{yi | pi = (xi , yi ) ∈ D} and ymax = max{yi | pi = (xi , yi ) ∈ D}. Accordingly, denote b
t =
xmax − xmin and b
t′ = ymax − ymin . If b
t = ⌈b
t⌉, then denote t = b
t + 1, and otherwise denote
t=b
t. Similarly, if b
t′ = ⌈b
t′ ⌉, then denote t′ = b
t′ + 1, and otherwise denote t′ = b
t′ . Now, deﬁne
f : V (G) → [t] × [t′ ] as follows. For all pi = (xi , yi ) ∈ V (G), deﬁne ai = ⌊xi − xmin + 1⌋,
bi = ⌊yi − ymin + 1⌋ and f (pi ) = (ai , bi ).
First, let us verify that Condition 1 in Deﬁnition 3.1 is satisﬁed. To this end, let pi = (xi , yi )
and pj = (xj , yj ) be two distinct vertices in V (G) such that f (pi ) = f (pj ). Then, ⌊xi − xmin + 1⌋ =
⌊xj − xmin + 1⌋ and ⌊yi − ymin + 1⌋ = ⌊yj − ymin + 1⌋. Thus, we have that |xi − xj | < 1 and
|yi − yj | < 1, which implies that (pi , pj ) ∈ E(G).
Next, let us verify that Condition 2 in Deﬁnition 3.1 is satisﬁed. To this end, let {pi =
(xi , yi ), pj = (xj , yj )} ∈ E(G). Recall that f (pi ) and f (pj ) are denoted by (ai , bi ) and (aj , bj ),
respectively. Thus, to prove that f (pj ) ∈ {(a′ , b′ ) | |ai − a′ | ≤ 2, |bi − b′ | ≤ 2}, it should be shown
that |ai − aj | ≤ 2 and |bi − bj | ≤ 2. In fact, we will actually prove that |ai − aj | ≤ 1 and |bi − bj | ≤ 1.
By substituting ai , aj , bi and bj , it is suﬃcient to show that
• |⌊xi − xmin ⌋ − ⌊xj − xmin ⌋| ≤ 1, and
• |⌊yi − ymin ⌋ − ⌊yj − ymin ⌋| ≤ 1.
We focus on the proof of the ﬁrst item, as the proof of the second item is symmetric. Without
loss of generality, suppose that xj ≤ xi . Then, it remains to show that ⌊xi − xmin ⌋ − ⌊xj − xmin ⌋ ≤ 1.
Since G is the unit disk graph of D, {pi , pj } ∈ E(G) and xj ≤ xi , it holds that xi − xj ≤ 1. Denote
X = xj − xmin . Then, ⌊xi − xmin ⌋ − ⌊xj − xmin ⌋ ≤ ⌊X + 1⌋ − ⌊X⌋ ≤ 1.
Consequently, we have the following.
Corollary 3.4. Let (G, O, H, k) ((G, O, k)) be an instance of SI (resp. Longest Cycle) on
unit disk/square graphs. Then, in polynomial time, one can output a representation f such that
(G, f, H, k) (resp. (G, f, k)) is an instance of SI (resp. Longest Cycle) on clique-grid graphs
that is equivalent to (G, O, H, k) (resp. (G, O, k)).
We conclude this section by introducing the deﬁnition of an ℓ-NCTD, which is useful for doing
our dynamic programming algorithms.
Definition 3.5. A tree decomposition T = (T, β) of a clique-grid graph G with representation f
is a nice ℓ-clique tree decomposition, or simply an ℓ-NCTD, if for the root r of T , it holds that
β(r) = ∅, and for each node v ∈ V (T ), it holds that
7

• There exist at most ℓ cells, (i1 , j1 ), . . . , (iℓ , jℓ ), such that β(v) =
• The node v is of one of the following types.

Sℓ

t=1 f

−1 (i , j ),
t t

and

– Leaf: v is a leaf in T and β(v) = ∅.

– Forget: v has exactly one child u, and there exists a cell (i, j) ∈ [t] × [t′ ] such that
f −1 (i, j) ⊆ β(u) and β(v) = β(u) \ f −1 (i, j).
– Introduce: v has exactly one child u, and there exists a cell (i, j) ∈ [t] × [t′ ] such that
f −1 (i, j) ⊆ β(v) and β(v) \ f −1 (i, j) = β(u) \ f −1 (i, j).

– Join: v has exactly two children, u and w, and β(v) = β(u) = β(w).

A nice ℓ-clique path decomposition, or simply an ℓ-NCPD, is an ℓ-NCTD where T is a path. In
this context, for convenience, we use the notation referring to a sequence presented in Section 2.

4

The Cell Graph of a Clique-Grid Graph

In this section, we introduce two compact representations of clique-grid graphs. By examining
these representations, we are able to infer information on the structure of clique-grid graphs that
are also unit disk/square graphs.
Definition 4.1 (backbone). Given a clique-grid graph G with representation f : V (G) → [t] × [t′ ],
an induced subgraph H of G is a backbone for (G, f ) if for every two distinct cells (i, j), (i′ , j ′ ) ∈
[t] × [t′ ] for which there exist u ∈ f −1 (i, j) and v ∈ f −1 (i′ , j ′ ) such that {u, v} ∈ E(G), there also
exist u′ ∈ f −1 (i, j) and v ′ ∈ f −1 (i′ , j ′ ) such that {u′ , v ′ } ∈ E(H). If no induced subgraph of H is a
backbone for (G, f ), then H is a minimal backbone for (G, f ).
First, we bound the maximum degree of a minimal backbone.
Lemma 4.2. Let G be a clique-grid graph with representation f , and let H be a minimal backbone
for (G, f ). Then, for all (i, j) ∈ [t] × [t′ ], it holds that |f −1 (i, j) ∩ V (H)| ≤ 24. Furthermore, the
maximum degree of H is at most 599.
Proof. By Condition 2 in Deﬁnition 3.1, we have that for all cells (i, j) ∈ [t] × [t′ ], it holds that
f −1 (i, j) ∩ V (H) ≤ |{(i′ , j ′ ) ∈ [t] × [t′ ] \ {(i, j)} | |i − i′ | ≤ 2, |j − j ′ | ≤ 2}| ≤ 24. Thus, for all
(i, j) ∈ [t] × [t′ ], the degree in H of a vertex in f −1 (i, j) ∩ V (H) is bounded by
[
|(
f −1 (i, j) ∩ V (H)) \ {v}| ≤ |{(i′ , j ′ ) ∈ [t] × [t′ ] | |i − i′ | ≤ 2, |j − j ′ | ≤ 2}| · 24 − 1
(i′ ,j ′ )∈[t]×[t′ ]
|i−i′ |≤2
|j−j ′|≤2

= 25 · 24 − 1 = 599

Note that it is easy to compute a minimal backbone. The most naive computation simply
initializes H = G; then, for every vertex v ∈ V (G), it checks if the graph H \ {v} has the same
backbone as H, in which case it updates H to H \ {v}. Thus, we have the following.
Observation 4.3. Given a clique-grid graph G with representation f , a minimal backbone H for
(G, f ) can be computed in polynomial time.
To analyze the treewidth of a backbone, we need the following.1
1
The paper [25] does not consider unit square graphs, but the arguments it presents for unit disk graphs can be
adapted to handle unit square graphs as well.

8

tw
tw
Proposition 4.4 ([25]). Any unit disk/square graph with maximum degree ∆ contains a
×
3
100∆
100∆3
grid as a minor.
Thus, we have the following.
Lemma 4.5. Given a clique-grid graph G that is a unit disk/square graph, a representation f of
G and an integer ℓ ∈ N, in time 2O(ℓ) · nO(1) , one can either correctly conclude that G contains
ℓ
ℓ
×
grid as a minor, or obtain a minimal backbone H for (G, f ) with a nice
a
3
100 · 599
100 · 5993
tree decomposition T of width at most 5k.
Proof. By Lemma 4.2, Observation 4.3 and Proposition 4.4, in polynomial time, one can compute
ℓ
ℓ
a minimal backbone of H such that H either contains a
×
grid as a minor or
3
100 · 599
100 · 5993
has treewidth at most ℓ. Since H is a subgraph of G, it holds that if H contains an a × b grid
as a minor, then G also contains an a × b grid as a minor. Thus, by Propositions 2.5 and 2.3, we
conclude the proof of the lemma.
√
We use Lemma 4.5 with ℓ = O( k). Next, we deﬁne a more compact representation of a
clique-grid graph.
Definition 4.6 (cell graph). Given a clique-grid graph G with representation f : V (G) → [t] × [t′ ],
the cell graph of G, denoted by cell(G), is the graph on the vertex-set {vi,j : i ∈ [t], j ∈ [t′ ], f −1 (i, j) 6=
∅} and edge-set {{vi,j , vi′ ,j ′ } : (i, j) 6= (i′ , j ′ ), ∃u ∈ f −1 (i, j)∃v ∈ f −1 (i′ , j ′ ) such that {u, v} ∈
E(G)}.
By Deﬁnitions 4.1 and 4.6, we directly conclude the following.
Observation 4.7. For a clique-grid graph G, a representation f of G and a backbone H for (G, f ),
it holds that cell(G) is a minor of H.
Since for any graph G and a minor H of G, it holds that tw(H) ≤ tw(G), we have the following.
Observation 4.8. For a clique-grid graph G, a representation f of G and a backbone H for (G, f ),
it holds that tw(cell(G)) ≤ tw(H).
Overall, from Lemma 4.5 and Observation 4.8, we directly have the following.
Lemma 4.9. Given a clique-grid graph G that is a unit disk/square graph, a representation f of
G and an integer ℓ ∈ N, in time 2O(ℓ) · nO(1) , one can either correctly conclude that G contains a
ℓ
ℓ
×
grid as a minor, or compute a nice tree decomposition of cell(G) of width
3
100 · 599
100 · 5993
at most 5ℓ.
Note that a nice tree decomposition of cell(G) of width 5ℓ corresponds to a 5ℓ-NCTD of G. In
other words, Lemma 4.9 implies the following.
Corollary 4.10. Given a clique-grid graph G that is a unit disk/square graph, a representation f
of G and an integer ℓ ∈ N, in time 2O(ℓ) · nO(1) , one can either correctly conclude that G contains
ℓ
ℓ
×
grid as a minor, or compute a 5ℓ-NCTD of G.
a
3
100 · 599
100 · 5993

9

5

Turing Kernels

For the sake of uniformity, throughout this section, we denote an instance (G, O, k) ((G, f, k))
of Longest Cycle on unit disk/square graphs (resp. clique-grid graphs) also by (G, O, H, k)
(resp. (G, f, H, k)) where H is the empty graph. Our objective is to show that both SI and Longest
Cycle on unit disk/square graphs admit a Turing kernel. More precisely, we prove the following.
Theorem 5.1. Let (G, O, H, k) be an instance of SI ( Longest Cycle) on unit disk/square graphs.
Then, in polynomial time, one can output a set I of instances of SI (resp. Longest Cycle) on
unit disk/square graphs such that (G, O, H, k) is a Yes-instance if and only if at least one instance
b O,
b H,
b b
b = O(k3 ), |E(G)|
b = O(k4 ),
in I is a Yes-instance, and for all (G,
k) ∈ I, it holds that |V (G)|
b
b
H = H and k = k.
To prove Theorem 5.1, we ﬁrst need two deﬁnitions.

Definition 5.2. Let G be a clique-grid graph with representation f : V (G) → [t] × [t′ ], H ′ be a
subgraph of G, and ℓ ∈ N. We say that H ′ is ℓ-stretched if there exist cells (i, j), (i′ , j ′ ) ∈ [t] × [t′ ]
such that the following conditions are satisﬁed.
• It holds that |i − i′ | ≥ 2ℓ or |j − j ′ | ≥ 2ℓ (or both).
• It holds that V (H ′ ) ∩ f −1 (i, j) 6= ∅ and V (H ′ ) ∩ f −1 (i′ , j ′ ) 6= ∅.
Definition 5.3. Let I = (G, f : V (G) → [t] × [t′ ], k) be an instance of Longest Cycle on cliquegrid graphs. We say that I is a stretched instance if G has a cycle C that is ℓ-stretched for some
ℓ ≥ 2k.
We proceed by proving two claims concerning solutions to Longest Cycle and SI on cliquegrid graphs.
Lemma 5.4. Let I = (G, f : V (G) → [t] × [t′ ], H, k) be an instance of SI on clique-grid graphs.
Then, for any subgraph H ′ of G that is isomorphic to H, it holds that H ′ is not 2k-stretched.
S
Proof. Let H ′ be a subgraph of G that is isomorphic to H. Denote imin = min{i ∈ [t] : ( j∈[t′ ] f −1 (i, j))∩
S
V (H ′ ) 6= ∅}, imax = max{i ∈ [t] : ( j∈[t′ ] f −1 (i, j)) ∩ V (H ′ ) 6= ∅}, jmin = min{j ∈ [t′ ] :
S
S
( i∈[t] f −1 (i, j)) ∩ V (H ′ ) 6= ∅} and jmax = max{j ∈ [t′ ] : ( i∈[t] f −1 (i, j)) ∩ V (H ′ ) 6= ∅}. To
prove that H ′ is not 2k-stretched, we need to prove that imax − imin < 2k and jmax − jmin < 2k.
We only prove that imax − imin < 2k, as the proof that jmax − jmin < 2k is symmetric.
S
Let i1 < i2 < · · · < iℓ for the appropriate ℓ be the set of indices i ∈ [t] such that j∈[t′ ] f −1 (i, j))∩
V (H ′ ) 6= ∅}. Note that i1 = imin and iℓ = imax . We claim that for all r ∈ [ℓ − 1], it holds that
ir+1 − ir ≤ 2. Suppose, by way of contradiction, that there exists r ∈ [ℓ − 1] such that ir+1 − ir > 2.
Recall that H is a connected graph, and therefore H ′ is also a connected graph.
there exists
S Thus,−1
′
′
an edge {u, v} ∈ E(H ) ⊆ E(G) and indices i ≤ ir and i ≥ ir+1 such that u ∈ j∈[t′ ] f (i, j)) and
S
v ∈ j∈[t′ ] f −1 (i′ , j)). However, this contradicts the fact that f is a representation of G.
Now, since for all r ∈ [ℓ − 1], we proved that ir+1 − ir ≤ 2, we have that that there exist at
S
imax − imin
+ 1 indices i ∈ [t] such that j∈[t′ ] f −1 (i, j)) ∩ V (H ′ ) 6= ∅. However, |V (H)| ≤ k.
least
2
imax − imin
+ 1 ≤ k, which implies that imax − imin < 2k.
Therefore
2
Lemma 5.5. Let I = (G, f : V (G) → [t]×[t′ ], k) be an instance of Longest Cycle on clique-grid
graphs. Then, it can be determined in polynomial time whether I is a stretched instance, in which
case it is also a Yes-instance.
10

Proof. It is well known that for any given graph and pair of vertices in this graph, one can determine
(in polynomial time) whether the given graph has a cycle that contains both given vertices by
checking whether there exists a ﬂow of size 2 between them (see, e.g., [5]). Thus, by considering
every pair (u, v) of vertices in V (G) such that |i − i′ | ≥ 2k or |j − j ′ | ≥ 2k (or both) where
f (u) = (i, j) and f (v) = (i′ , j ′ ), we can determine (in polynomial time) whether I is a stretched
instance.
Now, suppose that I is a stretched instance. Then, G has a cycle C that is ℓ-stretched for some
ℓ ≥ 2k. Note that I ′ = (G, f, C, |V (C)|) is a Yes-instance of SI on clique-grid graphs. Thus, by
Lemma 5.4, it holds that C is not 2|V (C)|-stretched. Therefore, ℓ < 2|V (C)|, and since ℓ ≥ 2k, we
conclude that k < |V (C)|. Thus, I is a Yes-instance.
Next, we prove a statement similar to the one of Theorem 5.1, but which concerns clique-grid
graphs. Our method is inspired by Baker’s technique [3].
Lemma 5.6. Let I = (G, f : V (G) → [t] × [t′ ], H, k) be an instance of SI ( Longest Cycle) on clique-grid graphs. Then, in polynomial time, one can output a set I of instances of
SI (resp. Longest Cycle) on clique-grid graphs such that (G, f, H, k) is a Yes-instance if and
b fb : V (G)
b → [b
b b
only if at least one instance in I is a Yes-instance, and for all (G,
t] × [b
t′ ], H,
k) ∈ I,
′
−1
b
b
b
b
b
b
it holds that G is either an induced subgraph of G or Kbk , t, t ≤ 2k = O(k), |f (i, j)| < k for any
b = H and b
cell (i, j) ∈ [t] × [t′ ], H
k = k.
Proof. First, suppose that there exists a cell (i, j) ∈ [t] × [t′ ] such that |f −1 (i, j)| ≥ k, then by
Deﬁnition 3.1, G[f −1 (i, j)] is a clique on at least k vertices. In particular, the pattern H is a
subgraph of G[f −1 (i, j)], and therefore it is also a subgraph of G. Thus, in this case, we conclude
the proof by setting I to be the set that contains only one instance, (Kk , fb : V (Kk ) → [1]×[1], H, k).
From now on, suppose that for all cells (i, j) ∈ [t] × [t′ ], it holds that |f −1 (i, j)| < k.
Second, in case the input instance I is of Longest Cycle, we use the computation given
by Lemma 5.5 to determine whether I is a stretched instance. If the answer is positive, then by
Lemma 5.5, it holds that I is a Yes-instance. In this case, we again conclude the proof by setting
I to be the set that contains only one instance, (Kk , fb : V (Kk ) → [1] × [1], H, k). From now on,
also suppose that if the input instance I is of Longest Cycle, then it is not stretched .
Now, our kernelization algorithm works as follows. For every (p, q) ∈ [t] × [t′ ], it computes
[
Gp,q = G[
f −1 (i, j)].
p≤i<min{p+2k,t+1}
q≤j<min{q+2k,t′ +1}

Accordingly, it computes fp,q : V (Gp,q ) → [min{2k, t}] × [min{2k, t′ }] as follows. For every v ∈
V (Gp,q ), compute fp,q (v) = (i − p + 1, j − q + 1) where (i, j) = f (v). Note that for all (i, j) ∈
−1 (i, j) = f −1 (i + p − 1, j + q − 1). Thus, since f is
[min{2k, t}] × [min{2k, t′ }], it holds that fp,q
a representation of G, it holds that fp,q is a representation of Gp,q . Finally, our kernelization
algorithm outputs I = {Ip,q = (Gp,q , fp,q , H, k) : (p, q) ∈ [t] × [t′ ]}.
To conclude the proof, it remains to show that (G, f, H, k) is a Yes-instance if and only if at
least one instance in I is a Yes-instance. Since for all (Gp,q , fp,q , H, k) ∈ I, it holds that Gp,q is
an induced subgraph of G, we have that if (G, f, H, k) is a No-instance, then every instance in I is
No-instance as well. Next, suppose that (G, f, H, k) is a Yes-instance. Let us consider two cases.
• (G, f, H, k) is an instance of SI. Then,
H ′ be a subgraph of G that is isomorhpic to
S let −1
H. Denote imin = min{i ∈ [t] : ( j∈[t′ ] f (i, j)) ∩ V (H ′ ) 6= ∅}, imax = max{i ∈ [t] :
S
S
( j∈[t′ ] f −1 (i, j)) ∩ V (H ′ ) 6= ∅}, jmin = min{j ∈ [t′ ] : ( i∈[t] f −1 (i, j)) ∩ V (H ′ ) 6= ∅} and
11

S
jmax = max{j ∈ [t′ ] : ( i∈[t] f −1 (i, j)) ∩ V (H ′ ) 6= ∅}. By Lemma 5.4, it holds that both
imax − imin < 2k and jmax − jmin < 2k. Therefore, H ′ is a subgraph of Gimin ,jmin , which
implies that Ip,q is a Yes-instance.
• (G, f, H, k) is an instance of Longest Cycle. Then, Slet C be a subgraph of G that is a
cycle on at least k vertices. Denote imin = min{i ∈ [t] : ( j∈[t′ ] f −1 (i, j)) ∩ V (C) 6= ∅}, imax =
S
S
max{i ∈ [t] : ( j∈[t′ ] f −1 (i, j))∩V (C) 6= ∅}, jmin = min{j ∈ [t′ ] : ( i∈[t] f −1 (i, j))∩V (C) 6= ∅}
S
and jmax = max{j ∈ [t′ ] : ( i∈[t] f −1 (i, j)) ∩ V (C) 6= ∅}. Since (G, f, H, k) is not stretched,
it holds that both imax − imin < 2k and jmax − jmin < 2k. Therefore, C is a subgraph of
Gimin ,jmin , which implies that Ip,q is a Yes-instance.
Towards proving Theorem 5.1, we extract a claim that is reused in Sections 6 and 7.
Corollary 5.7. Let (G, O, H, k) be an instance of SI ( Longest Cycle) on unit disk/square
graphs. Then, in polynomial time, one can output a set I of instances of SI (resp. Longest
Cycle) on clique-grid graphs such that (G, O, H, k) is a Yes-instance if and only if at least one
b fb, H,
b b
b is either an induced
instance in I is a Yes-instance, and for all (G,
k) ∈ I, it holds that G
′
−1
′
b = H and b
subgraph of G or Kbk , b
t, b
t = O(b
k), |fb (i, j)| < b
k for any cell (i, j) ∈ [b
t] × [b
t ], H
k = k.

Proof. First, by Corollary 3.4, we obtain (in polynomial time) an instance (G, f, H, k) of SI
(Longest Cycle) on clique-grid graphs that is equivalent to (G, O, H, k). Then, by Lemma 5.6
with (G, f, H, k), we obtain (in polynomial time) the desired set I.
We are now ready to prove Theorem 5.1.

Proof of Theorem 5.1. First, by Corollary 5.7, we obtain (in polynomial time) a set I of
instances of SI (Longest Cycle) on clique-grid graphs such that (G, O, H, k) is a Yes-instance
b fb, H,
b b
if and only if at least one instance in I is a Yes-instance, and for all (G,
k) ∈ I, it holds that
′
2
−1
b
b
b
b
t, b
t = O(k ), |f (i, j)| ≤ k for a cell (i, j) ∈ [b
t] × [b
t′ ],
G is either an induced subgraph of G or Kbk , b
b = H and b
H
k = k. Thus, to conclude our proof, it is suﬃcient to show that for any instance
b
b
b
b
(G, f , H, k) ∈ I, we can compute (in polynomial time) an equivalent instance (G′ , O′ , H ′ , k′ ) of SI
(Longest Cycle) on unit disk/square graphs such that |O′ | = O(k′3 ), H ′ = H and k′ = k. To this
b fb, H,
b b
b is equal to Kb .
end, ﬁx some instance (G,
k) ∈ I. Let us ﬁrst handle the simple case where G
k
′
Here, we conclude the proof by deﬁning pi = (0, i/k) for i ∈ [k], and then setting O ′ = {p′i : i ∈ [k]}.
b is an induced subgraph of G. Then, we have that V (G)
b ⊆ O, and the
Now, suppose that G
′
′
′
′
b
b
b
b H,
b b
unit disk/square graph of V (G) is exactly G. Thus, we deﬁne (G , O , H , k ) = (G, V (G),
k). It
3
4
b
b
remains to show that |V (G)| = O(k ),|E(G)| = O(k ).
By Deﬁnition 3.1, it holds that
X
b =
|V (G)|
|f −1 (i, j)|.
(i,j)∈[b
t]×[b
t′ ]

b = O(k3 ).
Thus, since b
t, b
t′ = O(k) and |fb−1 (i, j)| ≤ k for (i, j) ∈ [b
t] × [b
t′ ], we have that |V (G)|
Now, denote X = {((i, j), (i′ , j ′ )) : i, i′ ∈ [t], j, j ′ ∈ [t′ ], |i−i′ | ≤ 2, |j −j ′ | ≤ 2}. Since b
t, b
t′ = O(k),
2
we have that |X| = O(k ). By Deﬁnition 3.1, it also holds that
X
b ≤
|E(G)|
|f −1 (i, j)| · |f −1 (i′ , j ′ )|.
((i,j),(i′ ,j ′ ))∈X

b = O(k4 ).
Thus, since |X| = O(k2 ), and |fb−1 (i, j)| ≤ k for (i, j) ∈ [b
t] × [b
t′ ], we have that |E(G)|
12

6

Exact k-Cycle

In this section we prove the following theorem.
√

Theorem 6.1. Exact k-Cycle on unit disk/square graphs can be solved in 2O(
time.

k log k)

· nO(1)

Towards proving Theorem 6.1, we design an algorithm which given a clique-grid graph G
along
with its representation f : V (G) → [t] × [t′ ] and an integer k as input, runs in time
√
k
log
k) |V (G)|O(1) and decides whether G has a cycle of length k or not. In Section 5 (Lemma 5.6)
O(
2
we have seen that SI admits a polynomial
sized Turing kernel on clique-grid graphs. Hence to give
√
an algorithm of running time 2O( k log k) |V (G)|O(1) , we can restrict to instances of size bounded
by polynomial in k. More precisely, because of Lemma 5.6, we can assume that the input to our
algorithm is (G, f : V (G) → [t] × [t′ ], k) where G is a clique-grid graph with a representation f ,
|f −1 (i, j)| < k for all (i, j) ∈ [t] × [t′ ] and t, t′ ≤ 2k. Without loss of generality we can assume that
f is a function from V (G) to [2k] × [2k], because [t] × [t′ ] ⊆ [2k] × [2k].
Given an instance (G, f : V (G) → [2k] × [2k], k), √
the algorithm applies a method inspired by
k log k) instances of Exact k-Cycle. The
O(
Baker’s technique [3] and obtains a family, F , of 2
family F has following properties.
1. In each of these instances the input graph is an induced subgraph of G and has size kO(1) .
2. The input (G, f : V (G) → [2k] × [2k], k) is a Yes-instance if and only if there exists an
instance (H, f ∗ : V (H) → [2k] × [2k], k) ∈ F which is a Yes-instance.
√
3. More over, for any instance
(H, f ∗ : V (H) → [2k] × [2k], k) ∈ F , H has a nice 7 k-clique
√
path decomposition (7 k-NCPD).
We will call the family F satisfying the above properties as good√ family. Let (H, f ∗ : V (H) →
[2k] × [2k], k) be an instance of F . Let P = (X1 , . . . , Xq ) be a 7 k-NCPD of H. We ﬁrst prove
that if there is a cycle of length k in H, then there is a cycle C of length k in H such that for
any two distinct cells (i, j) and (i′ , j ′ ) of f , the number of edges with one end point in (i, j) and
other in (i′ , j ′ ) is at most 4. Let C be such a cycle in H. Then using the property of C we get the
following important property.
For any i ∈ [q], the number of edges of V (C) with one end point in Xi and other in
√
is upper bounded by O( k).

S

i<j≤q

Xj

The above mentioned property allows us to design√a dynamic programming (DP) algorithm
√
over 7 k-NCPD, P, for Exact k-Cycle in time 2O( k log k) . Now we are ready to give formal
details about the algorithm. As explained before, we assume that the number of vertices in the
input graph is bounded by kO(1) .
Lemma 6.2. Let (G, f : V (G) → [2k] × [2k], k) be an instance of Exact k-Cycle, where G is a
clique-grid graph with representation f , |f −1 (i, j)| < k for all (i, j) ∈ [2k] × [2k] √
and |V (G)| = k O(1) .
O(
k log k) that outputs
Given (G, f : V (G) → [2k] × [2k], k), there is an algorithm running in time 2
a good family F .

13

Proof. Let C be a k length cycle in G. First we deﬁne a column of the 2k ×2k grid. For any j ∈ [2k]
the set of cells {(i, j) : i ∈ [2k]} is called a column. There are 2k columns for the 2k × 2k grid. We
partition 2k columns of√the 2k × 2k grid with k blocks of two consecutive columns and label them
is labelled
from the set √
of labels [ k]. That is, each pair of columns 2i − 1 and 2i, where i ∈ [k] √
and 2i are labelled with i mod k. Then
with i mod k. In other words both column 2i − 1 √
by pigeon hole principle there is a label ℓ ∈ {1, 2,
.
.
.
,
k} such that the number of vertices from
√
V (C) which are in columns labelled ℓ is at most k. As |V (G)| ≤ kO(1) , the number of vertices of
G in columns labelled ℓ is at most kO(1) . We guess the vertices of
V (C) which are in the columns
√
O(
k)
labelled ℓ. The number of potential guesses is bounded by k
. Let Y√be the set of guessed
vertices of V (C) which are in the columns labelled by ℓ. Notice that |Y | ≤ k. Then we delete all
the vertices in columns labelled ℓ, except the vertices of Y . Let S be the set of deleted vertices. By
the property 2 of clique-grid graph, G\(S ∪Y ) is a disjoint union of clique-grid graphs each of which
√
S2(ℓ−1)
is represented by a function with at most 2 k columns. That is, let G1 = G[ j=1 f −1 (∗, j)], and
√
√
Smin{i·2ℓ+2 k,2k} −1
Gi+1 = G[ j=i·2ℓ+1
f (∗, j)] for all i ∈ {1, . . . , ⌈ k⌉}. Notice that Gi is clique-grid graph
√
with representation fi : V (Gi ) → [2k]×[2 k] deﬁned as, fi (u) = (r, j), when f (u) = (r, (i−1)2ℓ+j).
By the property 2 of clique-grid graph, G \ (S ∪ Y ) = G1 ⊎ . . . ⊎ G⌈√k⌉+1 .
√
√
Claim 6.3. G \ S has a nice 7 k-clique path decomposition (7 k-NCPD).
√
Proof. First, for each i ∈ {1,
√
√ . . . , ⌈ k⌉ + 1}, we deﬁne a path decomposition of Gi such that each
bag is a union of at most 6 k many cells of fi . As G \ (S ∪ Y ) = G1 ⊎ . . . ⊎ G⌈√k⌉−1 , and |Y | ≤ k,
√
by adding Y to each bag of all path decompositions we can get a required nice 7 k-clique path
decomposition for G \ S.
Now, for each Gi , we deﬁne a path decomposition Pi = (Xi,1 , Xi,2 , . . . Xi,2k−2 ) where Xi,j =
fi−1 (j, ∗) ∪ fi−1 (j + 1, ∗) ∪ fi−1 (j + 2, ∗). We claim that Pi is indeed a path decomposition of
Sk−1
Gi . Notice that j=1
Xi,j = fi−1 (∗, ∗) = V (Gi ). By property 2 of clique-grid graph, we have
that for each edge {u, v} ∈ E(G), there exists j ∈ [2k − 2] such that {u, v} ∈ Xi,j . For each
u ∈ V (G), u is contained in at most three bags and these bags are consecutive in the sequence
(Xi,1 , Xi,2 , . . . Xi,2k−2 ). Hence Pi is a path decomposition of√Gi . Since Xi,j = fi−1 (j, ∗) ∪ fi−1 (j +
1, ∗) ∪ fi−1 (j + 2, ∗), number
of columns in fi is at most 2 k and each cell of fi is a cell of f ,
√
each Xi,j is a union of 6 k many cells of f . Since G \ (S ∪ Y ) = G1 ⊎ . . . ⊎ G⌈√k⌉+1 , the sequence
P ′ = (X1,1 , . . . X1,2k−2 , X2,1 , . . . X2,2k−2 , . . . , X⌈√k⌉−1,1 , . . . X⌈√k⌉−1,2k−2 ) is a path decomposition of
√
G \ (S ∪ Y ). More√over, the vertices of each bag is a union of vertices from at most 6 k cells of f .
Also, since |Y | ≤ k, the sequence P = (X1,1 ∪ Y, . . . X1,k−2 ∪ Y, . . . X⌈√k⌉−1,k−2 ∪ Y ) obtained by
adding Y to each bag of P ′ we get a path decomposition
of G \ S. More over, the vertices of each
√
bag in P√is a union of vertices from at most 7 k cells of f . We can turn the path decomposition
P to a 7 k-NCPD by an algorithm similar to the one mentioned in Proposition 2.5.
√
Our algorithm will construct a family F as follows. For each ℓ ∈ {1, . . . , ⌈ k⌉} and for two
subsets√ of vertices S and Y such that S ∪ Y is a set of vertices in the columns labelled ℓ and
|Y | ≤ k, our algorithm will include an instance (G \ S, f |V (G)\S , k) in F . The number of choices
√

√

of S and Y is bounded by 2O( k log k) and thus the size of F is bounded by 2O( k log k) .
We claim that F is indeed a good family.
√ C of length k in G. Then, by
√ Suppose there is a cycle
pigeon hole principle there is ℓ ∈ {1, . . . , ⌈ k⌉} such that at most k vertices from V (C) are in the
columns labelled by ℓ. Let S ′ be the√set of vertices in the columns labelled by ℓ. Let Y = S ′ ∩ V (C)
and S = S ′ \ Y . Notice that |Y | ≤ k. The instance (G \ S, f |V (G)\S , k) in F , is a Yes instance.
This completes the proof of the lemma.
14

ur
•

vr
•

ur
•

vr
•

•
ur ′

•
vr ′

•
ur′

•
vr′

Figure 1: Illustration of Lemma 6.4. Figure on the left is the cycle C = [ur vr ]Q1 [ur′ vr′ ]Q2 and the
←
−
one on the right is the cycle C ′ = [ur ur′ ] Q 1 [vr vr′ ]Q2
Now we can assume that we are solving Exact k-Cycle on (H, f, k), where (H, f, k) ∈ F
(here we rename the function f |V (H) with f for ease of presentation). Now we prove that if there
is a cycle of length k in H, then there is a cycle C of length k in H such that for any two cells
(i, j) and (i′ , j ′ ) of f , the number of edges of E(C) with one end point in (i, j) and other (i′ , j ′ ) is
at most 5.
Lemma 6.4. Let (H, f : V (H) → [2k] × [2k], k) be a Yes instance of Exact k-Cycle. Then
there is a cycle C of length k in H such that for any two distinct cells (i, j) and (i′ , j ′ ) of f , the
number of edges of E(C) with one end point in (i, j) and other (i′ , j ′ ) is at most 5.
Proof. Let C be a k length cycle such that the number edges of E(C) whose end points are in
diﬀerent cells is minimized. We claim that for any two disjoint cells (i, j) and (i′ , j ′ ), the number
of edges of E(C) with one end point in (i, j) and other (i′ , j ′ ) is at most 4. Suppose not. Then
there exist (i, j) and (i′ , j ′ ) such that the number of edges of E(C) with one end point in (i, j) and
other in (i′ , j ′ ) is at least 6. Let C = P1 [u1 v1 ]P2 [u2 v2 ]P3 [u3 v3 ]P4 [u4 v4 ]P5 [u5 v5 ]P6 [u6 v6 ] where for
each {ur , vr }, r ∈ [6], one end point is in the cell (i, j) and other in the cell (i′ j ′ ), and each subpath
Pℓ , ℓ ∈ [6], can be empty too. Since C is a cycle, at least 3 edges from {{ur , vr } : i ∈ [6]} form a
matching. Let {ur1 , vr1 }, {ur2 , vr2 } and {ur3 , vr3 } be a matching of size 3, where {r1 , r2 , r3 } ⊆ [6].
Then, by pigeon hole principle there exist r, r ′ ∈ {r1 , r2 , r3 } such that either ur , ur′ ∈ f −1 (i, j) or
ur , ur′ ∈ f −1 (i′ , j ′ ). Without loss of generality assume that ur , ur′ ∈ f −1 (i, j) (otherwise we rename
cell (i, j) with (i′ , j ′ ) and vice versa). That is, C = [ur vr ]Q1 [ur′ vr′ ]Q2 such that ur , ur′ ∈ f −1 (i, j)
←
−
and vr , vr′ ∈ f −1 (i′ , j ′ ). Then, since f −1 (i, j) and f −1 (i′ , j ′ ) are cliques, C ′ = [ur ur′ ] Q 1 [vr vr′ ]Q2 is
a k length cycle in G, such that the number edges of E(C ′ ) whose end points are in diﬀerent cells
is less than that of E(C), which is contradiction to our assumption. See Fig. 1 for an illustration
of C and C ′ . This completes the proof of the lemma.
Next we design a DP algorithm that ﬁnds a cycle of length k, if it exists, satisfying properties
of Lemma 6.4.
Lemma
√ 6.5. Let (H, f : V (H) → [2k] × [2k], k) ∈ F be an instance of Exact k-Cycle and P
be a 7 k-NCPD of H. √Then, given (H, f : V (H) → [2k] × [2k], k) and P, there is an algorithm A
which runs in time 2O( k log k) , and outputs Yes, if there is a cycle C in H such that for any two
distinct cells (i, j) and (i′ , j ′ ) of f , the number of edges with one end point in (i, j) and other (i′ , j ′ )
is at most 5. Otherwise algorithm A will output No.

15

√
Proof. Algorithm A is a DP algorithm overSthe 7 k-NCPD P = (X1 , . . . Xq ) of H. For any ℓ ∈ [q],
we deﬁne Hℓ be the induced subgraph H[ i≤ℓ Xi ] of H. Deﬁne C to be the set of k length cycles
in H such that for any C ∈ C and two disjoint cells (i, j) and (i′ , j ′ ) of f , the number of edges
of√E(C) with one end point in (i, j) and other (i′ , j ′ ) is at most 5. Let C ∈ C. Since P is a
7 k-NCPD and the fact that for any two distinct cells (i, j) and (i′ , j ′ ) of f , the number of edges
of C with one end point in (i, j) and other (i′ , j ′ ) is at most 5, we have that for any bag Xℓ of
√ P,
the number of vertices of V (C)√∩ Xℓ which has a neighbour in V (H) \ Xℓ is bounded by O( k).
This allows us to keep only 2O( k log k) states in the DP algorithm. Fix any ℓ ∈ [q] and deﬁne CL
the set of paths of C (or the cycle C itself) when we restrict
C to Hℓ . That is CL = Hℓ [E(C)]. Let
bL = {{u, v} | there is a u-v path in CL }. Notice that S b P is the set of vertices of degree 0
C
P ∈CL
√
S
or 1 in CL and P ∈CbL P ⊆ Xℓ . Since Xℓ is a union of vertices from at most 7 k many cells of
f and for any two distinct cells (i, j) and (i′ , j ′ ) of f , the number of edges of E(C) with one end
′ ′
point in (i, j) and other
√ 2 of the clique-grid graph, we have
√ property
S (i , j ) is at most 5, and by
that the cardinality of P ∈CbL P is at most 5 · 24 · 7 k = 840 k. In our DP algorithm we will have
bL , |E(CL )|) which will be set to 1. Formally, for any ℓ ∈ [q], k′ ∈ [k] and a
state indexed by (ℓ, C
family
Z of vertex disjoint
that the cardinality of
√ sets of size at most 2 of Xℓ with the property
S
′
Z∈Z Z is at most 840 k, we will have a DP table entry A[ℓ, Z, k ]. For each ℓ ∈ [q], we maintain
the following correctness invariant.
bL =
Correctness Invariants: (i) For every C ∈ C, let CL = Hℓ [E(C)] and C
{{u, v} | there is a connected component P in CL and P is a u-v path as well}. Then
bL , |E(CL )|] = 1, (ii) for any family Z of vertex disjoint sets of size at most 2 of
A[ℓ, C
√
S
Xℓ with 0 < | Z∈Z Z| ≤ 840 k, k′ ∈ [k], and A[ℓ, Z, k′ ] = 1, there is a set Q of |Z|
vertex disjoint paths in Hℓ where the end points of each path are speciﬁed by a set in
Z and |E(Q)| = k′ , and (iii) If A[ℓ, ∅, k] = 1, then there is a cycle of length k in Hℓ .
The correctness of the our algorithm will follow from the correctness invariant. Before explaining
the computation of DP table entries, we ﬁrst deﬁne some notations. Fix ℓ ∈ [q]. For any C ∈ C,
deﬁne CL = Hℓ [E(C)] and CR = H[E(C) \ E(CL )]. For any family Q of vertex disjoint paths
b = {{u, v} | there is a u-v path in Q}. That is, for any C ∈ C,
with end points in Xℓ , deﬁne Q
b
CL = {{u, v} | there is a u-v path in CL }. Now we explain how to compute the values A[·, ·, ·]. In
′
′
what follows we explain how to compute A[ℓ,
√ ℓ ∈ [q], k ∈ [k] and family Z of vertex
S Z, k ] for every
disjoint sets of size at most 2 of Xℓ with | Z∈Z Z| ≤ 840 k, the running to compute it from the
previously computed DP table entries, and prove the correctness invariants. While proving the
correctness invariants for ℓ, we assume that the correctness invariant holds for ℓ − 1. When ℓ = 1,
X1 = ∅ and the DP table entries are deﬁned as follows.
A[1, ∅, k′ ] =



1 if k′ = 0
0 otherwise

Since H1 = (∅, ∅), the correctness invarient follows. The values A[1, ∗, ∗] can be computed in O(1)
time. Now we move to the case where ℓ > 1.
Case 1: Xℓ is an Introduce bag. That is Xℓ = Xℓ−1 ∪ f −1S(i, j) for some cell (i, j).
√ Fix a
family Z of vertex disjoint sets of size at most 2 of Xℓ such that | Z∈Z Z| is at most 840 k and
k′ ∈ [k]. Deﬁne Qℓ (r) to be the set Q of vertex disjoint paths in H[Xℓ \ Xℓ−1 ] = H[f −1 (i, j)] with
b = {{u, v} | there is a u-v path in Q}.
at most 120 end points and |E(Q)| = r. Recall that that Q
bℓ (r) = {Q
b : Q ∈ Qℓ (r)}.
Deﬁne Q
16

bℓ (r)| = kO(1) and Q
bℓ (r) can be enumerated in time kO(1) .
Claim 6.6. |Q

Proof. We know that H[Xℓ \ Xℓ−1 ] is a clique on f −1 (i, j). For any family W of vertex disjoint sets
of size at most 2 of f −1 (i, j), one can get |W| vertex disjoint paths with end points being the one
speciﬁed by the sets in W with total number of edges r, only if either |{W S
∈ W : |W | = 2}| = r
or 1 ≤ |{W ∈ W : |W | = 2}| < r and |{W ∈ W : |W | = 2}| + |f −1 (i, j) \ W ∈W W | ≥ r. Hence
bℓ (r) in time kO(1)
we can enumerate Q
For any family Y of sets of size at most 2, deﬁne Y ′ = {A ∈ Y : |A| = 2}. For any three
families Y1 , Y2 and Y3 of sets of size at most 2 in Xℓ , we
S Y1 ∪ Y2 ∪ Y3 for a family of
S say that
paths (respectively, a cycle) in G′ = K[Xℓ ], if the graph ( i∈[3] Y, i∈[3] Yi′ ) form a family of paths

(respectively, a cycle). Consider the case when Z 6= ∅.

bℓ (k′ ), then we set A[ℓ, Z, k′ ] = 1
If Z ∈ Q

Otherwise,
A[ℓ, Z, k′ ] = max

Y ∈Yi

n

(1)

b∈Q
bℓ (r),
A[ℓ − 1, Z ′ , k′′ ] : Z ′ 6= ∅ and there exist r ∈ N, Q


[
[
Q,
Z  such that , |E ′ | ≤ 120, k ′ = k′′ + r + |E ′ |,
E′ ⊆ E 
b
Q∈Q

c′
Z∈Z

b ∪ E ′ forms a set R of paths in K[Xℓ ], and R
b=Z
Z ∪Q
′

o

(2)

Now consider that case when Z = ∅.

If A[ℓ − 1, ∅, k′ ] = 1, then we set A[ℓ, ∅, k′ ] = 1

(3)

Otherwise
A[ℓ, ∅, k′ ] = max

n

b∈Q
bℓ (r),
A[ℓ − 1, Z ′ , k′′ ] : there exist r ∈ N, Q


[
[
E′ ⊆ E 
Q,
Z  such that , |E ′ | ≤ 120,
b
Q∈Q

c′
Z∈Z

o
b ∪ E ′ forms a cycle in K[Xℓ ]
k′ = k′′ + r + |E ′ |, and Z ′ ∪ Q

(4)

Notice that in the above
computation (Equations 2 and 4) the number of potential choices
√
k
log
k) . By Claim 6.6 we know that the cardinality of Q
′
O(
bℓ (r) is at most
for Z is bounded by 2
O(1)
O(1)
O(1)
k
and it can be enumerated in time k
. Since |Xℓ | = k
, the number of choices for E ′ is
O(1)
the above computation is bounded by k √. This implies that we can compute A[ℓ, Z, k′ ] using
previously computed DP entries in time 2O( k log k) .
Before proving the correctness invariant, we state the following simple claim, which can be
proved using induction of ℓ.
Claim 6.7. For any ℓ ∈ [q], A[ℓ, ∅, 0] = 1.

17

Now we prove the correctness invariants. Let C ∈ C. Recall that CL = Hℓ [E(C)] and
b
CL = {{u, v} | there is a connected component P in CL and P is a u-v path as well}. Partition
the edges CL into E1 ⊎ E2 ⊎ E ′ where E1 = E(CL ) ∩ E(Hℓ−1 ), E2 = E(CL ) ∩ E(Xℓ \ Xℓ−1 )
and E ′ = E(CL ) ∩ E(Xℓ−1 , Xℓ \ Xℓ−1 ). Let CL′ = H[E1 ]. That is, CL′ = Hℓ−1 [E(C)]. Let
b ′ = {{u, v} | there is a u-v path in C ′ }. We have two cases based whether C
bL = ∅ or not.
C
L
L
bL 6= ∅. If CL is a subgraph of H[Xℓ \ Xℓ−1 ], then C
bL ∈ Q(|E(C
b
Suppose C
L )|). Then by
bL , |E(CL )|] = 1. So now we have that CL is not a subgraph of
Equation 1, we have that A[ℓ, C
b′
H[Xℓ \ Xℓ−1 ]. This implies that either E
√1 6= ∅ or E2 6= ∅. In either case, we have that CL 6= ∅.
Since Xℓ−1 is a union of vertices from 7 k cells, the property 2 of clique-grid graph and C ∈ C,
we have √that the number
of edges with one
√
S endpoint Xℓ−1√and other in H \ Xℓ−1 is at most
5 · 24 · 7 k = 840 k. This implies that | D∈Cb′ D| ≤ 840 k. By the correctness invariant of
L
b′ , |E(C ′ )|] = 1. Consider the graph H[E2 ]. The
statement (i) for ℓ − 1, we have that (a) A[ℓ − 1, C
L
L
graph H[E2 ] is a collection Q of paths in H[Xℓ \ Xℓ−1 ] = K[f −1 (i, j)]. Since C ∈ C, the number
of edges of E(C) with one end point in f −1 (i, j) and other in Xℓ−1 is at most 4 · 25 = 120. This
b∈Q
bℓ (r), where r = |E(Q)|. By facts (a), (b) and (c), using
implies that (b) |E ′ | ≤ 120 and (c) Q
b
Equation 2, we get A[ℓ, CL , |E(CL )|] = 1.
bL = ∅. In this case either E(C) ∩ Hℓ = ∅ or E(C) ⊆ E(Hℓ ). If
Now consider the case when C
bL , |E(CL )|] = A[ℓ, ∅, 0] = 1, by Claim 6.7. Now
E(C) ∩ Hℓ = ∅, then |E(CL )| = 0 and hence A[ℓ, C
b
we have CL = ∅ and E(C) ⊆ E(Hℓ ). This implies that |E(CL )| = k. If E(CL ) = E(CL′ ), then
b ′ , k] = A[ℓ−1, ∅, k] = 1, by the statement (i) of the correctness invariant for ℓ−1. So, now
A[ℓ−1, C
L
we have E(CL ) 6= E(CL′ ). This implies that either E2 or E ′ is not empty. Since |f −1 (i, j)| < k and
b′ 6= ∅. The graph H[E2 ] is a collection Q
CL = C form a cycle and E(CL ) 6= E(CL′ ), we have that C
L
√
S
−1
of paths in H[Xℓ \ Xℓ−1 ] = K[f (i, j)]. As like before, we can bound (d) | D∈Cb′ D| ≤ 840 k, (e)
L
b∈Q
b ℓ (r), where r = |E(Q)|. By (d) and the statement (i) of the correctness
|E ′ | ≤ 120 and (g) Q
b′ , |E(C ′ )|] = 1. By facts (h), (e) and (d), using Equation 4,
invariant for ℓ − 1, we get (h) A[ℓ − 1, C
L
L
bL , |E(CL )|] = A[ℓ, ∅, k] = 1. This completes the proof of statement (i).
we get A[ℓ, C
Now we need to prove statement (ii) in the correctness
invariants.
√ Let Z ′be a family of vertex
S
disjoint sets of size at most 2 of Xℓ with 0 < | Z∈Z Z| ≤ 840 k and k ∈ [k]. Notice that
Z 6= ∅. Suppose in the above computation we set A[ℓ, Z, k′ ] = 1. Either A[ℓ, Z, k′ ] is set to 1
because of Equation 1 or because of Equation 2. If A[ℓ, Z, k′ ] is set to 1 because of Equation 1,
bℓ (k′ ). By the deﬁnition of Q
bℓ (k′ ), we get that there is a set R of vertex
then we know that Z ∈ Q
b = Z. So, now assume that A[ℓ, Z, k′ ] is
disjoint paths in H[Xℓ \ Xℓ−1 ], hence in H[Xℓ ] and R
set to 1 because of Equation 2. This implies that there exist k′′
, r ∈ N, a family Z′ of vertex
b ∈ Q
bℓ (r), and E ′ ⊆ E S b Q, S c′ Z such that
disjoint sets of size at most 2 of Xℓ−1 , Q
Q∈Q
Z∈Z
b ∪ E ′ forms a set of paths R in K[Xℓ ]
A[ℓ − 1, Z ′ , k′′ ] = 1, |E ′ | ≤ 120, k′ = k′′ + r + |E ′ |, Z ′ ∪ Q
b = Z. Since A[ℓ − 1, Z ′ , k′′ ] = 1, by the statement (ii) of the correctness invariant for
with R
ℓ − 1, we have that there is a set Y of |Z ′ | vertex disjoint paths in Hℓ−1 where the end points
of each path are speciﬁed by a set in Z ′ and |E(Y)| = k′′ . Let Q be the set of paths in Qℓ (r)
b Thus by replacing each edge of Z ′ in Z ′ ∪ Q
b ∪ E ′ by the corresponding
corresponding to the set Q.
b by a corresponding path in Q, we can get a set W of vertex disjoint
path in Y and each edge of Q
S
paths in Hℓ , because the internal vertices of paths in Y are disjoint from (Xℓ \ Xℓ−1 ) ∪ Z∈Z Z
S
c = Z and
and the interval vertices of paths in Q are disjoint from Xℓ−1 ∪ Z∈Z Z. More over, W
′
′′
′
′
|E(W)| = |E(Y)| + |E(Q)| + |E | = k + r + |E | = k . This completes the proof of statement (ii)
in the correctness invariant.
Now we prove statement (iii) in the correctness invariants. Suppose we set A[ℓ, ∅, k] = 1. Then
either A[ℓ, ∅, k] is set to 1 because of Equation 3 or because of Equation 4. If A[ℓ, ∅, k] is set to
18

1 because of Equation 1, then we know that A[ℓ − 1, ∅, k] = 1, then by the statement (iii) of the
correctness invariant for ℓ − 1, we have that there is a cycle of length k in Hℓ−1 and hence in Hℓ .
Suppose A[ℓ, ∅, k] is set to 1 because of Equation 4. Then, there exist k′′ , r ∈ N, a family Z ′ of
b ∈Q
bℓ (r), and E ′ ⊆ E S b Q, S c′ Z such
vertex disjoint sets of size at most 2 of Xℓ−1 , Q
Q∈Q
Z∈Z
′
′′
′
′′
′
′
′
b
that A[ℓ − 1, Z , k ] = 1, |E | ≤ 120, k = k + r + |E |, Z ∪ Q ∪ E forms a cycle in K[Xℓ ]. Since
A[ℓ − 1, Z ′ , k′′ ] = 1, by the statement (ii) of the correctness invariant for ℓ − 1, we have that there
is a set Y of |Z ′ | vertex disjoint paths in Hℓ−1 where the end points of each path are speciﬁed by
b Thus
a set in Z ′ and |E(Y)| = k′′ . Let Q be the set of paths in Qℓ (r) corresponding to the set Q.
′
′
′
b ∪ E by the corresponding path in Y and each edge of Q
b by
by replacing each edge of Z in Z ∪ Q
a corresponding path in Q, we can
S get a cycle C in Hℓ , because the internal vertices of paths in
Y are disjoint
from
(X
\
X
)
∪
ℓ
ℓ−1
Z∈Z Z and the interval vertices of paths in Q are disjoint from
S
Xℓ−1 ∪ Z∈Z Z. More over, |E(C)| = |E(Y)| + |E(Q)| + |E ′ | = k′′ + r + |E ′ | = k. This completes
the proof of statement (iii) in the correctness invariant.
Case 2:S Xℓ is a forget bag. √ Fix a family Z of vertex disjoint sets of size at most 2 of Xℓ
such that | Z∈Z Z| is at most 840 k and k′ ∈ [k].
A[ℓ, Z, k′ ] = A[ℓ − 1, Z, k′ ]

(5)

Clearly A[ℓ, Z, k′ ] can be computed in O(1) time using the previously computed DP table entries.
Now we prove the correctness invariant. Let C ∈ C. Recall that CL = Hℓ [E(C)] and
bL = {{u, v} | there is a connected component P in CL and P is a u-v path as well}. By arguC
√
S
ments similar to those in Case 1, we get | D∈CbL D| ≤ 840 k. Since Hℓ = Hℓ−1 , we have that
bL , |E(CL )|] =
CL = Hℓ−1 [E(C)]. Hence by the correctness invariant for ℓ−1, we have that A[ℓ−1, C
bL , |E(CL )|] = 1.
1. Hence, by Equation 5, A[ℓ − 1, C
Now we need to prove statement (ii) of the correctness
invariants.
Let Z be a family of vertex
√
S
disjoint sets of size at most 2 of Xℓ with 0 < | Z∈Z Z| ≤ 840 k and k′ ∈ [k]. Suppose in the
above computation (Equation 5) we set A[ℓ, Z, k′ ] = 1. This implies that A[ℓ − 1, Z, k′ ] = 1. Since
A[ℓ − 1, Z, k′ ] = 1, by the correctness invariant for ℓ − 1, we have that there is a set Y of |Z| vertex
disjoint paths in Hℓ−1 where the end points of each path are speciﬁed by a set in Z and |E(Y)| = k ′ .
Since Hℓ = Hℓ−1 , Y is the required set of vertex disjoint paths and this completes the proof of
statement (ii) in the correctness invariant.
Now we prove the statement (iii) in the correctness invariants. Suppose in the above computation (Equation 5) we set A[ℓ, ∅, k] = 1. This implies that A[ℓ − 1, ∅, k] = 1 Since A[ℓ − 1, ∅, k] = 1,
by the correctness invariant for ℓ − 1, we have that there is k length cycle in Hℓ−1 , and hence in
Hℓ . This completes the proof of correctness invariants.
Algorithm A output Yes if A[q, ∅, k] = ∅ and a output No otherwise. The correctness of the
algorithm follows from the correctness invariants. Now we analyse the total
√ running time. Notice
that |V (H)| = kO(1) and number√of DP table entries is bounded by 2O( k log k) . Each DP table
entry can be computed in time 2O( k log k) using
√ the previously stored values in the DP table. Hence
k log k) .
O(
the total running time of the algorithm is 2
Lemmata 5.6, 6.2, 6.4 and 6.5 implies the following Lemma.
√

Lemma 6.8. Exact k-Cycle on clique-grid graphs can be solved in time 2O(

k log k) nO(1) .

Theorem 6.1 follows from Lemma
6.8 and Corollary 3.4. We can design a similar algorithm to
√
solve Longest Path in time 2O( k log k) nO(1) .
19

7

Longest Cycle

In this section, we show that Longest Cycle admits a subexponential-time parameterized algorithm. More precisely, we prove the following.
√

Theorem 7.1. Longest Cycle on unit disk/square graphs can be solved in time 2O(

k log k) ·nO(1) .

We start by stating a direct implication of Lemma 6.8.
Corollary
7.2. Given a graph G, representation f and k ∈ N, it can be determined in time
√
O(
k
log
k)
2
· nO(1) whether G contain a cycle whose number of vertices is between k and 2k.
Proof. Run the algorithm given by Lemma 6.8 with k = ℓ, ℓ + 1, . . . , 2ℓ, and return Yes if and only
if at least one of the executions returns Yes. Correctness and running time follow directly from
Lemma 6.8.
Next, we examine the operation that contracts an edge. To this end, we need the following.
Definition 7.3. A pair (u, v) of distinct vertices u, v ∈ V (G) is contractible if f (u) = f (v).
Note that if (u, v) is a contractible pair, then by Condition 1 in Deﬁnition 3.1, it holds that
{u, v} ∈ E(G). Now, given a contractible pair (u, v), denote e = {u, v}, and deﬁne the function
f/e : V (G/e) → [t] × [t′ ] as follows. For all w ∈ V (G) \ {v, u}, deﬁne f/e (w) = f (w). Moreover,
deﬁne f/e (x{u,v} ) = f (u). By Deﬁnitions 3.1 and 4.6, we immediately have the following.
Observation 7.4. The function f/e is a representation of G/e. Furthermore, G and G/e have the
same cell graph.
In particular, we deduce that (G/e, f/e , k) is an instance of Longest Cycle on clique-grid
graphs. Next, we note that the operation that contracts an edge preserves the answer No—the
correctness of this claim follows from the fact that G/e is a minor of G.
Observation 7.5. Let (G, f, k) be an instance of Longest Cycle on clique-grid graphs. Then,
(G/e, f/e , k) is an instance of Longest Cycle on clique-grid graphs such that if (G, f, k) is a
No-instance, then (G/e, f/e , k) is a No-instance.
Now, we also verify that in case there exists a cycle on at least 2k vertices, the operation that
contracts an edge also preserves the answer Yes.
Lemma 7.6. Let (G, f, k) be an instance of Longest Cycle on clique-grid graphs such that G
contains a cycle C on at least 2k vertices. Then, (G/e, f/e , k) is a Yes-instance.
Proof. Denote e = {u, v}. In case V (C) ∩ {u, v} = ∅, then C is also a cycle in G/e, and in case
|V (C) ∩ {u, v}| = 1, then by replacing the vertex in V (C) ∩ {u, v} by x{u,v} in C, we obtain a cycle
of the same length as C in G/e. In both of these cases, the proof is complete, and thus we next
suppose that {u, v} ⊆ V (C).
Let us denote C = v1 − v2 − v3 − · · · − vℓ − v1 , where v1 = u and vi = v for some i ∈ [ℓ] \ {1}.
Note that ℓ ≥ 2k. Without loss of generality, assume that i − 2 ≥ ℓ − i (else we replace each
vj , except for v1 , by vℓ−j , and obtain a cycle where this property holds). Now, note that C ′ =
x{u,v} − v2 − · · · − vi−1 − x{u,v} is a cycle in G/e. Moreover, since i − 2 ≥ ℓ − i, it holds that
|V (C ′ )| = i − 1 ≥ 2ℓ ≥ k. Thus, (G/e, f/e , k) is a Yes-instance.

20

Before we present our algorithm, we need two additional propositions, handling the extreme
cases where we either discover that our input graph contains a large grid or, after a series of
operations that contracted edges in G, we ended up with a graph isomorhpic to the cell graph of
G. For the ﬁrst case, we need the following result (see also [17, 14]).
Observation
7.7. Let (G, k) be an instance of Longest Cycle on general graphs. If G contains
√
√
a k × k grid as a minor, then (G, k) is a Yes-instance.
For the second case, we need the following result (see also [14]).
Proposition 7.8 ([7]). Longest Cycle on graphs of treewidth tw can be solved in time 2O(tw ) ·
nO(1) .
From Proposition 7.8 and the fact that cell(G) is a minor of G, we have the following.
Observation 7.9. Let (G, f, k) be an instance of Longest Cycle on clique-grid graphs. Then, it
can be determined in time 2O(tw(cell(G))) ·nO(1) whether cell(G) contains a cycle on at least k vertices,
in which case (G, f, k) is a Yes-instance.
We are now ready to present our algorithm. The proof of correctness and analysis of running
times are integrated in the description of the algorithm.
Proof of Theorem 7.1. Let (G, O, k) be an instance of Longest Cycle on unit disk/square
graphs. By using Corollary 3.4, we ﬁrst obtain an equivalent instance (G, f, k) of Longest Cycle
on clique-grid graphs (both instances refer to the same
√ graph G and parameter k). Next, by
3 ·
using Lemma
4.9
with
the
parameter
ℓ
=
100
·
599
k, we either correctly conclude that G
√
√
contains a √k × k grid
√ as a minor, or compute a tree decomposition of cell(G) of width at most
7.7, we are done. In the latter case,
500 · 5993 · k = O( k). In the ﬁrst case, by Observation
√
k)
O(1)
O(
·n
whether cell(G) contains a cycle on
by using Observation 7.9, we determine in time 2
at least k vertices, where if the answer is positive, then we are done. Thus, we next suppose that
cell(G) does not contain a cycle on at least k vertices.
Now, as long as there exists a contractible pair √(u, v), we perform the following operation. First,
by using Corollary 7.2, we determine in time 2O( k log k) · nO(1) whether G contain a cycle whose
number of vertices is between k and 2k. If the answer is positive, then we are done (our ﬁnal answer
is Yes). If the answer is negative, then we contract the edge {u, v}. By Lemma 7.6, we obtain an
instance that is equivalent to the previous one. Note that the loop described in this paragraph
can
√
k
log
k)
2
O(
O(1)
have at most O(n ) iterations, and therefore its total running time is bounded by 2
·n
.
Once there does not exist a contractible pair (u, v), as we have only modiﬁed the graph by contracting edges, on at a time, between contractible pairs, we are left with a graph that is isomorphic
to the cell graph of our original input graph. We have already correctly concluded that this graph
does not contain a cycle on at least k vertices. Thus, at this point, we correctly answer No.

8

Feedback Vertex Set

In this section, we show that Feedback Vertex Set admits a subexponential-time parameterized
algorithm. More precisely, we prove the following.
√

Theorem 8.1. Feedback Vertex Set on unit disk/square graphs can be solved in time 2O(
nO(1) .
21

k log k) ·

First, we observe that if we ﬁnd a large grid, we can answer No (see also [17, 14]).
√
Observation
8.2. Let (G, k) be an instance of Feedback Vertex Set. If G contains a 2 k ×
√
2 k grid as a minor, then (G, k) is a No-instance.
This observation leads us to the following.
Lemma 8.3. Let√(G, O, k) be an instance of Feedback Vertex Set on unit disk/square graphs.
Then, in time 2O( k log k) ·|V (G)|O(1) , one can either solve (G, O, k) or obtain an √
equivalent instance
(G, f, k) of Feedback Vertex Set on clique-grid graphs together with an O( k)-NCTD of G.
Proof. First, by using Lemmata 3.2√or 3.3, we
√ obtain a representation f of G. Then, by using
3
Corollary
√
√ 4.10 with ℓ = 200 · 599 · k = O( √k), we either correctly conclude that G contains a
2 k × 2 k grid as a minor, or compute an O( k)-NCTD of G. In both cases, by Observation 8.2,
we are done.
Because of Lemma 8.3, to prove Theorem 8.1, we
√ can focus on Feedback Vertex Set on
clique-grid graphs, where the input also contains a O( k)-NCTD. That is, the input of Feedback
Vertex Set on clique-grid graphs is a√tuple (G, f, k, T ) where G is a clique-grid graph with
representation f and T = (T, β) is a O( k)-NCTD of G. Notice that if there is a cell (i, j) of f ,
such that |f −1 (i, j)| ≥ k + 3, then there is no feedback vertex set of size at most k in G, because
f −1 (i, j) is a clique of size at least k + 3 in G.
Observation 8.4. Let (G, f, k, T ) be an instance of Feedback Vertex Set, where G is a cliquegrid graph with representation f . If there is a cell (i, j) in f such that |f −1 (i, j)| ≥ k + 3, then
(G, f, k, T ) is a No-instance.
√
The following observation follows from the fact that T is a O( k)-NCTD and |f −1 (i, j)| ≤ k + 2
for any cell (i, j) of f .
Observation 8.5. For any v ∈ V (T ), |β(v)| = O(k1.5 ).
Notice that G has a feedback vertex set of size at most k if and only if there is a vertex subset
F ⊆ V (G) of cardinality at least |V (G)| − k such that G[F ] is a forest. Hence, instead of stating
the problem as ﬁnding a k sized feedback vertex set in G, we can state it as ﬁnding an induced
subgraph H of G with maximum number of vertices such that H is a forest.
Max Induced Forest (MIF)
Parameter: k
√
Input: A clique-grid graph G with representation f and an integer k such that T is a c kNCTD of G and for any cell (i, j) in f , |f −1 (i, j)| ≤ k + 2, where c is a constant
Question: Is there subset W ⊆ V (G) such that G[W ] is a forest and |W | ≥ |V (G)| − k
Observation 8.6. Let (G, f, k, T ) be an instance of MIF. Then (G, f, k, T ) is a Yes-instance of
MIF if and only if (G, f, k, T ) is a Yes-instance of Feedback Vertex Set.
By Lemma 8.3 and Observations 8.4 and 8.6, to prove Theorem 8.1, it is suﬃcient that we prove
the following result (which is the focus of the rest of this section).
√

Lemma 8.7. MIF on clique-grid graphs can be solved in time 2O(

22

k log k)

· nO(1) .

Proof sketch. We explain a DP algorithm which
G is a clique-grid
√ given as input (G, f, k, T ) where
−1
graph with representation f , T = (T, β) is a c k-NCTD, c is a constant and |f (i, j)| ≤ k + 2 for
any cell (i, j) of f and outputs Yes if there is an induced forest with at least |V (G)| − k vertices
and outputs No otherwise. Here we use the term solution for a vertex subset S ⊆ V (G) with the
property that G[S] is a forest. First notice that any solution S contains at most 2 vertices
from
√
f −1 (i, j) for any cell (i, j). Now, the following claim follows from the fact that T is a c k-NCTD
and any solution contain at most 2 vertices from f −1 (i, j) for any cell (i, j).
√
Claim 8.8. For any v ∈ V (T ) and any solution S, |S ∩ β(v)| ≤ 2c k.
We ﬁrst brieﬂy explain what is the table entries in a standard DP algorithm for our problem on
graphs of bounded treewidth [14]. Then we explain that in fact many of the entries we compute in
the standard DP table is redundant in our case, because√ of Observation 8.5 and Claim 8.8. That
is, Observation 8.5 and Claim 8.8, shows that only 2O( k log k) |V (G)|O(1) many states in the DP
table are relevant in our case. Recall that for any v ∈ V (T ), γ(v) denote the union of the bags
of v and its descendants. The standard DP table for our problem will have an entry indexed by
(v, U, U1 ⊎ U2 . . . Uℓ = U ) where v ∈ V (T ), U ⊆ β(v). The table entry A[v, U, U1 ⊎ U2 . . . Uℓ ] stores
the following information: the maximum cardinality of a vertex subset W ⊆ G[γ(v)] such that
W ∩ β(v) = U , G[W ] is a forest with a set of connected components C and for any C ∈ C, either
V (C) ∩ β(v) = ∅ or V (C) ∩ β(v) = Ui for some i ∈ [ℓ]. Notice that the total number of DP table
entries is bounded by twO(tw) |V (G)|O(1) where tw is the width of the tree decomposition T . One
can easily show that the computation of the DP table at a node can be done in time polynomial
in the size of the tables of its children.
By Observation 8.5 and Claim 8.8, we know that for any bag β(v)
in T , the potential number
√
of subsets of β(v) which can be part of any solution is at most 2O( k log k) . This implies that we
only need to compute the
√ DP table entries for indices (v, U, U1 ⊎ U2 . . . Uℓ = U ) where v ∈ V (T ),
k. Thus, the size of DP table, and hence the time to compute it takes
U ⊆
β(v)
and
|U
|
≤
2c
√
O(
k
log
k)
O(1)
2
n
time. This concludes the description.

9

Cycle Packing

In this section, we show that Cycle Packing admits a subexponential-time parameterized algorithm. More precisely, we prove the following.
√

Theorem 9.1. Cycle Packing on unit disk/square graphs can be solved in time 2O(

k log k) ·nO(1) .

First, we observe that if we ﬁnd a large grid, we can answer Yes (see also [17, 14]).
Observation
√ 9.2. Let (G, k) be an instance of Cycle Packing on general graphs. If G contains
√
a 2 k × 2 k grid as a minor, then (G, k) is a Yes-instance.
This observation leads us to the following.
Lemma 9.3.
Let (G, O, k) be an instance of Cycle Packing on unit disk/square graphs. Then,
√
k
log
k) · nO(1) , one can either solve (G, O, k) or obtain an equivalent instance (G, f, k)
O(
in time 2
√
of Cycle Packing on clique-grid graphs together with an O( k)-NCTD of G.
Proof. First, by using Lemmata 3.2√or 3.3, we
√ obtain a representation f of G. Then, by using
3
Corollary
√ 4.10 with ℓ = 200 · 599 · k = O( √k), we either correctly conclude that G contains a
√
2 k × 2 k grid as a minor, or compute an O( k)-NCTD of G. In both cases, by Observation 9.2,
we are done.
23

Now, note that if there exists a cell (i, j) ∈ [t] × [t′ ] such that |f −1 (i, j)| ≥ 3k, then by Condition
1 in Deﬁnition 3.1, G[f −1 (i, j)] is a clique on at least 3k vertices and thus it contains k pairwise
vertex-disjoint cycles (triangles). More precisely, we have the following.
Observation 9.4. Let (G, f : V (G) → [t]× [t′ ], k) of Cycle Packing on clique-grid graphs. Then,
if there exists a cell (i, j) ∈ [t] × [t′ ] such that |f −1 (i, j)| ≥ 3k, then (G, f, k) is a Yes-instance.
By Lemma 9.3 and Observation 9.4, to prove Theorem 9.1, it is suﬃcient that we prove the
following result (which is the focus of the rest of this section).
√

Lemma 9.5. Cycle Packing on clique-grid
graphs can be solved in time 2O( k log k) · nO(1) , as√
suming that the input includes an O( k)-NCTD of G, and that for every cell (i, j) ∈ [t] × [t′ ], it
holds that |f −1 (i, j)| ≤ 3k.
Let (G, f : V (G)√→ [t] × [t′ ], k) denote the input instance of √
Cycle Packing, and let T =
(T, β) denote our O( k)-NCTD of G. Note that since T is an O( k)-NCTD, and since for every
(i, j) ∈ [t] × [t′ ], it holds that |f −1 (i, j)| ≤ 3k, we also have the following.
Observation 9.6. For all v ∈ V (T ), it holds that |β(v)| = O(k 1.5 ).
We proceed by considering the “interaction” between cells in the context of the manner in which
cycles in a solution cross their boundaries. To be precise, by Deﬁnition 3.1, we ﬁrst observe the
following.
Observation 9.7. Let C be an induced cycle in G. Then, there does not exist a cell (i, j) ∈ [t] × [t′ ]
and two distinct vertices u, v ∈ V (C) ∩ f −1 (i, j) such that {u, v} ∈
/ E(C). In particular, for every
cell (i, j) ∈ [t] × [t′ ], exactly one of the following conditions holds.
1. V (C) ⊆ f −1 (i, j).
2. |V (C) ∩ f −1 (i, j)| = 1.
3. |V (C) ∩ f −1 (i, j)| = 2 and the two vertices in V (C) ∩ f −1 (i, j) are neighbors in C.
Next, note that given a set C of pairwise vertex-disjoint cycles and a cycle C ∈ C that is not an
induced cycle in G, by replacing C in C by an induced cycle in G[V (C)], we obtain another set of
pairwise vertex-disjoint cycles. Thus, we have the following.
Observation 9.8. If (G, f, k) is a Yes-instance, then G contains a set C of k pairwise-disjoint
induced cycles.
Definition 9.9. Given two distinct cells (i, j), (i′ , j ′ ) ∈ [t]× [t′ ], we say that C crosses ((i, j), (i′ , j ′ ))
if there exist (not necessarily distinct) u, v ∈ f −1 (i, j) and distinct w, r ∈ f −1 (i′ , j ′ ) such that
{u, w}, {v, r} ∈ E(C). Moreover, we say that C crosses {(i, j), (i′ , j ′ )} if it crosses at least one of
the pairs ((i, j), (i′ , j ′ )) and ((i′ , j ′ ), (i, j)).
Definition 9.10. Given three distinct cells (i1 , j1 ), (i2 , j2 ), (i3 , j3 ) ∈ [t] × [t′ ], we say that C
crosses ((i1 , j1 ), (i2 , j2 ), (i3 , j3 )) if there exist u ∈ f −1 (i1 , j1 ), (not necessarily distinct) v, w ∈
f −1 (i2 , j2 ) and r ∈ f −1 (i3 , j3 ) such that {u, v}, {w, r} ∈ E(C). Moreover, we say that C crosses
{(i1 , j1 ), (i2 , j2 ), (i3 , j3 )} if it crosses at least one of the tuples in {((is , js ), (ir , jr ), (it , jt )) : {s, r, t} =
{1, 2, 3}}.
Next, we use the deﬁnitions above to capture the set of cycles which we would like detect (if a
solution exists).
24

Definition 9.11. A set C of pairwise vertex-disjoint induced cycles is simple if it satisﬁes the
following conditions.
• For every two distinct cells (i, j), (i′ , j ′ ) ∈ [t] × [t′ ], there exist at most two cycles in C that
cross {(i, j), (i′ , j ′ )}.
• For every three distinct cells (i1 , j1 ), (i2 , j2 ), (i3 , j3 ) ∈ [t] × [t′ ], there exist at most two cycles
in C that cross {(i1 , j1 ), (i2 , j2 ), (i3 , j3 )}.
Given a cycle C (in G), denote cross(C) = {{u, v} ∈ E(C) : f (u) 6= f (v)}, and given a set C of
cycles, denote cross(C) = ∪C∈C cross(C). Next, we show that we can focus on the deciding whether
a simple set, rather than a general set, of k pairwise-disjoint cycles exists.
Lemma 9.12. If (G, f, k) is a Yes-instance, then G contains a simple set of k pairwise-disjoint
induced cycles.
Proof. Suppose that (G, f : V (G) → [t] × [t′ ], k) is a Yes-instance. Next, let C denote a set of k
pairwise vertex-disjoint induced cycles that minimizes |cross(C)| among all such sets of cycles (the
existence of at least one such set of induced cycles is guaranteed by Observation 9.8). We will show
that C is simple. In what follows, we implicitly rely on Condition 1 in Deﬁnition 3.1.
First, suppose that there exist two distinct cells (i, j), (i′ , j ′ ) ∈ [t] × [t′ ] and three cycles in C
that cross {(i, j), (i′ , j ′ )}. Let C1 , C2 and C3 denote these three cycles. Then, at least one of the
three following conditions is true.
1. There exist distinct s, t ∈ {1, 2, 3} such that |(V (Cs ) ∪ V (Ct )) ∩ f −1 (i, j)| ≥ 3 and |(V (Cs ) ∪
V (Ct )) ∩ f −1 (i′ , j ′ )| ≥ 3: In this case, we replace Cs and Ct in C by some cycle on three
vertices in G[(V (Cs ) ∪ V (Ct )) ∩ f −1 (i, j)] and some cycle on three vertices in G[(V (Cs ) ∪
V (Ct )) ∩ f −1 (i′ , j ′ )]. We thus obtain a set of k pairwise vertex-disjoint cycles, C ′ , such that
|cross(C ′ )| < |cross(C)|, which is a contradiction to the choice of C.
2. |(V (C1 ) ∪ V (C2 ) ∪ V (C3 )) ∩ f −1 (i, j)| = 3 and |(V (C1 ) ∪ V (C2 ) ∪ V (C3 )) ∩ f −1 (i′ , j ′ )| ≥ 6:
In this case, we replace C1 , C2 and C3 in C by some cycle on three vertices in G[(V (C1 ) ∪
V (C2 )∪V (C3 ))∩f −1 (i, j)] and two vertex-disjoint cycles, each on three vertices, in G[(V (C1 )∪
V (C2 ) ∪ V (C3 )) ∩ f −1 (i′ , j ′ )]. We thus obtain a set of k pairwise vertex-disjoint cycles, C ′ ,
such that |cross(C ′ )| < |cross(C)|, which is a contradiction to the choice of C.
3. |(V (C1 ) ∪ V (C2 ) ∪ V (C3 )) ∩ f −1 (i, j)| ≥ 6 and |(V (C1 ) ∪ V (C2 ) ∪ V (C3 )) ∩ f −1 (i′ , j ′ )| = 3:
This case is symmetric to the previous one.
Second, suppose that there exist three distinct cells (i1 , j1 ), (i2 , j2 ), (i3 , j3 ) ∈ [t] × [t′ ] and three
cycles in C that cross {(i1 , j1 ), (i2 , j2 ), (i3 , j3 )}. Let C1 , C2 and C3 denote these three cycles. Then,
it holds that |(V (C1 )∪V (C2 )∪V (C3 ))∩f −1 (i1 , j1 )| ≥ 3, |(V (C1 )∪V (C2 )∪V (C3 ))∩f −1 (i2 , j2 )| ≥ 3
and |(V (C1 ) ∪ V (C2 ) ∪ V (C3 )) ∩ f −1 (i3 , j3 )| ≥ 3. We replace C1 , C2 and C3 in C by some cycle
on three vertices in G[(V (C1 ) ∪ V (C2 ) ∪ V (C3 )) ∩ f −1 (i1 , j1 )], some cycle on three vertices in
G[(V (C1 ) ∪ V (C2 ) ∪ V (C3 )) ∩ f −1 (i2 , j2 )], and some cycle on three vertices in G[(V (C1 ) ∪ V (C2 ) ∪
V (C3 )) ∩ f −1 (i3 , j3 )].
Now, we examine the information given by Lemma 9.12 to extract a form that will be easier for
us to exploit. To this end,
following. Given aSset C of cycles and a cell (i, j) ∈ [t] × [t′ ],
S we need the−1
denote cross(C, i, j) = ( cross(C)) ∩ f (i, j) (note that cross(C) is the set of every vertex that
is an endpoint of an edge in cross(C)).
25

Lemma 9.13. If (G, f : V (G) → [t] × [t′ ], k) is a Yes-instance, then G contains a set C of k
pairwise-disjoint induced cycles such that for every cell (i, j) ∈ [t]×[t′ ], it holds that |cross(C, i, j)| ≤
2304 = O(1).
Proof. Suppose that (G, f, k) is a Yes-instance. By Lemma 9.12, there exists a simple set C
of k pairwise-disjoint induced cycles. Let (i, j) ∈ [t] × [t′ ] be some cell. Given a cell (i′ , j ′ ) ∈
[t] × [t′ ] \ {(i, j)}, denote C(i′ , j ′ ) = {C ∈ C : C crosses {(i, j), (i′ , j ′ )}}. Moreover, given cells
(i2 , j2 ), (i3 , j3 ) ∈ [t]×[t′ ]\{(i, j)}, denote C(i2 , j2 , i3 , j3 ) = {C ∈ C : C crosses {(i, j), (i2 , j2 ), (i3 , j3 )}}.
Now, we deﬁne two sets of indices:
• I = {(i′ , j ′ ) ∈ [t] × [t′ ] \ {(i, j)} : C(i′ , j ′ ) 6= ∅}.
• I ′ = {((i2 , j2 ), (i3 , j3 )) ∈ ([t] × [t′ ] \ {(i, j)}) × ([t] × [t′ ] \ {(i, j), (i2 , j2 )}) : C(i2 , j2 , i3 , j3 ) 6= ∅}.
Then, by Observation 9.7 and Lemma 9.12, it holds that
[
[
|cross(C, i, j)| ≤ 2(|
C(i′ , j ′ )| + |
(i′ ,j ′ )∈I

((i2 ,j2 ),(i3 ,j3

))∈I ′

C(i2 , j2 , i3 , j3 )|)

≤ 4(|I| + |I ′ |).
Note that |{(i′ , j ′ ) ∈ [t] × [t′ ] \ {(i, j)} | |i − i′ | ≤ 2, |j − j ′ | ≤ 2}| ≤ 24. Thus, by Condition
2 in Deﬁnition 3.1, we have that |I| ≤ 24 and |I ′ | ≤ 24 · 23 = 552. Therefore, cross(C, i, j)| ≤
4(24 + 552) = 2304.
We are now ready to prove Lemma 9.5. √
Except for the arguments where we crucially rely on
Lemma 9.13 and the fact the we have an O( k)-NCTD and not some general nice tree decomposition, the description of the DP is standard (see, e.g., [14]). Thus, we only give a sketch of the
proof.
Proof sketch of Lemma 9.5. Let us ﬁrst examine a standard DP table A to solve Cycle
Packing when the parameter is tw(G). Here, we have an entry A[v, Z, k′ ] for every node v ∈ V (T ),
multiset Z of subsets of sizes 1 or 2 of β(v) and nonnegative integer k′ ≤ k. Moreover, each set
of size 1 in Z has only one occurrence and its vertex does not appear in any set of size 2 in Z,
and every vertex in β(v) appears in at most two sets in Z. Each such entry stores either 0 or 1.
The value is 1 if an only if there exist a set S of k′ pairwise vertex-disjoint cycles in G[γ(v)] and a
set P of internally pairwise vertex-disjoint paths in G[γ(v)] such that the following conditions are
satisﬁed.
S
S
• ( C∈S V (C)) ∩ ( P ∈P V (P )) = ∅.
• On the one hand, for every cycle C ∈ C, it holds that |V (C)∩β(v)| ≤ 1 and if |V (C)∩β(v)| = 1
then there exists a set in Z that is equal to V (C) ∩ β(v). On the other hand, if Z contains a
set of size 1, then there exists a cycle C ∈ C such that V (C) ∩ β(v) equals this set.

• On the one hand, for every path P ∈ P, it holds that P contains at least three vertices,
both endpoints of P belong to a distinct occurrence of a set in Z (of size 2), and none of the
internal vertices of P belongs to β(v). On the other hand, for every occurrence X of a set of
size 2 in Z, there exists a distinct path P in P such that the set containing the two endpoints
of P is equal to X.

26

b where u is a child
b k]
The entry A[v, Z, k′ ] can be computed by examining the all entries A[u, Z,
of v in T (recall that v can have at most two children). At the end of the computation of A, we
conclude that the input instance is a Yes-instance if and only if A[r, ∅, k] contains 1 where r is the
root of T . By Observation 9.6, we deduce that A contains 2O(k log k) · n entries, where each entry
can be computed in time 2O(k log k) .
√
We claim that for every v ∈ V (T ), it is suﬃcient to compute only 2O( k log k) entries.S More
precisely, for every v ∈ V (T√), it is suﬃcient to compute only entries A[v, Z, k′ ] such that | Z| =
√
O( k) (there are only 2O( k log k) such entries). Indeed, suppose that the input instance is a Yesinstance. Then, by Lemma 9.13, there exists a set C of k pairwise vertex-disjoint induced cycles
such that for every cell (i, j) ∈ [t]×[t′ ], it holds that |cross(C, i, j)| = O(1). Now, we sketch the main
arguments that show that for every v ∈ V (T ), we still
have an entry that “captures” C (as explained
√
k
log
k) , which would imply that eventually, we
O(
below) and we are able to compute it in time 2
would still be able to deduce that A[r, ∅, k] contains 1. For this purpose, consider some v ∈ V (T ).
′
First, we notice that since for every cell
√ (i, j) ∈ [t] × [t ], it holds that |cross(C, i, j)| = O(1), by
Observation
9.7, and since T is an O( k)-NCTD, we have that there exists a set U of at most
√
O( k) vertices in β(v) such that every cycle C ∈ C satisﬁes at least one of the following conditions.
1. V (C) ∩ β(v) ⊆ U
2. V (C) ⊆ γ(v) \ β(v).
3. V (C) ⊆ V (G) \ γ(v).
Now, we let S denote the set of cycles in C such that all of their vertices, except at most one
that belongs to β(v), belong to γ(v) \ β(v). Accordingly, we denote k ′ = |S|. Moreover, let P
denote the set of every subpath of a cycle in C whose endpoints belong to β(v) and whose set of
internal vertices is a subset of size at least 1 of γ(v)
S \ β(v). √Finally, we deﬁne Z as the multiset
{β(v) ∩ O | O ∈ S ∪ P}. Then, it holds that | Z| = O( k) and C witnesses that A[v, Z, k′ ]
should be 1. Overall, by the existence of√the set U that is mentioned above, we conclude the entry
A[v, Z, k′ ] can be computed in time 2O( k log k) . This completes the proof sketch.

10

Conclusion
√

In this paper, we gave subexponential algorithms of running time 2O( k log k) · nO(1) for a number
of parameterized problems about cycles in unit disk graphs. The ﬁrst natural question is whether
the log k factor in the exponent can be shaved oﬀ. While we were not able to do it, we do not
exclude such a possibility. In particular, it would be very interesting to build a theory for unit disk
graphs, which is similar to the bidimensionality theory for planar graphs. In this context, it will be
useful to provide a general characterization of parameterized problems admitting subexponential
algorithms on unit disk graphs.

References
[1] Jochen Alber and Jiřı́ Fiala. Geometric separation and exact solutions for the parameterized
independent set problem on disk graphs. In Foundations of Information Technology in the Era
of Network and Mobile Computing, pages 26–37. Springer, 2002.
[2] Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. Assoc. Comput. Mach., 42(4):844–
856, 1995.
27

[3] Brenda S. Baker. Approximation algorithms for NP-complete problems on planar graphs. J.
Assoc. Comput. Mach., 41(1):153–180, 1994.
[4] Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Narrow sieves for
parameterized paths and packings. CoRR, abs/1007.1161, 2010.
[5] Andreas Björklund, Thore Husfeldt, and Nina Taslaman. Shortest cycle through speciﬁed
elements. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete
Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 1747–1753, 2012.
[6] Hans L. Bodlaender. A linear-time algorithm for ﬁnding tree-decompositions of small treewidth.
SIAM J. Comput., 25(6):1305–1317, 1996.
[7] Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf.
Comput., 243:86–111, 2015.
[8] Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. On
problems without polynomial kernels. J. Comput. Syst. Sci., 75(8):423–434, 2009.
[9] Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov,
and Michal Pilipczuk. A ck n 5-approximation algorithm for treewidth. SIAM J. Comput.,
45(2):317–378, 2016.
[10] Timothy M. Chan. Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms, 46(2):178–189, 2003.
[11] Jianer Chen, Iyad A. Kanj, and Weijia Jia. Vertex cover: further observations and further
improvements. Journal of Algorithms, 41(2):280–301, 2001.
[12] Brent N. Clark, Charles J. Colbourn, and David S. Johnson. Unit disk graphs. Discrete
Mathematics, 86(1-3):165–177, 1990.
[13] Kenneth L. Clarkson and Kasturi R. Varadarajan. Improved approximation algorithms for
geometric set cover. Discrete & Computational Geometry, 37(1):43–58, 2007.
[14] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin
Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015.
[15] Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, and Dimitrios M. Thilikos. Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free
graphs. J. ACM, 52(6):866–893, 2005.
[16] Erik D. Demaine and MohammadTaghi Hajiaghayi. Bidimensionality: new connections between fpt algorithms and ptass. In Proceedings of the 16th Annual ACM-SIAM Symposium on
Discrete Algorithms (SODA 2005), pages 590–601, New York, 2005. ACM-SIAM.
[17] Erik D. Demaine and MohammadTaghi Hajiaghayi. The bidimensionality theory and its algorithmic applications. Comput. J., 51(3):292–302, 2008.
[18] Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics.
Springer, 2012.

28

[19] Frederic Dorn, Eelko Penninkx, Hans L. Bodlaender, and Fedor V. Fomin. Eﬃcient exact
algorithms on planar graphs: Exploiting sphere cut decompositions. Algorithmica, 58(3):790–
810, 2010.
[20] Adrian Dumitrescu and János Pach. Minimum clique partition in unit disk graphs. Graphs
and Combinatorics, 27(3):399–411, 2011.
[21] F. V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos. Bidimensionality and kernels. In
Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010),
pages 503–510. SIAM, 2010.
[22] Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and
Saket Saurabh. Subexponential parameterized algorithms for planar and apex-minor-free
graphs via low treewidth pattern covering. In Proceedings of the 57th Annual Symposium
on Foundations of Computer Science (FOCS), to appear, 2016.
[23] Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Eﬃcient computation
of representative families with applications in parameterized and exact algorithms. J. ACM,
63(4):29, 2016.
[24] Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh. Bidimensionality
and EPTAS. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete
Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 748–759,
2011.
[25] Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh. Bidimensionality and geometric
graphs. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms
(SODA), pages 1563–1575. SIAM, 2012.
[26] William K Hale. Frequency assignment: Theory and applications. Proceedings of the IEEE,
68(12):1497–1514, 1980.
[27] Sariel Har-Peled and Mira Lee. Weighted geometric set cover problems revisited. JoCG,
3(1):65–85, 2012.
[28] Sariel Har-Peled and Kent Quanrud. Approximation algorithms for polynomial-expansion and
low-density graphs. In Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras,
Greece, September 14-16, 2015, Proceedings, volume 9294, pages 717–728. Springer, 2015.
[29] Dorit S. Hochbaum and Wolfgang Maass. Approximation schemes for covering and packing
problems in image processing and VLSI. J. ACM, 32(1):130–136, 1985.
[30] Harry B. Hunt III, Madhav V. Marathe, Venkatesh Radhakrishnan, S. S. Ravi, Daniel J.
Rosenkrantz, and Richard Edwin Stearns. Nc-approximation schemes for NP- and pspacehard problems for geometric graphs. J. Algorithms, 26(2):238–274, 1998.
[31] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly
exponential complexity. Journal of Computer and System Sciences, 63(4):512–530, 2001.
[32] Hiro Ito and Masakazu Kadoshita. Tractability and intractability of problems on unit disk
graphs parameterized by domain area. In Proceedings of the 9th International Symposium on
Operations Research and Its Applications (ISORA10), pages 120–127, 2010.
29

[33] Bart M. P. Jansen. Polynomial kernels for hard problems on disk graphs. In Proceedings of the
12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), volume 6139 of
Lecture Notes in Comput. Sci., pages 310–321. Springer, 2010.
[34] KARL Kammerlander. C 900-an advanced mobile radio telephone system with optimum
frequency utilization. IEEE journal on selected areas in communications, 2(4):589–597, 1984.
[35] Ioannis Koutis. Faster algebraic algorithms for path and packing problems. In Proceedings of
the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008),
volume 5125 of Lecture Notes in Computer Science, pages 575–586, 2008.
[36] Ioannis Koutis and Ryan Williams. Algebraic ﬁngerprints for faster algorithms. Commun.
ACM, 59(1):98–105, 2016.
[37] Dániel Marx. Eﬃcient approximation schemes for geometric problems? In Proceedings of
the 13th Annual European Symposium on Algorithms (ESA), volume 3669 of Lecture Notes in
Comput. Sci., pages 448–459. Springer, 2005.
[38] Nabil H. Mustafa, Rajiv Raman, and Saurabh Ray. Settling the apx-hardness status for
geometric set cover. In 55th IEEE Annual Symposium on Foundations of Computer Science,
FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 541–550. IEEE Computer
Society, 2014.
[39] Warren D. Smith and Nicholas C. Wormald. Geometric separator theorems & applications.
In Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS),
pages 232–243. IEEE Computer Society, 1998.
[40] Stéphan Thomassé. A quadratic kernel for feedback vertex set. ACM Transactions on Algorithms, 6(2), 2010.
[41] DW Wang and Yue-Sun Kuo. A study on two geometric location problems. Information
processing letters, 28(6):281–286, 1988.
[42] Ryan Williams. Finding paths of length k in O ∗ (2k ) time. Inf. Process. Lett., 109(6):315–318,
2009.
[43] Yu-Shuan Yeh, J Wilson, and S Schwartz. Outage probability in mobile telephony with directive antennas and macrodiversity. IEEE journal on selected areas in communications, 2(4):507–
511, 1984.
[44] Meirav Zehavi. Mixing color coding-related techniques. In Proceedings of the 23rd Annual
European Symposium on Algorithms (ESA), volume 9294 of Lecture Notes in Comput. Sci.,
pages 1037–1049. Springer, 2013.

30

