Tight Bounds for Connected Odd Cycle Transversal Parameterized by Clique-Width

Parameterized complexity studies the fine-grained complexity of problems by analyzing the dependence of the running time on different measures of the input (called parameters) in addition to its size. Typical parameters are the solution size or structural measures relating, e.g., to sparsity or the existence of certain decompositions of the input. We refer to [12] for an introduction to the field. A central goal is to determine whether a problem with chosen parameter $t$ can be solved in time $f(t)\cdot n^{𝒪(1)}$ where $f$ is an arbitrary computable function and $n$ is the input size. Such problems are called fixed-parameter tractable and form the class FPT. While in general the dependence on $t$ may be arbitrary, there is much interest in making this as low as possible and possibly establishing conditional optimality of obtained time bounds.

The most studied parameter in this direction is the treewidth (of a graph), a measure that sparks interest in different areas of theoretical computer science, not only parameterized complexity. Roughly, the treewidth of a graph $G$ is the smallest value $k$ such that $G$ can be fully decomposed along non-crossing separators of size $k$. FPT algorithms with single exponential dependence on the treewidth of the graph have long been known for many problems. However, one would still try to improve the exponential dependence on the parameter, by improving the base of the exponent in the running time. In 2010, Lokshtanov et al. [33, 34] provided the first tight lower bounds for problems parameterized by treewidth, proving that known bases for some benchmark problems cannot be improved assuming the strong exponential time hypothesis (SETH), a widely used hypothesis that, informally speaking, conjectures that the naive solution of the SAT problem by testing all possible assignments is essentially optimal [27, 28]. This has inspired a series of SETH based lower bounds for structural parameters [11, 16, 36, 32, 22, 24].

Connectivity problems like Steiner Tree or Feedback Vertex Set, however, resisted single exponential running time algorithms for a long time. A major obstacle had been keeping track of different connectivity patterns in the boundary of the graph, representing different partial solutions in this graph. This seemed to necessitate a factor of $k^{𝒪(k)}$ in the running time. In 2011, Cygan et al. [14, 15] showed that this issue can be overcome for many (but not all) connectivity problems, by means of their Cut&Count technique. The core idea is to count the number of connected solutions of a problem modulo 2 in single exponential time by counting the ways that (possibly disconnected) solution candidates can be cut. They used the isolation lemma [35] to solve the underlying decision problem with high probability. Finally, they also proved that many of the resulting bases were tight under SETH.

Relying on the Cut&Count technique, tight bounds for connectivity problems were also derived relative to parameters such as pathwidth [13], cutwidth [6], modular treewidth [25], and clique-width [24, 8]. In this paper, we focus on Clique-width, a graph parameter defined by the smallest value $k$, such that a given graph can be built recursively from the disjoint union of $k$-labeled graphs, by allowing to add bicliques between the vertices of two label classes, and to relabel all vertices in a class. Clique-width is a more general parameter than treewidth, since cliques have clique-width at most $2$, and unbounded treewidth, while graphs of treewidth $k$ have bounded clique-width (at most $2^{𝒪(k)}$) [10, 9].

The first single exponential time algorithms for connectivity problems parameterized by clique-width, to the best of our knowledge, were given by Bergougnoux and Kanté [2]. However, the first SETH-tight bounds were given by Hegerfeld and Kratsch [24], where they provided algorithms, based on the Cut&Count technique, and matching SETH-based lower bounds for the Connected Vertex Cover and the Connected Dominating Set problems. They left open however, the tight complexity of other connectivity problems such as Steiner Tree and the Connected Odd Cycle Transversal. A major obstacle towards finding the optimal base of the exponent, as they mention, is a gap between the rank of a matrix defined by the interactions of partial solutions of the underlying problem (called the compatibility matrix), and its largest triangular submatrix. Except for a handful examples (Feedback Vertex Set [$\mathrm{ctw}$] [6]), the rank of such matrices has usually been used directly to derive the optimal running time, while current lower bound techniques usually match the size of a largest triangular submatrix.

