Tight Bounds for Feedback Vertex Set Parameterized by Clique-Width

In order to solve the Connected Feedback Vertex Set problem parameterized by clique-width, we need to ensure the connectivity of the solution set in addition to the acyclicity of the remaining graph. We obtain an SETH-tight algorithm with running time $𝒪({18}^{\mathrm{cw}}{n}^c)$ by combining our acyclicity representation with a connectivity representation technique that was introduced recently by Bojikian and Kratsch [8], called “isolating a representative”. Each partial solution $X$ is first represented by its connectivity pattern, defined as a set of subsets of labels, where we add a set for each connected component $C$ of $G_x[X]$ that contains the labels of all vertices of $C$. In contrast to acyclicity representation, where we needed to distinguish whether a label appears once or at least twice in a connected component, and whether copies of different components exist once or at least twice, to represent connectivity it suffices to track existence, and hence, simple sets of labels suffice to represent connectivity.

However, a parity-preserving replacement argument, similar to the one used for Feedback Vertex Set, would only reduce the size of the family to $4^k$ (where each label has a state $𝑶$, $𝑫$, $𝑪$, or ${𝑪}^{+}$). Instead, following the approach of [8] we first use an “existential representation” step, where the representing family does not preserve the parity of the number of compatible partial solutions, but only preserves the existence of a compatible partial solution: We define local operations, called actions over the nodes of $𝒯$ that decide for a given label (with state $𝑪$) whether it will be used in the future to connect different components of a partial solution (and hence, it can be added as a singleton safely, turning its state to ${𝑪}^{+}$), or will not be used anymore (and hence, it can be safely removed from all sets, turning its state to $𝑶$). The resulting family can then be reduced to size $3^k$ by a parity-preserving reduction argument similar to the one above.

A priori, we cannot usefully combine existential and parity representation. Even after the usual isolation of a solution, we have no control over the parity of the number of representations, so working modulo two makes no sense. The key idea of [8] is that after isolating (with high probability) a unique minimum weight solution by giving random weights to vertices, we can furthermore isolate (w.h.p.) a unique representation by giving random weights to the possible actions at each node. More formally, what we isolate is a minimum weight action sequence – the mapping that decides which actions are taken to produce a single representation of a unique minimum weight solution by assigning an integer in $[4]$ to each node. In this way, the remaining parity-based arguments work correctly.

Accordingly, our partial solutions are pairs of a vertex set $X$ and an action sequence $\pi$, where we index the dynamic programming tables by the acyclicity-pattern of $G\setminus X$ and by the connectivity-pattern of the representative created by $\pi$ from the partial solution $X$. This results in $6\cdot 3=18$ states per label. Again, we need to efficiently process union nodes in the clique expression. We build upon the convolution technique introduced above, extending it to a $4$-level convolution, where we start by processing the connectivity part of the pattern. We show that this can be done in time $𝒪({18}^k{n}^c)$, resulting in the claimed running time.

Finally, in order to count modulo two the number of feedback vertex sets of a specific size when parameterized by treewidth, we make use of the same acyclicity representation technique. Essentially, in a tree decomposition, each vertex appears in a bag at most once, compared to labels in a labeled graph, while the size of the bags is bounded by the parameter. We start by defining a mapping $\varphi$ that assigns to each vertex in the graph a label $i\in [k+1]$ such that the restriction of $\varphi$ to each bag is injective. Using these labels, we can restrict the family of all patterns to patterns where each label appears at most once. This allows us to replace vectors that count the multiplicity of each label in each connected component by the sets of labels that appear in each connected component, and to replace the multisets of vectors by simple sets, since we cannot have two components containing the same labels. This simplifies the definition of patterns to sets of disjoint subsets of $[k]$ – each corresponding to a different connected component. Essentially, it reduces the six states defined above into the “single” states $𝑶$, $𝑫$, and $𝑪$ resulting in the family of nice treewidth patterns ${𝒯}_{CS}$ of size $3^{k+1}$. We use this family to index the dynamic programming tables.

Similar to the algorithm when parameterized by clique-width, join nodes form a bottleneck in this dynamic programming routine, where we need to efficiently combine all pairs of partial solutions in the two children bags. We show that this can be done in time $𝒪(3^k{n}^c)$ by introducing an ordering over these states, and showing that the required convolution corresponds to the join product of the $k$th power of the corresponding lattice. We refer to the full version [9] for details. The running time then follows from a result by Hegerfeld and Kratsch [18] that shows how to compute such convolutions efficiently.

