MaxMin Separation Problems: FPT Algorithms for $st$-Separator and Odd Cycle Transversal

Given the extensive study of the Vertex Cover problem in parameterized complexity, the parameterized complexity MaxMin Vertex Cover has naturally garnered significant attention [30, 8, 31, 2]. More recently, MaxMin Feedback Vertex Set problem has also been explored in [13, 24], where several faster FPT algorithms are proposed. The MaxMin Upper Dominating Set problem has been studied in [1, 3, 5, 14], and its edge variant, the MaxMin Upper Edge Dominating Set, is addressed in [28, 17]. Additionally, MaxMin and MinMax formulations have been investigated for a range of other problems, including cut and separation problems [23, 12], knapsack problems [18, 16], matching problems [9], and coloring problems [6]. We elaborate more on the literature around MaxMin versions of cut and separation problems in the later paragraph.

We remark that for most problems mentioned in the paragraph above, showing that they are FPT parameterized by the solution size is not very difficult (though designing faster FPT algorithms could be much challenging and require deep problem-specific combinatorial insights). The reason is that it is easy to bound the treewidth of the input graph: find a greedy packing of obstructions (edges for MaxMin Vertex Cover and cycles for MaxMin Feedback Vertex Set); if the packing size is at least $k$, then the instance is a yes-instance, otherwise there exists a vertex cover (resp. feedback vertex set) of the input graph, of size at most $2k$ (resp. $𝒪(k\log k)$ from the Erdös-Pósa theorem). In both case, the treewidth of the graph is bounded by a function of $k$. Since these problems are expressible in Monadic Second Order (MSO) Logic, from Courcelle’s theorem a linear-time FPT in $k$ algorithm follows.

The key challenge in the study of cut and separation problems, in contrast to the vertex/edge-deletion problems mentioned in the paragraph above, is that it is not always easy to bound the treewidth of the instances. Having said that the existing work on MaxMin versions of cut and separation problems are still based on treewidth win-win approaches as explained below.

Hanaka et al. [20] studied the parameterized complexity of the MaxMin Separator problem. Here the input is only a connected graph $G$ and a positive integer $k$, and the goal is to find a minimal vertex set of size at least $k$ whose deletion disconnects the graph. This problem has an easy FPT algorithm parameterized by $k$ based on a win-win approach: if the input graph has large treewidth, then it has a large grid-minor which implies the existence of a large solution; otherwise the treewidth is bounded and since the problem is expressible in MSO, one can solve the problem in linear time on bounded treewidth graphs. Note that this approach completely fails when we are looking for an $st$-separator (which is the problem we attack in the present work) for fixed vertices $s$ and $t$. In particular, a large grid minor does not necessarily imply a large $st$-separator.

In the same work Hanaka et al. designed an explicit FPT algorithm parameterized by treewidth for the MaxMin $st$-Sep problem and left open the question of determining the parameterized complexity of MaxMin $st$-Sep parameterized by the solution size $k$.

Common techniques like flow augmentation [22] and treewidth reduction [27] are not suitable for solving the Maximum Minimal $st$-Separator problem. This is because the size of the solution in this problem can be arbitrarily large, rather than being bounded by a function of $k$. When the solution size is unbounded, these methods fail to simplify the problem or give meaningful reductions. We also considered the idea to reduce the problem to a scenario where the solution size is bounded by some function of $k$ using some win-win approach, and then use techniques like treewidth-reduction, unbreakable tree decompositions or even flow-augmentation. But showing the first part seemed tricky and even if one shows that the solution size is bounded, it is still not straightforward to use these classical cut-based techniques as maintaining certificates of minimality of a partial solution is hard in general.

Later Duarte et al. [12] studied the edge-deletion variant of the MaxMin $st$-Sep problem. They termed it the Largest $st$-Bond problem and showed, amongst other results, that it is FPT parameterized by the solution size $k$. At the core of this algorithm is another treewidth-based win-win approach, which seems hard to generalize to the vertex-deletion case.