Very recently Bojikian and Kratsch [8] introduced a new technique called “isolating a representative” closing the gap for the Steiner Tree problem. Their technique is based on a smaller set of possible representations of connectivity patterns. They showed that one can count the number of these representations (modulo 2) in time proportional to the size of a largest triangular submatrix of the corresponding compatibility matrix. They introduced the notion of action-sequences to distinguish different representations of the same solution, and using the isolation lemma to also isolate a unique representation, they were able to solve the underlying decision problem in the same running time, matching known lower bounds.

We denote by $[k]$ the set $\{1,2,\mathrm{\dots }k\}$ and by ${[k]}_0$ the set $[k]\cup \{0\}$. A labeled graph is a graph $G=(V,E)$ together with a labeling function $\mathrm{lab}:V\to \mathbb{N}$. We usually omit $\mathrm{lab}$ and assume that it is given implicitly with $G$. We define a clique-expression $\mu$ as a well-formed expression defined by the following operations on labeled graphs:

• $\mathrm{■}$

  Introduce vertex $i(v)$ for $i\in \mathbb{N}$: constructs a graph with a single vertex labeled $i$.

• $\mathrm{■}$

  Union $G_1\uplus G_2$: the disjoint union of $G_1$ and $G_2$.

• $\mathrm{■}$

  Relabel ${\rho }_{i\to j}(G)$ for $i\ne j\in \mathbb{N}$: change the label of all vertices labeled $i$ to $j$.

• $\mathrm{■}$

  Join ${\eta }_{i,j}(G)$ for $i\ne j\in \mathbb{N}$: add all edges between vertices labeled $i$ and vertices labeled $j$.

We denote the graph resulting from a clique-expression $\mu$ by $G_{\mu }$, and the constructed labeling function by ${\mathrm{lab}}_{\mu }$. We associate with a clique-expression $\mu$ a syntax tree ${𝒯}_{\mu }$ in the natural way, and associate with each node $x\in V(𝒯)$ the corresponding operation. Let ${𝒱}_{\mu }=V({𝒯}_{\mu })$. We omit $\mu$ when clear from the context. The subtree rooted at each node $x$ induces a subexpression ${\mu }_x$. We define $G_x=G_{{\mu }_x}$, $V_x=V(G_x)$, $E_x=E(G_x)$, ${\mathrm{lab}}_x={\mathrm{lab}}_{{\mu }_x}$, ${𝒯}_x={𝒯}_{{\mu }_x}$, and ${𝒱}_x={𝒱}_{{\mu }_x}$. We also define the set ${𝒱}_x^C$ as the set of all introduce nodes in ${𝒯}_x$, and ${𝒱}_x^{CJ}$ as the set of all introduce and join nodes in ${𝒯}_x$. Given a set $S\subseteq V$, we define $S_x=S\cap V_x$. For a mapping $g:S\to U$, we denote by $g_x$ the mapping $g_{|S_x}$, i.e. the restriction of $g$ to $S\cap V_x$.

We call a clique-expression $\mu$ linear, if it holds for each union node $x$ with children $x_1$ and $x_2$ that ${\mu }_{x_2}$ is an introduce operation. We say that $G$ is $k$-labeled, if it holds that $\mathrm{lab}(v)\le k$ for all $v\in V(G)$. We say that a clique-expression $\mu$ is a $k$-expression if $G_x$ is a $k$-labeled graph for all $x\in 𝒱$. We define the (linear) clique-width of a graph $G$, denoted by $\mathrm{cw}(G)$ ($\mathrm{lcw}(G)$ resp.) as the smallest value $k$ such that there exists a (linear) $k$-expression $\mu$, with $G_{\mu }$ isomorphic to $G$. We can assume without loss of generality, that any given $k$-expression defining a graph $G=(V,E)$ uses at most $O(|V|)$ union operations, and at most $O(|V|k^2)$ unary operations [2, 10].

A mapping $g:V\to [q]$, for $q\in \mathbb{N}$, is a proper $q$-coloring of $G$, iff for all $\{u,v\}\in E$ it holds that $g(u)\ne g(v)$. A graph $G$ is $q$-colorable if it admits a proper $q$-coloring. A set $S\subseteq V$ is an odd cycle transversal of $G$, if $G\setminus S$ is $2$-colorable. In this case, we call a proper $2$-coloring $g$ of $G\setminus S$ a witness. In the Connected Odd Cycle Transversal problem, given is a graph $G$ and a positive integer $\overline{b}$, asked is whether $G$ admits an odd cycle transversal $S$ of size at most $\overline{b}$, such that $S$ induces a connected subgraph of $G$.

