3
$\begingroup$

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

$\endgroup$

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – daniello
    May 24 at 4:15
  • $\begingroup$ 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. $\endgroup$
    – daniello
    May 24 at 4:17
  • $\begingroup$ 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. $\endgroup$
    – BBK
    May 31 at 16:34
  • $\begingroup$ Are G,u,v,s,t given as input? $\endgroup$
    – daniello
    Jun 1 at 5:48
  • $\begingroup$ 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)$. $\endgroup$
    – BBK
    Jun 1 at 6:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.