(Almost-)Optimal FPT Algorithm and Kernel for $T$-CYCLE on Planar Graphs

We first note that when the $T$-Cycle problem is extended to directed graphs, it becomes NP-hard already when $k=2$ [18]. Various other extensions/generalizations of $T$-Cycle were studied in the literature, including from the perspective of parameterized complexity. For example, Kawarabayashi et al. [26] developed an algorithm for detecting a $T$-loop whose length has a given parity; for fixed $k$, the running time is polynomial in $n$, but the dependency on $k$ is unspecified. For another example, Kobayashi and Kawarabayashi [27] developed an algorithm for detecting an induced $T$-loop in a planar graph in time $2^{O(k^{3/2}\log k)}{n}^2$. The survey of additional results of this nature is beyond the scope of this paper.

Highly relevant to the $T$-Cycle problem is the Disjoint Paths problem. Here, given a graph $G$ and a set $T=\{(s_i,t_i):i\in \{1,2,\mathrm{\dots },k\}\}$ of pairs of vertices (termed terminals) in $G$, the objective is to determine whether $G$ contains $k$ vertex-disjoint²²2With the exception that a vertex can occur in multiple paths if it is an endpoint in all of them. paths $P_1,P_2,\mathrm{\dots },P_k$ so that the endpoints of $P_i$ are $s_i$ and $t_i$. The $T$-Cycle problem can be reduced to the Disjoint Paths problem with an overhead of $k!=k^{O(k)}$: Given an instance $(G,T)$ of $T$-Cycle, for every ordering $v_0,v_1,\mathrm{\dots },v_{k-1}$ of $T$, create an instance $(G,T^{\prime })$ of Disjoint Paths where $T^{\prime }=\{(v_i,v_{(i+1)modk}):i\in \{0,1,\mathrm{\dots },k-1\}\}$; then, $(G,T)$ is a yes-instance of $T$-Cycle if and only if at least one of the constructed instances of Disjoint Paths is. Being foundational to the entire graph minor theory [30], the Disjoint Paths problem is of great importance to both algorithm design and graph theory, and has been intensively studied for several decades. Most relevant to this manuscript is to mention that, currently, the fastest algorithms for Disjoint Paths run in $f(k)\cdot n^2$ time for $f(k)>2^{2^{2^{2^{2^k}}}}$ on general graphs [25], and in $2^{k^{O(1)}}\cdot n$ time on planar graphs [11]. It is worth mentioning that Korhonen, Pilipczuk, and Stamoulis [28] recently provided an FPT algorithm for Disjoint Paths with almost-linear running time dependence on the number of vertices and edges, i.e., with running time $f(k)\cdot {(m+n)}^{1+o(1)}$. Also, the Disjoint Paths problem does not admit a polynomial kernel w.r.t. $k$ even on planar graphs [39], but it admits a polynomial kernel w.r.t. $k$ plus the treewidth of the input graph on planar graphs [39] (on general graphs, it is unknown whether Disjoint Paths admits a polynomial kernel w.r.t. $k$ plus treewidth).

Also quite relevant to the $T$-Cycle problem is the $k$-Cycle (or $k$-Path) problem, which is also, perhaps, the second or third most well-studied problem in Parameterized Complexity (see, e.g., the dozens of papers cited in [31]). Here, given a graph $G$ and a nonnegative integer $k$, the objective is to determine whether $G$ contains a simple cycle (or path) on $k$ vertices. The techniques used to solve $k$-Cycle can be trivially lifted to solve $T$-Cycle when parameterized by the sought size of a solution $\mathrm{\ell }$ (given as an extra parameter in the input), which can be arbitrarily larger than $T$ (e.g., in the extreme case where the entire graph is a single cycle, $\mathrm{\ell }=n$ while $k=1$). In particular, this means that, on general graphs, $T$-Cycle is solvable in time $O(2^k{1.66}^{\mathrm{\ell }-k}\cdot (n+m))$ by a randomized algorithm [4] (or time $O({2.56}^k{1.66}^{\mathrm{\ell }-k}\cdot (n+m))$ by a deterministic algorithm [37]), and on planar graphs, $T$-Cycle is solvable in time $2^{O(\sqrt{\mathrm{\ell }})}\cdot (n+m)$ by a deterministic algorithm (e.g., via [14]).

We present a high-level overview of our proofs in the next section. Here, we only briefly highlight (in a very informal manner) the novelties in our proofs, and put them in the context of the known literature. Essentially, the following theorem reveals some of the core combinatorial arguments that underlie our algorithmic results. Thus, we believe that this result may be of independent interest.