We denote the symmetric difference by $\mathrm{\Delta }$. A weight function $\omega$ is a mapping from a set $U$ to some ring (usually $\mathbb{Z}$). Given $S\subseteq U$, we define $\omega (S)={\sum }_{u\in S}\omega (u)$. Let $f:U^k\to U$ be a mapping (not explicitly defined as a weight function). For $S_1,\mathrm{\dots }{S}_k\subseteq U$, we define $f(S_1,\mathrm{\dots }{S}_k)=\{f(u_1,\mathrm{\dots },u_k):u_i\in S_i\}$. For $S\subseteq U$, we define $f^{-1}(S)$ in a natural way. Finally, we define the operation $\stackrel{△}{f}:{(2^U)}^k\to 2^U$ with $\stackrel{△}{f}(S_1,\mathrm{\dots },S_k)={△}_{(u_1,\mathrm{\dots },u_k)\in S_1\times \mathrm{\cdots }\times S_k}\left\{f(u_1,\mathrm{\dots },u_k)\right\},$ and call it exclusive $f$. We define the union of two mappings $f\dot{\cup }g$ over disjoint domains in a natural way.

A short introduction to lattices can be found in the full version. For a lattice $(ℒ,\le )$, we define the set of join-irreducible elements ${ℒ}_{\vee }\subseteq ℒ$ as the set of elements $u\in ℒ$ where for all $v,w\in ℒ$ with $u=v\vee w$ it holds that $u=v$ or $u=w$. We say that a lattice $(ℒ,\le )$ is given in the join representation if its elements are given as $𝒪(\log |ℒ|)$-bit strings, together with the elements of ${ℒ}_{\vee }$, and an algorithm ${𝒜}_{ℒ}$ that computes the join $u\vee v$ for $u\in ℒ$ and $v\in {ℒ}_{\vee }$.

Let $A,B\in {𝔽}^{ℒ}$ be two vectors over a ring $𝔽$. We define the $\vee$-product $A\otimes B\in {𝔽}^{ℒ}$ where for $z\in ℒ$ it holds that $A\otimes B[z]={\sum }_{\begin{array}{c}x,y\in ℒ\\ x\vee y=z\end{array}}A[x]\cdot B[y]$. We refer to the full version for details.

Patterns are structures that represent connectivity in labeled graphs. We use the definition of patterns and some of their properties from [8]. A pattern $p$ is a set of subsets of $U_0$, such that there exists exactly one set $Z_p\in p$ that contains the element $0$ in it. We call this set the zero-set of $p$. We denote by $𝒫$ the family of all patterns. Let $\mathrm{label}(p)\subseteq U$ be set of labels that appear in at least one set of $p$, and $\mathrm{singleton}(p)\subseteq U$ the set of labels that appear as singletons in $p$ (excluding the element $0$). We define the set of incomplete labels $\mathrm{inc}(p)=\mathrm{label}(p)\setminus \mathrm{singleton}(p)$. We denote a pattern $\{\{i_1^1,\mathrm{\dots },i_{k_1}^1\},\mathrm{\dots },\{i_1^{\mathrm{\ell }},\mathrm{\dots },i_{k_{\mathrm{\ell }}}^{\mathrm{\ell }}\}\}$ by $[i_1^1\mathrm{\dots }{i}_{k_1}^1\mathbf{,}\mathrm{\cdots }\mathbf{,}{i}_1^{\mathrm{\ell }}\mathrm{\dots }{i}_{k_{\mathrm{\ell }}}^{\mathrm{\ell }}]$, but only if this notation does not cause confusion. We also omit the zero-set when it is a singleton.

Such patterns carry enough information about the connectivity of partial solutions. We define pattern operations, that allow us to build connectivity patterns corresponding to different partial solutions recursively over the nodes of $𝒯$ (see [8] for details).

