<p><strong>tldr:</strong> your counterexample is correct.</p>
<p><strong>Longer Answer:</strong>
The way <span class="math-container">$A$</span>-<span class="math-container">$B$</span>-separators are defined above the problem to determine whether at least one <span class="math-container">$A$</span>-<span class="math-container">$B$</span>-separator exists is NP-complete.</p>
<p>In particular the following problem, called 2-Disjoint Connected Subgraphs, is NP-complete (see <a href="https://arxiv.org/abs/1301.2506" rel="noreferrer">Connecting Terminals and 2-Disjoint Connected Subgraphs
</a> by Telle and Villanger and references within).</p>
<p>Input is a graph <span class="math-container">$G$</span> and two disjoint vertex sets <span class="math-container">$A$</span>, <span class="math-container">$B$</span>, and the task is to determine whether there exist two disjoint vertex sets <span class="math-container">$P$</span> and <span class="math-container">$Q$</span> such that <span class="math-container">$G[P]$</span> and <span class="math-container">$G[Q]$</span> are both connected, and <span class="math-container">$A \subseteq P$</span> and <span class="math-container">$B \subseteq Q$</span>.</p>
<p>2-Disjoint Connected Subgraphs can be reduced to the problem of determining whether there exists an <span class="math-container">$A$</span>-<span class="math-container">$B$</span> separator as follows. Given <span class="math-container">$G$</span>, <span class="math-container">$A$</span>, <span class="math-container">$B$</span>, <em>subdivide</em> every edge of <span class="math-container">$G$</span>. Here subdividing an edge <span class="math-container">$uv$</span> means removing the edge <span class="math-container">$uv$</span> from the graph, adding a new vertex <span class="math-container">$w$</span> and adding the edges <span class="math-container">$uw$</span> and <span class="math-container">$wv$</span> to <span class="math-container">$G$</span>. Call the resulting graph <span class="math-container">$G'$</span>.</p>
<p>If the 2-Disjoint Connected Subgraphs instance <span class="math-container">$G$</span>, <span class="math-container">$A$</span>, <span class="math-container">$B$</span> had a solution <span class="math-container">$P$</span>, <span class="math-container">$Q$</span> then let <span class="math-container">$P'$</span> be <span class="math-container">$P$</span> plus the set of all vertices in <span class="math-container">$G'$</span> corresponding to edges in <span class="math-container">$G[P]$</span>. Define <span class="math-container">$Q'$</span> from <span class="math-container">$Q$</span> similarly. Now <span class="math-container">$P'$</span> and <span class="math-container">$Q'$</span> are connected sets containing <span class="math-container">$A$</span> and <span class="math-container">$B$</span> respectively, and deleting all vertices of <span class="math-container">$G'$</span> that correspond to edges of <span class="math-container">$G$</span> with precisely one edge in <span class="math-container">$P$</span> will separate <span class="math-container">$P'$</span> from <span class="math-container">$Q'$</span>. So some subset of this set is a minimal <span class="math-container">$P'$</span>-<span class="math-container">$Q'$</span> separator in <span class="math-container">$G'$</span>.</p>
<p>On the other hand let <span class="math-container">$S$</span> be a <span class="math-container">$A$</span>-<span class="math-container">$B$</span>-minimal separator in <span class="math-container">$G'$</span> and select <span class="math-container">$P'$</span> and <span class="math-container">$Q'$</span> to be the components of <span class="math-container">$G'-S$</span> that contain <span class="math-container">$A$</span> and <span class="math-container">$B$</span> respectively. Let <span class="math-container">$P$</span> and <span class="math-container">$Q$</span> be the vertices in <span class="math-container">$P'$</span> and <span class="math-container">$Q'$</span> respectively, that correspond to vertices of <span class="math-container">$G$</span> (so drop vertices corresponding to edges). <span class="math-container">$P$</span> and <span class="math-container">$Q$</span> are disjoint connected sets containing <span class="math-container">$A$</span> and <span class="math-container">$B$</span> respectively.</p>