In this work, for the first time, we use the power of highly unbreakable instances to show fixed-parameter tractability of some MaxMin separation problems. For two positive integers $q,k$, a graph $G$ is called $(q,k)$-unbreakable if no vertex set of size at most $k$ can disconnect two (large) sets of size at least $q$ each. For the purposes of an informal discussion, we say a graph is unbreakable if it is $(q,k)$-unbreakable for some values of $q$ and $k$.

Chitnis et al. [10] developed a win-win approach based on this unbreakable structure of the graph. The approach has two parts: recursive understanding and randomized contractions. In the first part, a large enough part of the input graph is detected that is unbreakable and has small boundary to the rest of the graph. In the second part, a family of “partial solutions” are computed for this unbreakable part of the graph depending on how the solution for the whole graph interacts with its boundary. If the unbreakable part is large enough, then there exists an irrelevant edge/vertex that does not participate in the computed partial solutions, which helps in reducing the size of the graph.

Unfortunately, at the first glance it looks impossible to use this approach for solving any of the two problems MaxMin $st$-Sep and MaxMin OCT. The problem is that in the above approach one needs to find partial solutions on unbreakable graphs for a more general “extension-kind” of problem. In particular, the family of partial solutions should be such that if there exists a solution for the whole graph, then one should be able to replace the part of this solution that intersects with the unbreakable part, with one of the computed partial solutions. To do so, for example, it seems necessary to, in some implicit way at least, guess how an optimum solution of the whole graph intersects with the boundary of this unbreakable part and the partial solution should at least try to be “compatible” with this guess. The bottleneck here is that given a vertex $v$, finding whether the graph $G$ has any minimal $st$-separator containing $v$ is NP-hard (see Lemmas 1 and 2). Thus, the problem of determining, given a subset of vertices $X$, whether $G$ has a minimal $st$-separator of size at least $k$, that contains $X$, is W[1]-hard (it is in fact para-NP-hard).

For the first part, assume there exists a minimal $st$-separator $Z$ that contains $v$. By the minimality of $Z$, there must be a path $P$ between $s$ and $t$ in the graph $G-(Z\setminus \{v\})$, which passes through $v$. In other words, path $P$ is such that no vertex in $Z$ other than $v$ appears on it. However, since there is no induced path between $s$ and $t$ through $v$, two vertices, say $a$ and $b$, on $P$ must be adjacent, with $a$ lying between $s$ and $v$, and $b$ lying between $v$ and $t$. This creates a new path between $s$ and $t$ that does not include any vertex from $Z$, contradicting the assumption that $Z$ is an $st$-separator.

For the second part, if there exists an induced path between $s$ and $t$ passing through $v$, we can construct a minimal $st$-separator $Z$ that includes $v$. According to Definition 13, let $S$ be the set of all vertices on the induced path from $s$ to $a$, and $T$ the set of all vertices on the induced path from $b$ to $t$, where $a$ is a predecessor of $v$ and $b$ a successor of $v$. These sets, $S$ and $T$, serve as a certificate for the $st$-separator minimality for $v$. By Lemma 14, we can then construct a minimal $st$-separator that contains $v$. $◀$

Therefore, a first glance suggests that computing “partial solutions” may be W[1]-hard in general. One can ask if the hardness holds even when the graph is unbreakable (which is our scenario). It turns out yes, because a result by Lokshtanov et al. [26], shows that the FPT algorithm for unbreakable graphs can be lifted to an FPT algorithm on general graphs for problems definable in Counting Monadic Second Order (CMSO) Logic. Since the extension version is also CMSO definable, there shouldn’t be an FPT algorithm for the extension version even on unbreakable graphs.