In our lower bounds, we follow the general framework of SETH based reductions for structural parameters debuted by Lokshtanov et al. [24]. However, instead of reducing from the $d$-SAT problem, we follow the approach of Lampis [22] reducing from the $q$-CSP-$B$ problem defined as follows: Given is a set of $n$ variables and a set of $m$ constraints for some integer values $n$ and $m$, where each constraint is defined over $q$ variables and specifies which assignments of values from the set $[B]$ to these variables are allowed. The goal is to decide whether there exists an assignment of values from $[B]$ to all variables such that all constraints are satisfied.

The lower bound is then based on a result from [22], which informally states that for each fixed integer $B\ge 2$ and for each value $\delta >0$, there exists an integer $q$, such that the $q$-CSP-$B$ problem cannot be solved in time $𝒪({(B-\delta )}^n)$, unless SETH fails. Therefore, for our lower bound for Feedback Vertex Set, we choose $B=6$, and provide a reduction for each value of $q$ from the $q$-CSP-$6$ problem to Feedback Vertex Set.

Intuitively, we translate each variable into a gadget of constant size, called path gadget. We make use of the six states $𝑶$, $𝑫$, $𝑪$, ${𝑫}^{\ast }$, ${𝑪}^{+}$, and ${𝑪}^{\ast }$ defined above and translate the intersection of a solution with this gadget into one of these states. We also fix a bijective mapping from these states to the different assignments of a value from the set $[6]$ to the corresponding variable. We also define a so called constraint gadget corresponding to each constraint $C$. We define the adjacencies between a constraint gadget and the path gadgets in a way that ensures that the states defined in the path gadgets by a solution correspond to an assignment that satisfies the constraint $C$.

In order to find an assignment that satisfies all constraints, we will add $m$ copies of a path gadget for each variable $v$, each corresponding to a different constraint, where consecutive copies are connected by bicliques of size $4$, spanning two “exit vertices” of each gadget, and two “entry vertices” of the following gadget, resulting in a path sequence corresponding to each variable $v$. This results in a grid structure, where each row is a sequence of path gadgets corresponding to a variable $v$, and each column corresponds to a constraint $C$. We attach a corresponding constraint gadget to each column. See Figure 4 for a graphical depiction of the reduction.

The symmetric “biclique” cuts between consecutive path gadgets ensure that we can build all these sequences by “spending” a single label (unit of clique-width) for each path sequence, and a constant number of labels for the rest of the graph, building the whole graph column by column, which bounds the clique-width of the resulting graph. We show that these cuts are exactly enough to transition these six states.

However, these transitions have one final shortcoming: Instead of enforcing identical states in consecutive path gadgets, they only guarantee a monotone behavior, implicitly inducing a partial ordering over the six states. This behavior is common in SETH-based lower bounds, and a solution was already proposed by Lokshtanov et al. [24]: By adding $5n+1$ copies of these sequences of path gadgets corresponding to each variable – turning them into sequences over $(5n+1)m$ path gadgets – we ensure that in any solution, there exists at least one copy in which all path gadgets on each sequence are assigned the same state. This holds since between $6$ different states at most $5$ state-changes can happen under a monotone transition. The state assignment defined by this copy corresponds to an assignment that satisfies all constraints. Building on this, we show that the given instance is satisfiable, if and only if the resulting graph admits a feedback vertex set of a specific size.

For the Connected Feedback Vertex Set problem, we follow the same general schema. However, in order to achieve the base $18$, we combine an acyclicity state with a connectivity state, resulting in $6\cdot 3=18$ states per label, where an acyclicity state defines how a label appears in an induced forest, while a connectivity state defines the connectivity of a label in the solution set itself. However, a challenge arises, since states like $(𝑶,𝑶)$ are not realizable, while the upper bound realizes them through the existential representation technique mentioned above, and hence, they cannot be trimmed.

In order to overcome this challenge, we make use of the fact, that connectivity representation from [8] is a two-step existential representation, that turns a set of $4$ states into $3$ required states for connectivity. Hence, we make use of the “fourth” redundant state, and make careful choices of which $3$ connectivity states to combine with each acyclicity state. This does not only result in $18$ realizable states, but also results in combinations that allow for simpler realization, allowing to realize each state using three “boundary” vertices instead of four in a more straightforward approach.