All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs

Important separators have proved to be a very important tool in the design of many FPT algorithms, including fundamental problems such as Multiway Cut, Multicut, Directed Feedback Arc Set. We refer to Chapter 8 of [9] for various applications of important separators to design parameterized algorithms. Given two disjoint subsets of vertices $A,B$ and another set of vertices $X$ (which may intersect $A,B$) in a directed graph, we say that $X$ is an $A$-$B$ separator if there is no directed path from any vertex of $A$ to any vertex of $B$ in $G\setminus X$¹¹1$G\setminus X$ denotes the graph obtained from $G$ by deleting the vertex set $X$ along with its incident edges. For such a separator $X$, define $R(X)$ to be the set of vertices reachable from $A$ in $G\setminus X$. Then an $A$-$B$ separator $X$ is called an important $A$-$B$ separator if it is (a) inclusion-wise minimal - so that for any $v\in X$, $X\setminus \{v\}$ is not an $A$-$B$ separator and (b) for any other $A$-$B$ separator $Y\subseteq V(G)$ with $|Y|\le |X|$, we do not have $R(X)\subset R(Y)$.²²2Throughout the paper, we use the notation $P\subset Q$ to mean that $P$ is a proper subset of $Q$. Informally, important separators are those for which there is no other separator which is further away from $A$ without increasing the cut-size. Marx [28] first introduced the notion of important separators and showed a bound of $4^{k^2}$ on the number of important $A$-$B$ separators of size at most $k$. Later this bound was improved to $4^k$ (implicit in the FPT algorithm for Vertex Multiway Cut by Chen, Liu and Lu [6])³³3While these results focused mostly on the undirected version, the same proof works in directed graphs.. Over the last few years, this result has been used extensively to obtain FPT algorithms for various central parameterized problems [30, 7, 11, 25]. In this work, we show a new structural result on important separators in directed graphs: Given a directed graph $G$ and two disjoint subsets $S,T\subseteq V(G)$, we show that the number of $A$-$B$ important separators across all $A\subseteq S$ and $B\subseteq T$ is at most $\beta (|S|,|T|,k)=4^k\left(\genfrac{}{}{0pt}{}{|S|}{\le k}\right)\left(\genfrac{}{}{0pt}{}{|T|}{\le 2k}\right)$, where $\left(\genfrac{}{}{0pt}{}{n}{\le a}\right)={\sum }_{i=1}^a\left(\genfrac{}{}{0pt}{}{n}{i}\right)$. Note that the trivial bound is $4^k{2}^{|S|+|T|}$, which follows directly from the fact that there are at most $4^k$ important $A$-$B$ separators for any fixed $A\subseteq S,B\subseteq T$. Previously, no such result is known even for undirected graphs.

Throughout this paper, given a graph, we will denote by $n$ the number of vertices and by $m$ the number of edges/arcs.

It is not difficult to show that this result is essentially tight: we show this formally in the next lemma, whose proof is deferred to the appendix.

In the next few subsections, we show that this simple structural result has various interesting consequences, allowing us to obtain many new results which were previously only known for undirected graphs.

Kleinberg [18] introduced the concept of a detection set in a graph. The principal motivation for this concept was that of a network failure: given a network, can we compute a small set of representative nodes so that for any small set of failure nodes that cuts communication between two large subsets of nodes, there are two representatives that cannot communicate? Formally, Kleinberg defined an $(ϵ,k)$ detection set for an undirected graph $G$ as a set of terminals $T\subseteq V(G)$ which satisfies the following property. First, define a network failure as a set of vertices $X$ with $|X|\le k$ so that $G\setminus X$ can be partitioned into $A\cup B$ where $|A|,|B|\ge ϵn$ and there are no edges between $A$ and $B$. Then for every such (vertex) failure set $X$, the set $T$ must intersect with at least two components of $G\setminus X$. Kleinberg [18] showed that there is a detection set of size $𝒪(\frac{k^3}{ϵ}\log \frac{1}{ϵ})$. For the edge failure version, he showed a bound of $𝒪(\frac{k}{ϵ}\log \frac{1}{ϵ})$ which was subsequently improved to $𝒪(\frac{k}{\lambda }\frac{1}{ϵ}\log \frac{1}{ϵ})$ by Kleinberg et al. [19], where $\lambda$ is the size of the global minimum cut in the graph. Feige and Mahdian [15] showed an improved bound on (vertex) detection sets: they show a bound of $𝒪(\frac{k}{ϵ}\log \frac{1}{ϵ})$. Further, they showed a bound of $𝒪(\frac{k}{ϵ})$ for the edge failure version, removing the dependence on $\log \frac{1}{ϵ}$.