Despite this issue, we show that the core lies in solving the problem on unbreakable graphs, and in fact the problem on unbreakable graphs is FPT using non-trivial insights. In fact the result of Lokshtanov et al. [26] comes to rescue. In [26] Lokshtanov et al. show that, in order to show fixed-parameter tractability of CMSO definable problems parameterized by the solution size (say $k$), it is enough to design FPT algorithms for such problems when the input graph is $(q,k)$-unbreakable, for some large enough $q$ that depends only on $k$ and the problem. The highlight of this result, compared to explicitly doing the above-mentioned approach of recursive understanding and randomized contractions is that, this results says that it is enough to solve the same problem on unbreakable graphs. This allows us to skip taking the provably hard route of dealing with extension-kind problems.

After overcoming the above issues, we can safely say that the core lies in designing an FPT algorithm for the unbreakable case, which itself is far from obvious. We give a technical overview of this phase in Section 1.1.

The challenges continue for the MaxMin OCT problem. In parameterized complexity, the first FPT algorithm for the classical Odd Cycle Transversal (OCT) problem parameterized by the solution size, introduced the technique of Iterative Compression [29]. Using this, it was shown that OCT reduces to solving at most $3^k\cdot n$ instances of the polynomial-time $st$-Separator problem. Most algorithms for different variants of the OCT problem, like Independent OCT, use the same framework and reduce to essentially solving the variant of $st$-Separator, like Independent $st$-Separator [25].

For the MaxMin variant, unfortunately this is not the case. In fact our FPT algorithm for MaxMin OCT is independent of our FPT algorithm for MaxMin $st$-Sep. The reason is again that finding a minimal odd cycle transversal set (oct) that extends a given vertex is NP-hard (see Observation 3 and Lemma 4).

For the forward direction, let $Z$ be a minimal oct of $G$ of size at least $k$. Then $G-Z$ is bipartite. Additionally, for any $z\in Z$, the graph $G-(Z\setminus \{z\})$ contains an odd cycle through $z$, implying the existence of an induced odd cycle $C_z$ containing $z$. As the cycle is an induced odd cycle, we know that the vertex $v$ does not lie on this cycle. We will show that $Z$ is also a minimal oct in $G-v$. Clearly, $G-(Z\cup \{v\})$ is a bipartite graph. Therefore, $Z$ is an oct of $G-v$. For any vertex $z\in Z$, there is an induced odd cycle $C_z$ in $G-(Z\cup \{v\})$. Therefore, $Z$ is also a minimal odd cycle traversal of $G-v$.

For the other direction, let $Z$ be a minimal oct of $G-v$ with $|Z|\ge k$. Then, $G-(Z\cup \{v\})$ is bipartite. For each $z\in Z$, the graph $G-((Z\setminus \{z\})\cup \{v\})$ contains an induced odd cycle $C_z$. Since $v$ is not part of any induced odd cycle, $G-Z$ is bipartite, and $Z$ remains a minimal odd cycle transversal in $G$. $◀$

We know that given two vertices $a$ and $b$, determining if a graph contains an induced path of odd length between $a$ and $b$ is NP-complete [7]. Construct a graph $G^{\prime }$ by adding a new vertex $x$ to $G$ and making it adjacent to vertices $a$ and $b$. It is clear that there exists an induced odd cycle through $x$ in $G^{\prime }$ if and only if there is an induced path of odd length between $a$ and $b$ in $G$. This finishes the proof. $◀$

At the core of the Iterative Compression based approach for OCT, a subset of vertices $X$ is guessed to be in the solution, and after deleting $X$, the problem reduces to finding an $st$-separator, for some $s,t$. In particular, the final solution is this set $X$ union a minimum $st$-separator. For the MaxMin case, this amounts to finding a minimal $st$-separator that together with $X$ forms a minimal oct. Since the extension version of both the MaxMin $st$-Separator and MaxMin OCT are para-NP-hard, this leaves little hope to use the same approach for MaxMin versions.