CC BY-SA 4.0
2022-05-24T04:15:10.607Z
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.
daniello
CC BY-SA 4.0
2022-05-24T04:17:27.627Z
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.
daniello
CC BY-SA 4.0
2022-05-31T16:34:29.513Z
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.
BBK
CC BY-SA 4.0
2022-06-01T05:48:20.590Z
Are G,u,v,s,t given as input?
daniello
CC BY-SA 4.0
2022-06-01T06:46:55.300Z
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)$.
BBK
CC BY-SA 4.0
2022-05-24T04:14:16.643Z
2022-05-24T04:14:16.643Z
daniello
<p>Let <span class="math-container">$A,B\subseteq V(G)$</span> be two non-adjacent, disjoint subsets of vertices in <span class="math-container">$G$</span>.
A subset <span class="math-container">$S\subseteq V(G)\setminus (A\cup B)$</span> is an <span class="math-container">$AB$</span>-separator if the graph <span class="math-container">$G[V\setminus S]$</span> contains two distinct connected components <span class="math-container">$C_A$</span> and <span class="math-container">$C_B$</span> where <span class="math-container">$A\subseteq C_A$</span> and <span class="math-container">$B \subseteq C_B$</span>; <span class="math-container">$S$</span> is a minimal <span class="math-container">$AB$</span>-separator if no proper subset of <span class="math-container">$S$</span> has this property.</p>
<p>In <a href="https://i.sstatic.net/4tcJZ.png" rel="nofollow noreferrer">1</a> (Corollary 1), the authors reduce the task of enumerating all minimal <span class="math-container">$AB$</span>-separators of a graph to that of enumerating all minimal <span class="math-container">$ab$</span>-separators as follows.</p>
<ol>
<li>Consider the graph <span class="math-container">$G[V(G)\setminus N_G(A)]$</span> induced by <span class="math-container">$V(G)\setminus N_G(A)$</span>. If no connected component of <span class="math-container">$G[V(G)\setminus N_G(A)]$</span> contains <span class="math-container">$B$</span>, then terminate (i.e., <span class="math-container">$G$</span> does not contain any <span class="math-container">$AB$</span>-separator).</li>
<li>Otherwise, merge all vertices in <span class="math-container">$A$</span> to a vertex <span class="math-container">$a$</span> (i.e., <span class="math-container">$N_G(a)=N_G(A)$</span>), and all vertices of <span class="math-container">$B$</span> to vertex <span class="math-container">$b$</span>.</li>
<li>Enumerate all minimal <span class="math-container">$ab$</span>-separators.</li>
</ol>
<p>While it is clear that every minimal <span class="math-container">$AB$</span>-separator is also a minimal <span class="math-container">$ab$</span>-separator, why is it the case that every minimal <span class="math-container">$ab$</span>-separator is also a minimal <span class="math-container">$AB$</span>-separator ? Can't a minimal <span class="math-container">$ab$</span>-separator separate <span class="math-container">$A$</span> (or <span class="math-container">$B$</span>) into more than one connected component ?</p>
<p>For example, let <span class="math-container">$A=\{x,y\}$</span> and <span class="math-container">$B=\{e,f\}$</span> in the graph on the left. The graph <span class="math-container">$G[V\setminus N_G(A)]$</span> contains the connected component <span class="math-container">$\{e,f,h\}\supseteq B$</span>. However, while <span class="math-container">$\{c,d\}$</span> is a minimal <span class="math-container">$xy,ef$</span>-separator in the graph on the right, it is not an <span class="math-container">$AB$</span>-separator because it separates <span class="math-container">$x$</span> and <span class="math-container">$y$</span>.
<a href="https://i.sstatic.net/4tcJZ.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/4tcJZ.png" alt="enter image description here" /></a></p>
<p><a href="https://i.sstatic.net/4tcJZ.png" rel="nofollow noreferrer">1</a> &quot;Efficient enumeration of all minimal separators of a graph&quot; by Hong Shen and Weifa Liang, in Theoretical Computer Science, 1997</p>

<graph-algorithms><enumeration>
Question about algorithm for enumerating minimal AB-separators
BBK
# Question about algorithm for enumerating minimal AB-separators

(Asked by: username_0 on 2022-05-23)

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](https://i.sstatic.net/4tcJZ.png) (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](https://i.sstatic.net/4tcJZ.png)](https://i.sstatic.net/4tcJZ.png)

[1](https://i.sstatic.net/4tcJZ.png) "Efficient enumeration of all minimal separators of a graph" by Hong Shen and Weifa Liang, in Theoretical Computer Science, 1997

**Tags:** graph-algorithms, enumeration

---

## 1 answers

### Answer by username_1 on 2022-05-24. Score: 5 | Accepted answer

**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](https://arxiv.org/abs/1301.2506) 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:**
> **username_1**: 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.  
> **username_1**: 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.  
> **username_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.  
> **username_1**: Are G,u,v,s,t given as input?  
> **username_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)$.  

---