Feige and Mahdian [15] also studied a strengthening of this notion of detection sets called sample sets for undirected graphs: on a high level, these are a small set of terminals $T$ which represent all the small cuts of the graph in proportion to their size, up to some additive error. Concretely, given an undirected graph $G$ and a parameter $k$, they show that there exists a set of terminals $T$ with $|T|=𝒪(\frac{k}{{ϵ}^2}\log \frac{1}{ϵ})$, such that for any vertex set $X$ of size $|X|\le k$ and every connected component $C$ of $G\setminus X$, we have $\Vert C|-\frac{n}{|T|}|C\cap T\Vert \le ϵn$. Further, the set $T$ can be obtained by simple random sampling, and [15] shows that any random subset $T\subseteq V(G)$ of size $𝒪(\frac{k}{{ϵ}^2}\log \frac{1}{ϵ})$ is a sample set with constant probability.

The most important feature of these results is that the size of the detection set (or sample set) $T$ does not depend on $n$. It is then natural to ask if such results are possible for directed graphs. Given a digraph $G$, let us define a network failure as a set of vertices $X$ with $|X|\le k$, so that $G\setminus X$ can be partitioned into two parts $A$ and $B$, each of size at least $ϵn$, such that there is no arc from $B$ to $A$. The analogous question for detection sets is then: is there a set of terminals $T$ with $|T|=f(k,ϵ)$, such that for any network failure $X$ there exists a pair $t_1,t_2\in T$ so that there is no path from $t_1$ to $t_2$ in $G\setminus X$? Similarly, the analogous question for sample set becomes: is there a set of terminals $T$ with $|T|=g(k,ϵ)$ for some function $f$, so that for any set of vertices $X$ with $|X|\le k$, and any strongly connected component (SCC) $C$ of $G\setminus X$, we have $\Vert C|-\frac{n}{|T|}|C\cap T\Vert \le ϵn$? We answer both these questions in the affirmative, showing that one can in fact asymptotically match the same bound as in the undirected case, with $f(k,ϵ)=𝒪(\frac{k}{ϵ}\log \frac{1}{ϵ})$ and $g(k,ϵ)=𝒪(\frac{k}{{ϵ}^2}\log \frac{1}{ϵ})$.

While we believe that this is of independent interest, we also show a similar connection to parameterized and approximation algorithms for finding balanced cuts in directed graphs along the lines of the undirected case as in [15], as discussed in the following subsections. In fact, by using a slightly more nuanced analysis, our results generalize that of [15] even for undirected graphs.

Finally, we note that one can easily prove that there exists an absolute constant $c$ such that a random subset of size $c\frac{k\log n}{{ϵ}^2}$ is a sample set with constant probability in a directed graph. This follows from a simple application of Chernoff bounds and a union bound noting that the number of vertex sets of size at most $k$ is at most $\left(\genfrac{}{}{0pt}{}{n}{k}\right)$ ($\left(\genfrac{}{}{0pt}{}{m}{k}\right)$ in the case of edge sets). However, for most applications this bound is too weak. For instance, our parameterized algorithm for Directed Balanced Separator has an exponential dependency in the size of the sample set, and hence to show results parameterized by $k$, it is essential that the size of the sample set does not depend on $n$.

