Complexity and Algorithm for specific Vertex Separator Problem

Question

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)$?

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)})$.