Indeed, from here, Theorem 1 directly follows by using a $2^{O(tw)}\cdot n$-time algorithm for $T$-Cycle parameterized by the treewidth $tw$ of the planar graph $G^{\prime }$ as a black box (e.g., via [14]), while Theorem 2 requires additional non-trivial work, described later in this section.

Our proof of Theorem 4 consists of three main ingredients. Towards the first ingredient, we consider a sequence of concentric cycles, and classify the “segments” of an (unknown) solution $T$-loop that go inside this sequence into types, similarly to how it is done in [2] for the Disjoint Paths problem. Here, a cheap solution is one that uses as few edges as possible that do not belong to the sequence of concentric cycles. Then, we prove the following result, which is the first ingredient.

We note that in [2], it is proved that the number of segments of the same type for a Disjoint Paths solution is $2^{O(k)}$. Our proof of Lemma 5 is based on an elegant (and novel) re-routing argument (see Section 2), which has no relation to that in [2]. This argument is, in particular, perhaps the cornerstone of the proof of Theorem 4.

With Lemma 5 at hand, we then turn to prove our second ingredient.

We note that in [2], it is proved that no segment (for a Disjoint Paths solution) goes more than $2^{O(k)}$ cycles deep into the sequence. For the proof of our lemma, we make use of one intermediate result from [2] about Disjoint Paths solutions, which states that there can be $O(k)$ segments of different types. However, besides that, the proof of our lemma is different, based on a simple analysis of the “segment-tree” induced by the segments (see Section 2). We note that rerouting arguments have been used for other terminal-based routing problems [27]. But, in our knowledge, our rerouting arguments are first to achieve a sublinear bound on the number of concentric cycles used by a cheap solution. Further, we believe that another strength of our result is that the arguments used to prove Lemma 6 are rather simple, and therefore easy to reuse in future works.

In particular, Lemma 6 implies that within a $c\log k$-sized (for some constant $c$) sequence of concentric cycles that does not contain any terminal, every vertex that lies inside the innermost cycles is irrelevant, that is, can be deleted without turning a yes-instance into a no-instance. In particular, this implies that within a $c\log k\times c\log k$-grid minor that does not contain any terminal, the “middle-most” vertex is irrelevant. Here, it is important to mention that the main component in the proof of Kawarabayashi [24] is a lemma that (essentially) states that within a $ck\times ck$-grid minor that does not contain any terminal, the “middle-most” vertex is irrelevant. Our proof (that is, the arguments briefly described so far) is completely different, and, in particular, yields an exponential improvement (from $ck$ to $c\log k$).

From here, it is easy to provide a $k^{O(1)}\cdot n^2$-time algorithm that given an instance $(G,T)$ of $T$-Cycle on planar graphs, outputs an equivalent instance $(G^{\prime },T)$ of $T$-Cycle on planar graphs such that $G^{\prime }$ is a subgraph of $G$ whose treewidth is bounded by $O(\sqrt{k}\log k)$. Indeed, this can be done by, as long as possible, computing a $c\log k\times c\log k$ grid minor that does not contain any terminal, and removing its “middle-most” vertex, where each iteration requires time $k^{O(1)}\cdot n$, and where $O(n)$ iterations are performed in total.

To reduce the time complexity to be linear in $n$, we make use of Reed’s [33] approach of dividing the plane and working on each “piece” simultaneously, together with an argument by Cho et al. [11] that further simplifies the pieces such that none of the piece contains a sequence of “too many” concentric cycles. Here, the proof is mostly based on a similar approach described in the aforementioned two papers with minor adaptations. However, we need to add one novel and critical step. Briefly, by applying the known approach (with the minor adaptations to our case) we directly obtain pieces such that: (i) the total number of vertices on their boundaries is $O(k\log k)$; (ii) no piece contains a sequence of more than $c\log k$ many concentric cycles. This already yields a set of vertices $U$ such that $|U|\in O(k\log k)$ and the treewidth of $G^{\prime }-U$ (where $G^{\prime }$ is the current graph) is bounded by $O(\log k)$, by taking the union of boundaries (that is what we need for the second item in Theorem 4). However, from this, the aforementioned two papers (i.e., [33] and [11]) directly get their tree decomposition of $G^{\prime }$ by (implicitly) creating a tree decomposition for each piece, gluing them together, and putting the vertices of $U$ in all bags. For these two previous papers, this was sufficient – they get pieces of treewidth $2^{O(k)}$ and $U$ of size $2^{O(k)}$, and thus by doing this, they do not lose anything. However, for us, this yields a tree decomposition of width $O(k\log k)$, while we need width $O(\sqrt{k}\log k)$. We overcome this by adding a new step, where we attempt to remove (possibly many) boundary vertices, and after performing this step, we are able to directly argue that the graph $G^{\prime }$ itself (rather than just each one of its pieces individually) does not have a sequence of more than $c\log k$ many concentric cycles that do not contain any terminal (see Section 2). Thus, we get the bound $O(\sqrt{k}\log k)$.