One of the most well-studied graph partitioning problems, both from the parameterized and approximation algorithms point of view, is the problem of Minimum Bisection. Given an undirected graph $G$ and a parameter $k$, the goal of the Minimum Bisection problem is to obtain a partition of the graph into two equal sized parts, such that the number of cut edges is at most $k$. Minimum Bisection was shown to be fixed-parameter tractable by Cygan et al. [11] and the current best parameterized algorithm is due to [10] who show an algorithm with running time $2^{𝒪(k\log k)}{n}^{𝒪(1)}$. Räcke [33] gave an $𝒪(\log n)$ approximation for (the optimization version of) Minimum Bisection. If only an approximate bisection where both sides have $\mathrm{\Omega }(n)$ vertices is desired, then this problem is essentially the Balanced Separator problem which is known to have an FPT algorithm running in time $2^{𝒪(k)}(m+n)$ due to Feige and Mahdian [15] and an $𝒪(\sqrt{\log n})$ approximation algorithm in polynomial time using the seminal result of Arora, Rao and Vazirani [3]. Feige et al. [14] showed that in fact this guarantee can be made $𝒪(\sqrt{\log k})$, and also showed that one can compute vertex separators with the same approximation ratio. In directed graphs, the Minimum Bisection problem has been typically studied as Directed Bisection: Given a directed graph $G$ with even number of vertices, is it possible to partition the vertex set into two equal parts $A$ and $B$ so that the number of arcs from $A$ to $B$ is at most $k$? This question was first raised by Feige and Yahalom [16]. When $k=0$, they referred to this problem as Oneway Cuts, and showed that even this problem is NP-hard. However, given a Oneway Cuts instance which admits a solution, if one relaxes the requirement so that the algorithm can output a partition $(A^{\prime },B^{\prime })$ of $V(G)$ such that there are no arcs directed from $A^{\prime }$ to $B^{\prime }$ and $||A^{\prime }|-|B^{\prime }||\le ϵn$ where $ϵ=\mathrm{\Omega }(\frac{1}{\log n})$, the problem now becomes tractable, and they show a polynomial time algorithm for Oneway Cuts. Madathil et al. [27] showed that the Directed Bisection problem is FPT with respect to $k$, even when one requires $|A|=|B|$ exactly, on a subclass of directed graphs called semi-complete digraphs, which are the class of directed graphs where for every pair of vertices $u$ and $v$, there is an arc from $u$ to $v$ or an arc from $v$ to $u$. In terms of approximation algorithms, Agarwal et al. [1] showed an $𝒪(\sqrt{\log n})$ approximation for Directed Balanced Separator , the directed analogue of Balanced Separator, while Even et al. [13] showed an $𝒪(\log k)$ approximation, which is the best known approximation guarantee depending only on $k$.

However, there is no prior work on the fixed-parameter tractability of Directed Balanced Separator or Directed Bisection for general $k$ on general directed graphs, even when we relax the requirement of finding a bisection to that of finding an approximate bisection, that is, find a partition $(A^{\prime },B^{\prime })$ with $|A^{\prime }|,|B^{\prime }|=\mathrm{\Omega }(n)$ so that the number of arcs from $A^{\prime }$ to $B^{\prime }$ is at most $k$.

Our result makes the first progress on this problem. Before we state our results, we define the Directed Balanced Separator problem formally. Since all our results work for both the vertex and edge versions, we state them together as one problem. We adapt our definition from the definition of Balanced Separator in [15], whose results we generalize. For completeness, we recall the definition of Balanced Separator in [15].

Balanced Separator Parameter: $k,b$ Input: Undirected graph $G=(V,E)$ Question: Is there a set of vertices (edges) $F$ with $|F|\le k$, so that in $G\setminus F$, every connected component has size at most $bn$?

Directed Balanced Separator Parameter: $k,b$ Input: Directed graph $G=(V,E)$ Question: Is there a set of vertices (arcs) $F$ with $|F|\le k$, so that in $G\setminus F$, every strongly connected component has size at most $bn$?

For the sake of clarity and comparison, we state the main result of [15]. Given an undirected graph $G$, we say that a set of vertices/edges $F$ is a $b$-balanced separator if every connected component of $G\setminus F$ has size at most $bn$.

The following theorem, which directly generalizes the result of Theorem 5 is our main result. Given a directed graph $G$, we say that a set of vertices/arcs $F$ is a $b$-balanced separator if every strongly connected component (SCC) of $G\setminus F$ has size at most $bn$.

