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$. enter image description here

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

Solution

tldr: your counterexample is correct.

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.

Comments (5)

  • +0 – Note: I did not read the paper you link to in order to check whether your definition of A-B separators matches the definition as stated in the paper. — May 24, 2022 at 04:15  
  • +0 – Note 2: If we just want no component to contain both a vertex from $A$ and a vertex from $B$ then some reduction of the type above works. Judging by your question you know that already. — May 24, 2022 at 04:17  
  • +0 – Thanks for the helpful reply. I think that my setting is somewhat different than the one in the paper you linked, and may allow to find an efficient alg after all: I wish to enumerate all minimal $st$-separators of $G$ that are also minimal $uv$-separators where $\{u,v\}\cap \{s,t\}=\emptyset$. By my understanding, this is distinct from the Telle and Villanger paper. Additionally, suppose it is given that there is a minimum $st$-separator that contains both $u$ and $v$. Would appreciate any leads to this problem. — May 31, 2022 at 16:34  
  • +0 – Are G,u,v,s,t given as input? — Jun 01, 2022 at 05:48  
  • +0 – Yes. You are given $G,s,u,v,t$. Furthermore, you can assume that there exists a minimum $st$-separator that contains both $u$ and $v$. Of course, you may also assume that $(u,v)\notin E(G)$. — Jun 01, 2022 at 06:46  

External Links

External links referenced by this document:

References