Lastly, having Theorem 4 at hand, let us address the additional work we need to perform in order to prove Theorem 2. Here, we use two powerful theorems/machineries:

• $\mathrm{■}$

  Machinery I [7] (see also [17]): Suppose we are given a set of vertices $U$ with $|U|\in O(k\log k)$ so that the treewidth of $G^{\prime }-U$ is bounded by $O(\log k)$. Then, one can construct in $k^{O(1)}\cdot n$-time a so-called protrusion decomposition of $G^{\prime }$ with “very good parameters”. That is, roughly speaking, the vertex set of $G^{\prime }$ can be partitioned into a “universal” part $U^{\star }\supseteq U$ of size $O(k{\log }^{2}k)$ and $O(k{\log }^{2}k)$ additional “protrusion” parts such that each protrusion part induces a graph of treewidth $O(\log k)$, has $O(\log k)$ many vertices that have neighbors in $U^{\star }$, while having no neighbors in the other protrusions.

• $\mathrm{■}$

  Machinery II [39]: A generalization of the Disjoint Paths problem on planar graphs, where, roughly speaking, we need to preserve the yes/no answer for every possible pairing of the terminals vertices, admits a kernel of size $O({(k^{\prime }\cdot w^{\prime })}^{12})$ where $k^{\prime }$ is the number of terminals and $w^{\prime }$ is the treewidth of the graph, and the output graph is a minor of the input graph.

Thus, we can compute the protrusion decomposition using the set obtained from Theorem 1 (which, in particular, contains all terminals), and then kernelize each of the protrusions individually using Machinery II, where the terminal set is defined as those vertices having neighbors outside the protrusion. However, this will not yield a time complexity of $k^{O(1)}\cdot n$ since Machinery II only specifies a polynomial (rather than linear) dependency on $n$, and, furthermore, this will yield a huge polylogarithmic dependency on $k$ in the size of the reduced instance.

To overcome this, we employ two novel twists in this approach. First, we create a “nested” protrusion decomposition, or, alternatively, one can think about this as “bootstrapping” the entire proof for each protrusion. In more details, for each protrusion $P$, we yet again apply all the arguments in our proofs so far to now find a set of vertices $U_P$ with $|U_P|\in O(\log k\log \log k)$ so that the treewidth of $P-U_P$ is bounded by $O(\log \log k)$. Then, for each protrusion, we yet again compute a protrusion decomposition, but now with each “subprotrusion” having only $O(\log \log k)$ many vertices with neighbors outside the subprotrusion, and with treewidth $O(\log \log k)$. Then, the second twist is that instead of directly kernelizing the subprotrusion, we think of Machinery II as an existential rather than an algorithmic result – we know that there exists a ${\log }^{O(1)}\log k$-sized graph that can replace our subprotrusion. Then, we simply guess this replacement! That is, we generate all possible ${\log }^{O(1)}\log k$-sized graphs. For each generated graph $P^{\prime }$, we test whether:

1. 1.

   $P^{\prime }$ is equivalent to the subprotrusion with the same terminal set. That is, we must preserve the yes/no answers to the instances corresponding to all possible terminal pairings.

2. 2.

   $P^{\prime }$ is a minor of $P$.

This test can be done using a standard dynamic programming-based algorithm over tree decomposition, since both the treewidth of the subprotrusion and the size of $P^{\prime }$ are bounded by ${\log }^{O(1)}\log k$. Specifically, we have many guesses for the replacement, and the “validity” of each can be checked in time $k^{O(1)}\cdot n_P$ where $n_P$ is the number of vertices in $P$. We believe that this concept of “nested” protrusion decomposition can find applications in improving kernelization algorithms, in terms of both kernel size and running time, for other terminal-based problems.

Additional discussion and related open problems can be found in Section 3.

Our first contribution is an FPT algorithm for $T$-Cycle in planar graphs that has a running time subexponential in $k$ (which is, $2^{O(\sqrt{k}\log k)}$) and linear in $n$. Since $T$-Cycle can be solved in $2^{O(\mathrm{tw})}n$ time (e.g., using [14]), a natural way to attack our problem is via the technique of treewidth reduction by removal of some irrelevant vertices. In fact, this technique was used by Kawarabayashi [24] to reduce the treewidth to be polynomial in $k$. To get the algorithm that we desire, we need to

