Given a graph $\Gamma=(V,E)$ with vertex set $V$ and edge set $E$ a $\textit{three partition}$ is decomposition of $V$ into a triple $(V_1, S, V_2)$ such that vertices of $V_1$ are only incident to vertices in $V_1$ and $S$ and similar for $V_2$. In other words, by removing the vertices in $S$ from $\Gamma$ one ends up with two disjoint graphs. Let $n=|V|$ and $\beta: \mathbb{N}\rightarrow \mathbb{R}_{>0}$. In its easiest form the $\textit{vertex separator problem (VSP)}$ is to find a triple $(V_1, S, V_2)$ with

  1. $(V_1,S,V_2)$ is a three partition of $\Gamma$.
  2. $|V_1|, |V_2|\leq \beta(n)$
  3. The three partition is minimal among all three partitions satisfying 2., i.e. $|S|\leq |R|$ for all three partitions $(W_1, R,W_2)$ with $|W_1|, |W_2|\leq \beta(n)$.

It is known that for general graphs and $\beta(n)$ the problem is NP-hard. However, in Polyhedral VSP it is stated that for $\beta(n)=n-k$ for some positive integer $k$ the problem is in fact solvable in polynomial time. They give a solution by mapping $\Gamma$ to a bipartite graph $B_\Gamma= ((V_B, V^\prime_B), E_B)$: For each vertex $v\in V$ one has vertices $v_1\in V_B$, $v_2\in V^\prime_B$ and an edge $(v_1,v_2)\in E_B$. For an edge $e=(v, w)\in E$ there are edges $(v_1,w_2)$, $(w_1,v_2)\in E_B$. Solving the VSP on $\Gamma$ with $\beta(n)=n-k$ is now equivalent to finding an independent set $I$ in $B_\Gamma$ s.th. $|V_B\cap I|, |V_B^\prime \cap I| \leq n-k$. The claim is that such an independent set can be found in $\mathcal{O}(n^3n^k)$ time, but it isn't said how an algorithm for this looks like.

Question 1: Is the claim obvious and if so how does an algorithm for this look like? I thought maybe this is related to Koenig's theorem: A maximal independent set is the complement of a minimal vertex cover (in the set of vertices). Then by Koenig's theorem finding a minimal vertex cover on a bipartite graph is equivalent to finding a maximum matching which can be done in polynomial time. However, due to the condition $|V_B\cap I|, |V_B^\prime \cap I|\leq n-k$ the independent set $I$ doesn't need to be maximal in the first place I think.

Question 2: Formulating the VSP in terms of an independent set of a bipartite graph can be done in general. What goes wrong for a polynomial time algorithm for general $\beta(n)$?


1 Answer 1


I understand that the question is about the time bound, not about the correctness of the reduction. The claim does not sound obvious (although a bound of $\mathcal{O}(n^3n^2k)$ can be shown with a much simpler argument than the one I sketch below). Since the vertices of the independent set will correspond to vertices of $V_1$ and $V_2$ and the goal is to minimize $|S|=|V|-|V_1|-|V_2|$, it makes sense to find a maximum independent set in $B_\Gamma$, subject to $1 \leq |V_B\cap I|,|V_B'\cap I| \leq n-k$.

First suppose there is a solution with $|S| \leq k-2$. Then we can find it by trying all $\mathcal{O}(n^{k-2})$ subsets of $V$ of cardinality at most $k-2$, checking in polynomial time for each of then if it induces the desired partition and return the solution, if it is found.

Otherwise, we can iterate through every $S' \subset V$ of cardinality $k-1$ (we are guessing $k-1$ vertices of $S$), and each pair $v_1,w_2$ with $v_1\in V_B$, $w_2 \in V_B'$ and $v,w \not\in S'$, and find a maximum independent set $I$ (if it exists) satisfying:

  • $v_1, w_2 \in I$;
  • $\forall u \in S'$, $I \cap\{u_1, u_2\} = \emptyset$.

For that, it is enough to find the maximum independent set of the graph $B'$ obtained from $B_{\Gamma}$ by deleting the vertices in $N(v_1)$, $N(w_2)$ and $\{u_1, u_2 | u \in S'\}$. Note that $1\leq |V_B\cap I|,|V_B'\cap I|$, since $v_1,w_2 \in I$, and $|V_B\cap I|,|V_B'\cap I| \leq n-k$ since in $B'$ each partition lost $k$ vertices.

Since we are solving $\mathcal{O}(n^{k+1})$ instances of independent set, each in polynomial time, a time bound of $\mathcal{O}(n^{k+c})$ with small $c$ follows. Simply using Hopcroft–Karp algorithm would give $c=3.5$, but by reusing computation from previous iterations, or by greedly initialyzing the algorithm with all edges of type $u_1u_2$ still in $B'$, it should not be hard to make $c$ smaller.

Concerning Question 2, note that the running time is exponential in $k$, hence the algorithm would not be polynomial in the general case, since it would take time $\mathcal{O}(n^3n^{n - \beta(n)})$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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