Having eliminated this approach, we again go back to the approach via unbreakable graphs. This time again the core lies in designing an FPT algorithm when the graph is highly unbreakable and this algorithm require lot more insights than that of the MaxMin $st$-Sep. We give a technical overview of this stage in Section 1.1.

The instance $(G,k)$ is a yes instance of MaxMin $st$-Sep if there exists $Z\subseteq V(G)$ of size at least $k$ such that $G-Z$ has no $st$-path (equivalently $s$ and $t$ are in different connected components of $G-Z$), and for each $v\in Z$, $G-(Z\setminus \{v\})$ has an $st$-path (that is $s$ and $t$ are in the same connected component of $G-(Z\setminus \{v\})$).

Alternately, suppose $Z\subseteq V(G)$ (of arbitrarily large size) such that $G-Z$ has no $st$-path, and $Z$ contains $k$ distinct vertices $v_1,\mathrm{\dots },v_k$ such that for each $i\in [k]$, $G-(Z\setminus \{v_i\})$ contains an $st$-path. Then $Z$ may not be a minimal $st$-separator but it always contains a minimal $st$-separator of size at least $k$. In fact, $(G,k)$ is a yes instance if and only if such a set $Z$ exists. These properties of $Z$ can be incorporated as a CMSO formula $\psi$ as follows, where $\mathrm{𝐜𝐨𝐧𝐧}(U)$ is a CMSO sentence that checks whether a vertex set $U$ induces a connected graph. The CMSO description of CMSO can be, for example, found in [11].

It is clear that the size of the above formula $\psi$ depends linearly on $k$. $◀$

From Lemma 12 and Proposition 7, to prove Theorem 5, it is enough to prove Theorem 8.

See 8

We prove Theorem 8 in Section 3.1. As mentioned earlier, given a vertex set $V^{\prime }$, it may not always be possible to extend it to a minimal $st$-separator. Below, we give a definition for a certificate for the $st$-separator minimality of a set $V^{\prime }\subseteq V(G)$, which guarantees the existence of a minimal $st$-separator that contains (extends) the set $V^{\prime }$.

Let $S$ and $T$ serve as a certificate for the $st$-separator minimality of $V^{\prime }$. We will construct a set $V^{\prime }\subseteq Z\subseteq V(G)\setminus (S\cup T)$ which is a minimal $st$-separator in $G$. The set $Z$ is constructed iteratively. Initialize $Z:=\mathrm{\varnothing }$ and $G^{\prime }:=G[S\cup T]$. Fix an arbitrary ordering of the vertices in $V(G)\setminus (S\cup T)$.

For each vertex $v$ in the prescribed order: (i) if $G[S\cup T\cup \{v\}]$ is connected, then update $Z:=Z\cup \{v\}$, otherwise (ii) if $G[S\cup T\cup \{v\}]$ is not connected, then update $G^{\prime }:=G[V(G^{\prime })\cup \{v\}]$, update $S$ to be the vertices reachable from old $S$ in $G^{\prime }$, and update $T$ to be the vertices reachable from old $T$ in $G^{\prime }$.

The process continues until all vertices in $V(G)\setminus V(G^{\prime })$ have been processed. The final set $Z$ is then returned as a minimal $st$-separator of $G$. Note that if the initial sets $S$ and $T$ served as a certificate for the minimality of the $st$-separator $V^{\prime }$, then $V^{\prime }\subseteq Z$, as the subgraph $G[S\cup T\cup \{v\}]$ will always be connected for each $v\in V^{\prime }$ during every stage of the above process. $◀$

Let $(G,k)$ be an instance of Maximum Minimal OCT. Then $(G,k)$ is a yes instance if there exists $Z\subseteq V(G)$ of size at least $k$ such that $G-Z$ is bipartite and for each $v\in Z$, $G-(Z\setminus \{v\})$ is not bipartite.