As we shall see later, these operations allow to build all patterns corresponding to all partial solutions of a fixed size over $𝒯$. This can be done by deciding at each leaf node, whether to include the introduced vertex in the solution or not. One can then compute these families at each node by applying the corresponding pattern operations on the families at the children nodes of this node. It is not hard to see that a union node corresponds to a union operation, a relabel node corresponds to a relabel operation, and a join node to an add operation. A correctness proof of this is given later implicitly, when proving that the so-called solution-sequences correspond to all partial solutions of a given weight.

Now we define the compatibility relation over patterns. This relation indicates whether two partial solutions in two labeled subgraphs join into a connected graph by connecting all vertices of the same label between them. Formally, we call two patterns $p$ and $q$ compatible ($p\sim q$), if their join is a single set.

This notion of compatibility will allow us to define two kinds of representation, an existential one (representation), and a (modulo 2) count-preserving one (parity-representation). Based on these, we identify two special families of patterns, namely the family of complete patterns ${𝒫}_C$ and the family of $CS$-patterns ${𝒫}_{CS}$. We will show later that one can represent each family of patterns by a family of complete patterns, and parity-represent each family of complete patterns by a family of $CS$-patterns.

We will show that all defined pattern operations preserve (parity-)representation, in the sense that if $R$ represents $S$, then $\mathrm{Op}(R)$ represents $\mathrm{Op}(S)$ as well. Therefore, we can replace the families of patterns of all partial solutions over $𝒯$ by representations thereof, which allows us to restrict the dynamic programming algorithm to $CS$-patterns only, correctly counting (modulo 2) the number of all representations of all solutions. Therefore, the running time will depend on the number of $CS$-patterns over $k$ labels instead of the number of all patterns.

Finally, we use the isolation lemma to show that, by assigning random weights to the different representations of different partial solutions, we get a unique minimum-weight representation with high probability. This allows to solve the decision problem in the given time. The running time is implied by the number of $CS$-patterns over $k$ labels, combined with a proper $2$-coloring of the remaining part of the graph.

Before we present the algorithm, we still need to define the notion of actions and the operation $PREP$. Actions are series of “forget” and “fix” operations over patterns, that build a representation of a pattern by deciding whether a given label will still be relevant (in the future) for deciding the connectivity of a solution. Using actions, we build an equivalent representations of all partial solutions recursively over $𝒯$ using complete patterns only. The operation $PREP$ is then used to create a parity-representation thereof, consisting of $CS$-patterns only.

It was shown in [8] that $\{\mathrm{fix}(p,i),\mathrm{forget}(p,i)\}$ represents $p$. Hence, by applying the actions $\mathrm{Ac}(p,\mathrm{\ell })$ for $\mathrm{\ell }\in [4]$ on a pattern $p$ with $|\mathrm{inc}(p)|\le 2$, we get a family of complete patterns that represents $p$. It is not hard to see that applying pattern operations on $CS$-patterns yields patterns $p$ with $|\mathrm{inc}(p)|\le 2$. In particular, ${𝒫}_{CS}$ is closed under union and relabeling, whereas for $p\in {𝒫}_{CS}$ and $q={\mathrm{\square }}_{i,j}p$, it holds that $\mathrm{inc}(q)\subseteq \{i,j\}$.

Note that each pattern of $PREP(p)$ results from $p$ by removing all non-singleton sets different from $Z_p$, and adding some subset of their union to $Z_p$.

Now we present our main result, namely a dynamic programming algorithm over $𝒯$. We start by defining the family of states $ℐ$ that we use to index the dynamic programming tables.

Now we introduce solution-sequences and action-sequences. A solution-sequence is defined by the actions taken at all introduce nodes in a subtree of $𝒯$ to create a partial solution (together with a witness thereof). We show a bijective mapping between solution-sequences at a node and partial solutions (combined with witnesses) at that node. An action-sequence is defined by the actions taken at both introduce and join nodes in a subtree of $𝒯$, encoding the forget and fix operations along $𝒯$. Each action-sequence corresponds to a different representation of a partial solution. Intuitively, the set of all action-sequences extending a solution-sequence build a full complete-pattern representation of the corresponding partial solution.

Intuitively, ${\mathrm{col}}_G^g$ is the coloring defined by assigning to each label $\mathrm{\ell }$ the join of all basic colors assigned to vertices labeled $\mathrm{\ell }$ in $S$, or $\mathbf{\varnothing }$ if no such vertex exists. Hence, it indicates the colors assigned to each label in a witness of a partial solution.