We observe that our algorithm has a running time of $2^{𝒪\left(k\log \left(\frac{1}{ϵ}\right)/{ϵ}^2\right)}(m+n)$ for any $b=\mathrm{\Omega }(1)$, matching the run-time of Theorem 5 for $\frac{2}{3}\le b\le 1$ while also extending to any parameter $b\in (0,1)$. We also observe that Theorem 6 implies Theorem 5, since given any undirected graph $G$, one can create a directed graph $H$ on the same vertex set, so that for every edge $\{u,v\}\in E(G)$, we have the two arcs $(u,v),(v,u)\in E(H)$ and we can apply Theorem 6 to obtain Theorem 5.

Our algorithm for Directed Balanced Separator can be used to solve (approximate) Directed Bisection as well. To see this, given a graph $G$, observe that in any bisection $(A,B)$ so that the number of arcs going from $A$ to $B$ is at most $k$, the set $F$ of these at most $k$ arcs form a $\frac{1}{2}$-balanced separator, so that in $G\setminus F$, every strongly connected component is of size at most $\frac{n}{2}$. Using Theorem 6 with $b=\frac{1}{2}$, we can find a set of arcs $F^{\prime }$ with $|F^{\prime }|\le k$ that forms a $(\frac{1}{2}+ϵ)$ balanced separator. Finally, note that the strongly connected components of the graph $G\setminus F^{\prime }$ form a Directed Acyclic Graph (DAG), and each strongly connected component of $G\setminus F^{\prime }$ has size at most $(\frac{1}{2}+ϵ)n$. It follows that there is a topological ordering $\{C_1,C_2\mathrm{\dots }{C}_{\mathrm{\ell }}\}$ of these strongly connected components of $G\setminus F^{\prime }$, such that there is no arc from $C_j$ to $C_i$ for $i,j\in [\mathrm{\ell }]$ with $j>i$. Therefore we can pick some prefix of strongly connected components in the topological ordering of $G\setminus F^{\prime }$ to obtain a set $A^{\prime }$, so that both $|A^{\prime }|,|V(G)\setminus A^{\prime }|\ge (1-2ϵ)\frac{n}{4}$, and in $G\setminus F^{\prime }$, there are no arcs from $V(G)\setminus A^{\prime }$ to $A^{\prime }$. It follows that the set of arcs $F^{\prime }$ forms an (approximate) directed bisection. Note that the approximation is only in the balance, not in the number of arcs cut.

Next, we show a $𝒪(\sqrt{\log k})$ approximation for Directed Balanced Separator. This improves both the $𝒪(\sqrt{\log n})$ approximation of [1] and the $𝒪(\log k)$ approximation given by Even et al. [13] for approximating Directed Balanced Separator in polynomial time.

Note that for this theorem, we do not optimize $b^{\prime }$, unlike our FPT result where we were able to show that $b^{\prime }\le b+ϵ$ for some suitably chosen $ϵ$. Still, we remark that is not a limitation of our framework, but inherent in [1] due to the use of the ARV separation theorem [3].

Vertex sparsification is a fundamental problem in various settings. Broadly, given a graph and a terminal set $T$, a vertex sparsifier is a smaller graph (with size typically depending only on $|T|$) that preserves some (cut based) property of the terminals $T$. Moitra [32] first introduced a version of vertex sparsification in undirected graphs. Chuzhoy [8] generalized this notion by allowing Steiner nodes in the sparsifier. Both these notions preserve edge cuts between bi-partitions of the terminal set.

For our setting, we focus on directed graphs and vertex cuts. Given a directed graph $G$ and a set of terminals $T$ along with an integer $c$, a $(c,T)$ vertex cut sparsifier for $G$ is another graph $G^{\prime }$ with $T\subseteq V(G^{\prime })$, so that for every partition $\{A,B\}$ of $T$ (so that $A\cup B=T$ and $A\cap B=\mathrm{\varnothing }$), if the size of an $A$-$B$ vertex min-cut is at most $c$ in $G$, then the size of an $A$-$B$ vertex min-cut is the same in both in $G$ and $G^{\prime }$. In other words, the goal is to find a vertex sparsifier that preserves vertex min-cuts of size at most $c$ between sets of terminals. Here we allow the deletion of terminals as well.