Alternately, let $Z\subseteq V(G)$ such that $Z$ contains $k$ distinct vertices $v_1,\mathrm{\dots },v_k$, such that $G-Z$ is bipartite and for each $i\in [k]$, $G-(Z\setminus \{v\})$ is not bipartite. Observe that if such a set $Z$ exists, it may not be a minimal oct of $G$, but it definitely contains a minimal oct of size at least $k$. In fact, $(G,k)$ is a yes instance if and only if such a set $Z$ exists. We phrase this description of $Z$ as the CMSO formula $\psi$ as defined below.

where bipartite($W$) is a CMSO sentence given below, which checks whether the graph induced by the vertices in $W$ is bipartite.

It is clear that the size of the above formula $\phi$ depends linearly on $k$. $◀$

For the forward direction, let $Z$ be a minimal oct of $G$ of size at least $k$. Then $G-Z$ is bipartite. Additionally, for any $z\in Z$, the graph $G-(Z\setminus \{z\})$ contains an odd cycle through $z$, implying the existence of an induced odd cycle $C_z$ containing $z$. As the cycle is an induced odd cycle, we know that the vertex $v$ does not lie on this cycle. We will show that $Z$ is also a minimal oct in $G-v$. Clearly, $G-(Z\cup \{v\})$ is a bipartite graph. Therefore, $Z$ is an oct of $G-v$. For any vertex $z\in Z$, there is an induced odd cycle $C_z$ in $G-(Z\cup \{v\})$. Therefore, $Z$ is also a minimal odd cycle traversal of $G-v$.

For the other direction, let $Z$ be a minimal oct of $G-v$ with $|Z|\ge k$. Then, $G-(Z\cup \{v\})$ is bipartite. For each $z\in Z$, the graph $G-((Z\setminus \{z\})\cup \{v\})$ contains an induced odd cycle $C_z$. Since $v$ is not part of any induced odd cycle, $G-Z$ is bipartite, and $Z$ remains a minimal odd cycle transversal in $G$. $◀$

Because of Lemma 22 we can invoke Proposition 7. We invoke Proposition 7 with $c=2k$. Let $q$ be the $s$ from this proposition that corresponds to this choice of $c$. We conclude that to prove Theorem 6 it is enough to prove Theorem 9.

See 9

We prove Theorem 9 in Section 4.1. Next we define a certificate for minimality of oct for a vertex set $V^{\prime }$. The existence of such certificates guarantees the existence of a minimal oct which contains $V^{\prime }$.

Let $G^{\prime }$ be a certificate for minimality of $V^{\prime }$. First observe that $V^{\prime }\cap V(G^{\prime })=\mathrm{\varnothing }$ because $G^{\prime }$ is bipartite, but $G[V(G^{\prime })\cup \{v\}]$, for any $v\in V^{\prime }$, contains an odd cycle. We now construct a minimal oct of $G$, say $Z$, iteratively as follows. Initialize $Z=\mathrm{\varnothing }$. Fix an arbitrary ordering of the vertices in $V(G)\setminus V(G^{\prime })$ (note that $V^{\prime }\subseteq V(G)\setminus V(G^{\prime })$). Traverse the vertices of $V(G)\setminus V(G^{\prime })$ in this order. For any vertex $v\in V(G)\setminus V(G^{\prime })$ in the chosen order:

• $\mathrm{■}$

  if $G[V(G^{\prime })\cup \{v\}]$ is bipartite, update $G^{\prime }:=G[V(G^{\prime })\cup \{v\}]$, that is add $v$ to $G^{\prime }$, otherwise

• $\mathrm{■}$

  $G[V(G^{\prime })\cup \{v\}]$ contains an odd cycle, in which case add $v$ to the set $Z$.

When all the vertices in $V(G)\setminus V(G^{\prime })$ have been processed as stated above, then the set $Z$ is a minimal oct of $G$. Moreover, one can observe that if we start with $G^{\prime }$ which a certificate for minimality of $V^{\prime }$ then $V^{\prime }\subseteq Z$. $◀$