1. 1.

   reduce the treewidth to $O(\sqrt{k}\log k)$ by removal of some irrelevant vertices, and

2. 2.

   to ensure that this entire removal procedure is performed in $k^{O(1)}\cdot n$ time.

The main tool used in our kernelization algorithm is the so-called protrusion decomposition. Please refer to [17, Chapter 15] for a detailed discussion on this topic. Below, we provide a brief overview starting with a few definitions.

Let $G$ be a graph. Given a vertex set $U\subseteq V(G)$, its boundary $\partial U$, is the set of vertices in $U$ that have at least one neighbor outside of $U$. A vertex set $W\subseteq V(G)$ is called a treewidth-$\eta$-modulator if $\mathrm{tw}(G-W)\le \eta$. A vertex set $Z\subseteq V(G)$ is a $q$-protrusion if $\mathrm{tw}(Z)\le q$ and $|\partial Z|\le q$. Finally, given a vertex set $S\subset V(G)$, we use $S^{+}=N_G[S]$ to denote the set of vertices that are in the closed neighborhood of $S$ in $G$.

A partition $X_0,X_1,\mathrm{\dots },X_{\mathrm{\ell }}$ of vertex set $V(G)$ of a graph $G$ is called an $(\alpha ,\beta ,\gamma )$-protrusion decomposition of $G$ if $\alpha$, $\beta$ and $\gamma$ are integers such that:

• $\mathrm{■}$

  $|X_0|\le \alpha$,

• $\mathrm{■}$

  $\mathrm{\ell }\le \beta$,

• $\mathrm{■}$

  $X_i$ for every $i\in [\mathrm{\ell }]$ is a $\gamma$-protrusion of $G$,

• $\mathrm{■}$

  for $i\in [\mathrm{\ell }]$, $N_G(X_i)\subseteq X_0$ (here, $N_G(X_i)$ denotes the open neighborhood of $X_i$ in $G$).

For $i\in [\mathrm{\ell }]$, the sets $X_i$ are called protrusions. For every $i\in [\mathrm{\ell }]$, we set $B_i$ = $X_i^{+}\setminus X_i$.

A central result about protrusions is that if a planar graph $G$ has a treewidth-$\eta$ modulator $S$, then $G$ has a $(O(|\eta |\cdot |S|),O(|\eta |\cdot |S|),O(|\eta |))$-protrusion decomposition with $X_0\supseteq S$ [17, Lemma 15.14]. Moreover, such a protrusion can be computed efficiently using Algorithm 1 outlined in Figure 6. The key motivation behind our use of protrusion decompositions for kernelization is Theorem 4, which readily gives us a graph $\tilde{G}$ and a vertex set $U\subset V(\tilde{G})$ of size $O(k\log k)$ that is a treewidth-$O(\log k)$-modulator of $\tilde{G}$, where $(G,T)$ and $(\tilde{G},T)$ are equivalent as $T$-Cycle instances.

Apart from protrusions, the other main tool we use is a blackbox from [39]. In [39], the authors define the notion of $B$-linkage equivalence. Specifically, two graphs $G_1,G_2$ with a common vertex set $B$ are said to be $B$-linkage equivalent w.r.t. Disjoint Paths if for every set of pairs of terminals $M\in B^2$, the disjoint path instances $(G_1,M)$ and $(G_2,M)$ are equivalent. The key result we use from [39] is that a planar graph $G$ can be replaced by a smaller planar graph $H$ that is $B$-linkage equivalent w.r.t. Disjoint Paths, where the size of $H$ is polynomial in the treewidth of $G$ and $|B|$. This leads us to our first kernelization algorithm outlined in Figure 6 that serves as a forerunner to the linear time algorithm summarized in Figure 7.

One of the key insights behind the linear time kernelization algorithm is to treat the black box result from [39] as an existential result rather than an algorithmic one. Thus, instead of using the algorithm from [39] for replacing graphs with smaller $B$-linkage equivalent counterparts, one could guess the replacement graph instead. One obstacle in doing this is that $|B_i|$ where $B_i=X_i^{+}\setminus X_i$ and the treewidth of $\tilde{G}[X_i^{+}]$ for $i\in [\mathrm{\ell }]$ are both $O(\log k)$ making the guesses expensive. A potential remedy, which is our other key insight, is to apply a nested protrusion decomposition. However, a roadblock to this remedy is that we do not have a small treewidth modulator for graphs $\tilde{G}[X_i^{+}]$ right away. This is fixed by adapting the Reed decomposition algorithm for $T$-Cycle to $B_i$-linkage equivalence w.r.t. $T$-Cycle. We stress here that the notion of linkage equivalence w.r.t. Disjoint Paths differs from the notion of linkage equivalence w.r.t. $T$-Cycle. Below, we give an intuitive definition for linkage equivalence w.r.t. $T$-Cycle.