Kratsch and Wahlström [20, 21] first studied this notion of vertex sparsification for vertex cuts (without the parameter $c$) and showed that given $G,T$, there is a randomized polynomial time algorithm that obtains a $(|T|,T)$ vertex sparsifier $G^{\prime }$ for $G$ with $|V(G^{\prime })|\le 𝒪({|T|}^3)$. This bound was improved to $𝒪({|T|}^2)$ by [17] for the special case of directed acyclic graphs. Their algorithm runs in linear time for fixed $|T|$, but is still randomized as it needs to compute a representation of gammoids.

One can then ask the question as to what is known about deterministic algorithms. Recently, Misra et al. [31] showed that a representation of a gammoid with rank $r$ over a ground set of $m$ elements can be constructed in time $𝒪(\left(\genfrac{}{}{0pt}{}{m}{r}\right)m^{𝒪(1)})$ deterministic time. The technique of [20] needs to compute a representation of a gammoid whose ground set has size $n$, the number of vertices and rank $|T|$, the number of terminals. We therefore obtain the following result.

However, this algorithm (which is an XP algorithm in the notation of parameterized complexity) can be easily improved to a (still deterministic) FPT algorithm. The reason for this is simple: there are at most $2^{|T|}$ partitions of the terminal set $T$. For each partition $A\cup B$, we can compute an $(A,B)$ directed min-vertex cut $M$. Note that this min-cut is of size at most $|T|$, since one can simply delete all the terminals to obtain a cut. This gives a set $X$ of $2^{|T|}\cdot |T|$ vertices. It can now be shown that we can apply the closure operation to the set $V(G)\setminus X$, where we simply delete all vertices of $V(G)\setminus X$, and for each vertex pair $(u,w)$ such that there are vertices $(v_1,v_2)$ with $v_1,v_2\in V(G)\setminus X$ with $(u,v_1),(v_2,w)\in E(G)$ we add an arc $(u,w)$. This results in a sparsifier of size $𝒪(|T|2^{|T|})$. One can now set $n=𝒪(|T|2^{|T|})$ in Theorem 8 to obtain a sparsifer of size $2^{𝒪({|T|}^2)}$ in time $2^{𝒪({|T|}^2)}$. The total running time is $2^{𝒪(T)}(m+n)+2^{𝒪({|T|}^2)}$.

A similar line of research considers edge and vertex cuts in undirected graphs. For edge cuts in undirected graphs, Chalermsook et al. [4] showed an upper bound of $𝒪(|T|c^4)$ which was later improved to $𝒪(|T|c^3)$ by Liu [23]. Both these algorithms are randomized. Saranurak and Yingchareonthawornchai [34] considered the vertex version in undirected graphs, and gave a deterministic algorithm to compute a sparsifier of size $𝒪(|T|2^{𝒪(c^2)})$ in time $𝒪(m^{1+o(1)}{2}^{𝒪(c^2)})$.

However, no improvement on the FPT algorithm with running time $2^{O(|T|)}(m+n)+2^{O({|T|}^2)}$ based on Theorem 8 is known for deterministic algorithms for vertex cut sparsifiers in directed graphs. We show the following result, which shows that if one is interested in preserving cuts of size at most $c$, then a better deterministic algorithm is possible.

While the dependence on $c$ in the exponent for the size of the sparsifier seems undesirable, Theorem 9 shows that the vertex sparsifier $G^{\prime }$ constructed by our algorithm is more powerful: it in-fact “preserves” all $A$-$B$ important separators for any partition $(A,B)$ of $T$. Additionally, if one wants only a vertex sparsifier, we note that simply running the algorithm in Theorem 8 after applying our result in Theorem 9 gives a vertex sparsifier of size $𝒪({|T|}^3)$, but now the running time is ${\left(\frac{|T|}{c}\right)}^{𝒪(c|T|)}$. Thus, together, we obtain a vertex cut sparsifier of size $𝒪({|T|}^3)$ in time $\left(\genfrac{}{}{0pt}{}{|T|}{\le 3c}\right)2^{𝒪(c)}(m+n)+{\left(\frac{|T|}{c}\right)}^{𝒪(c|T|)}$.

In this section we give a high-level overview of our techniques. For the sake of simplicity and clarity we sometimes omit small details in this section.