From now on, we shorthand ${\mathrm{pat}}_x(S)$ for ${\mathrm{pat}}_{G_x}(S)$, and ${\mathrm{col}}_x^g$ for ${\mathrm{col}}_{G_x}^g$.

The notion of valid sequences ensures the validity of witnesses, as it forbids adding edges between vertices of the same color. Now we show the correspondence between solution-sequences and partial solutions at a node $x$.

This forms a bijective mapping between the family of partial solutions at a node $x$ and the family of all solution-sequences at $x$. In the full version, we show that $b(\pi )=|S|$, ${\mathrm{pat}}_x(S)=o_{\pi }$, ${\mathrm{col}}_x^g=c_{\pi }$. We also prove that $g$ is a proper 2-coloring of $G_x[V_x\setminus S]$ if and only if $\pi$ is valid. Now we show that action-sequences represent partial solutions.

We show in the full version (and from [8]) that pattern operations and actions preserve both representation and parity-representation over ${𝒫}_C$, in the sense that if $R$ (parity-) represents $S$, then $\mathrm{Op}(R)$ (parity-)represents $\mathrm{Op}(S)$. It was also shown in [8] that the four actions over a pattern $p$ with $|\mathrm{inc}(p)|\le 4$ represent $p$. Therefore, one can show by induction over $𝒯$ that the family of patterns corresponding to valid action-sequences at a node $x$ represents the family of patterns corresponding to valid solution-sequences at $x$, and hence, represents all partial solutions at $x$ as well. The following result follows:

All that is left to show is that the algorithm correctly counts (modulo 2) the number of valid action-sequences of cost $b$ and weight $w$ at each node $x$ that generate a pair $(p,c)$, where $p\sim q$ for some complete pattern $q\in {𝒫}_C$. In order to show this, we prove that $PREP(p)$ parity-represents $p$ over ${𝒫}_C$ for any $p\in {𝒫}_C$. Based on this, together with the fact that all defined operations preserve parity-representation over ${𝒫}_C$, we prove the following lemma:

The following corollary follows directly from Lemma 6:

So far, we have shown that the algorithm correctly counts the number of action-sequences of a specific weight, generating a pair $([0],c)$ for any coloring $c$. We make use of the isolation lemma [35], to show that by a careful choice of the value $W$ and the weight function $\omega$, we get a unique minimum weight sequence with high probability if a solution exists.

We prove Theorem 2 through a parameterized reduction from the $d$-SAT problem for each constant $d$, proving that an algorithm running in time ${𝒪}^{\ast }({(12-\epsilon )}^{\mathrm{cw}})$ for some $\epsilon \ge 0$ contradicts SETH. Let $I$ be the given instance with clauses $C_1,\mathrm{\dots },C_m$ over variables $v_1,\mathrm{\dots },v_n$. We refer to the full version for details. We start by a formal statement of SETH.

In this work, we have provided a single-sided error Monte Carlo algorithm for the Connected Odd Cycle Transversal problem with running time ${𝒪}^{\ast }({12}^{\mathrm{cw}})$, presenting a new application of the “isolating a representative” technique by [6]. We proved that the running time is tight assuming SETH. This closes the second open problem posed by Hegerfeld and Kratsch [24]. However, one more interesting benchmark problem is still open, namely the Feedback Vertex Set problem. As mentioned in their paper, solving this problem using the Cut&Count technique is challenging, since a direct application would require counting edges induced by partial solutions. Another approach would be to follow the approach of Bojikian and Kratsch [8]. The difficulty of such application lays in finding a low $\mathrm{GF}(2)$-rank representation of partial solutions.

Since both related techniques – the Cut&Count technique [15] and the rank-based approach [5] – were used to solve connectivity problems more efficiently under different structural parameters, it is natural to ask whether the approach of Bojikian and Kratsch [8] can likewise be adapted to different settings. In particular, one would ask whether this results in tight bounds for different connectivity problems under different parameters, where there also exists a gap between the rank of a corresponding compatibility matrix, and the size of a largest triangular submatrix thereof.