Given a $T$-Cycle instance $(G,T)$, let $G_1$ and $G_1^{\prime }$ be subgraphs of $G$ with a common set of vertices $B\subset V(G_1)\cap V(G_1^{\prime })$. Then, $G_1$ is $B$-linkage equivalent w.r.t. $T$-Cycle to $G_1^{\prime }$ if

• $\mathrm{■}$

  a $T$-loop in $G$ can be written as a union of collections of paths ${𝒫}_1\cup {𝒫}_2$ with endpoints of paths in ${𝒫}_1\cup {𝒫}_2$ lying in $B$ such that paths in ${𝒫}_1$ use edges that belong to $G_1$ and paths in ${𝒫}_2$ use edges outside of $G_1$ if and only if in the graph $H$ obtained by replacing $G_1$ with $G_1^{\prime }$ in $G$ there is a $T$-loop that can be written as a union of collections of paths ${𝒫}_1^{\prime }\cup {𝒫}_2$ where paths in ${𝒫}_1^{\prime }$ use edges that belong to $G_1^{\prime }$.

A vertex $v\in G_1$ is $B$-linkage irrelevant if $G_1-v$ is $B$-linkage equivalent w.r.t. $T$-Cycle to $G_1$. It is easy to check that vertices that are $B$-linkage irrelevant in $G_1$ are also irrelevant for the $T$-Cycle problem in $G$.

Returning to our discussion, an adaptation of the Reed decomposition algorithm allows us to delete $B_i$-linkage irrelevant vertices from $\tilde{G}[X_i^{+}]$ for every $i\in [\mathrm{\ell }]$. This has two important outcomes. First, for every $i\in [\mathrm{\ell }]$, we get smaller graphs $G_i^{\prime }$ that are $B_i$-linkage equivalent to $\tilde{G}[X_i^{+}]$. Second, for every $i\in [\mathrm{\ell }]$, the Reed decomposition algorithm also computes sets $B_i^{\prime }\supseteq B_i$ such that the sets $B_i^{\prime }$ are treewidth-$O(\log \log k)$-modulators of $G_i^{\prime }$. In fact, the sets $B_i^{\prime }$ are boundary vertices in the Reed decomposition algorithm.

With that at hand, we can apply protrusion decomposition to graphs $G_i^{\prime }$ giving us “subprotrusions”. Specifically, computing a protrusion decomposition of $G_i^{\prime }$ for every $i\in [\mathrm{\ell }]$, gives a partition $\{Y_{i,0},\mathrm{\dots },Y_{i,m_i}\}$ of $V(G_i^{\prime })$. For $i\in [\mathrm{\ell }]$, $j\in [m_i]$, let $G_{ij}^{\prime }=G_i^{\prime }[Y_{i,j}^{+}]$, where $Y_{i,j}^{+}=N_{G_i^{\prime }}[Y_{i,j}]$, and $B_{i,j}=Y_{i,j}^{+}\setminus Y_{i,j}$. Also, let $G_{i,0}^{\prime }=G_i^{\prime }[Y_{i,0}]$ for $i\in [\mathrm{\ell }]$.

To now apply [39] as an existential result, we need to guess graphs of size ${\log }^{O(1)}\log k$. Checking if a guessed graph is $B_{i,j}$ linkage equivalent w.r.t. Disjoint Paths to a subprotrusion $G_{i,j}^{\prime }$ and replacing it while preserving planarity involves the use of two dynamic programming subroutines: Minor Containment and Disjoint Paths, the details of which can be found in Section 7 of the extended version of the paper [19]. We do these replacements for all $i\in [\mathrm{\ell }]$, $j\in [m_i]$. The replacement graphs for $G_{i,j}^{\prime }$ are denoted by $H_{i,j}^{\prime }$.

The kernel for the $T$-Cycle problem is given by assembling the graph $K^{\prime }$ where

Figure 7 outlines the key steps in the linear time kernelization algorithm. We show in Section 7 of the extended version of the paper [19] that $|V(K^{\prime })|\le k{\log }^{4}k$, and $K^{\prime }$ can be computed in $k^{O(1)}\cdot n$ time.