# Complexity and Algorithm for specific Vertex Separator Problem

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

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