Theoretical Computer Science
graph-algorithms enumeration
Updated Thu, 16 Jun 2022 04:17:52 GMT

# Question about algorithm for enumerating minimal AB-separators

Let $$A,B\subseteq V(G)$$ be two non-adjacent, disjoint subsets of vertices in $$G$$. A subset $$S\subseteq V(G)\setminus (A\cup B)$$ is an $$AB$$-separator if the graph $$G[V\setminus S]$$ contains two distinct connected components $$C_A$$ and $$C_B$$ where $$A\subseteq C_A$$ and $$B \subseteq C_B$$; $$S$$ is a minimal $$AB$$-separator if no proper subset of $$S$$ has this property.

In 1 (Corollary 1), the authors reduce the task of enumerating all minimal $$AB$$-separators of a graph to that of enumerating all minimal $$ab$$-separators as follows.

1. Consider the graph $$G[V(G)\setminus N_G(A)]$$ induced by $$V(G)\setminus N_G(A)$$. If no connected component of $$G[V(G)\setminus N_G(A)]$$ contains $$B$$, then terminate (i.e., $$G$$ does not contain any $$AB$$-separator).
2. Otherwise, merge all vertices in $$A$$ to a vertex $$a$$ (i.e., $$N_G(a)=N_G(A)$$), and all vertices of $$B$$ to vertex $$b$$.
3. Enumerate all minimal $$ab$$-separators.

While it is clear that every minimal $$AB$$-separator is also a minimal $$ab$$-separator, why is it the case that every minimal $$ab$$-separator is also a minimal $$AB$$-separator ? Can't a minimal $$ab$$-separator separate $$A$$ (or $$B$$) into more than one connected component ?

For example, let $$A=\{x,y\}$$ and $$B=\{e,f\}$$ in the graph on the left. The graph $$G[V\setminus N_G(A)]$$ contains the connected component $$\{e,f,h\}\supseteq B$$. However, while $$\{c,d\}$$ is a minimal $$xy,ef$$-separator in the graph on the right, it is not an $$AB$$-separator because it separates $$x$$ and $$y$$.

1 "Efficient enumeration of all minimal separators of a graph" by Hong Shen and Weifa Liang, in Theoretical Computer Science, 1997

## Solution

Longer Answer: The way $$A$$-$$B$$-separators are defined above the problem to determine whether at least one $$A$$-$$B$$-separator exists is NP-complete.

In particular the following problem, called 2-Disjoint Connected Subgraphs, is NP-complete (see Connecting Terminals and 2-Disjoint Connected Subgraphs by Telle and Villanger and references within).

Input is a graph $$G$$ and two disjoint vertex sets $$A$$, $$B$$, and the task is to determine whether there exist two disjoint vertex sets $$P$$ and $$Q$$ such that $$G[P]$$ and $$G[Q]$$ are both connected, and $$A \subseteq P$$ and $$B \subseteq Q$$.

2-Disjoint Connected Subgraphs can be reduced to the problem of determining whether there exists an $$A$$-$$B$$ separator as follows. Given $$G$$, $$A$$, $$B$$, subdivide every edge of $$G$$. Here subdividing an edge $$uv$$ means removing the edge $$uv$$ from the graph, adding a new vertex $$w$$ and adding the edges $$uw$$ and $$wv$$ to $$G$$. Call the resulting graph $$G'$$.

If the 2-Disjoint Connected Subgraphs instance $$G$$, $$A$$, $$B$$ had a solution $$P$$, $$Q$$ then let $$P'$$ be $$P$$ plus the set of all vertices in $$G'$$ corresponding to edges in $$G[P]$$. Define $$Q'$$ from $$Q$$ similarly. Now $$P'$$ and $$Q'$$ are connected sets containing $$A$$ and $$B$$ respectively, and deleting all vertices of $$G'$$ that correspond to edges of $$G$$ with precisely one edge in $$P$$ will separate $$P'$$ from $$Q'$$. So some subset of this set is a minimal $$P'$$-$$Q'$$ separator in $$G'$$.

On the other hand let $$S$$ be a $$A$$-$$B$$-minimal separator in $$G'$$ and select $$P'$$ and $$Q'$$ to be the components of $$G'-S$$ that contain $$A$$ and $$B$$ respectively. Let $$P$$ and $$Q$$ be the vertices in $$P'$$ and $$Q'$$ respectively, that correspond to vertices of $$G$$ (so drop vertices corresponding to edges). $$P$$ and $$Q$$ are disjoint connected sets containing $$A$$ and $$B$$ respectively.