<p>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 <span class="math-container">$\mathcal{O}(n^3n^2k)$</span> 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 <span class="math-container">$V_1$</span> and <span class="math-container">$V_2$</span> and the goal is to minimize <span class="math-container">$|S|=|V|-|V_1|-|V_2|$</span>, it makes sense to find a maximum independent set in <span class="math-container">$B_\Gamma$</span>, subject to <span class="math-container">$1 \leq |V_B\cap I|,|V_B'\cap I| \leq n-k$</span>.</p>
<p>First suppose there is a solution with <span class="math-container">$|S| \leq k-2$</span>. Then we can find it by trying  all <span class="math-container">$\mathcal{O}(n^{k-2})$</span> subsets of <span class="math-container">$V$</span> of cardinality at most <span class="math-container">$k-2$</span>, checking in polynomial time for each of then if it induces the desired partition and return the solution, if it is found.</p>
<p>Otherwise, we can iterate through every <span class="math-container">$S' \subset V$</span> of cardinality <span class="math-container">$k-1$</span> (we are guessing <span class="math-container">$k-1$</span> vertices of <span class="math-container">$S$</span>), and each pair <span class="math-container">$v_1,w_2$</span> with <span class="math-container">$v_1\in V_B$</span>, <span class="math-container">$w_2 \in V_B'$</span> and <span class="math-container">$v,w \not\in S'$</span>, and find a maximum independent set <span class="math-container">$I$</span> (if it exists) satisfying:</p>
<ul>
<li><span class="math-container">$v_1, w_2 \in I$</span>;</li>
<li><span class="math-container">$\forall u \in S'$</span>, <span class="math-container">$I \cap\{u_1, u_2\} = \emptyset$</span>.</li>
</ul>
<p>For that, it is enough to find the maximum independent set of the graph <span class="math-container">$B'$</span> obtained from <span class="math-container">$B_{\Gamma}$</span> by deleting the vertices in <span class="math-container">$N(v_1)$</span>, <span class="math-container">$N(w_2)$</span> and <span class="math-container">$\{u_1, u_2 | u \in S'\}$</span>. Note that <span class="math-container">$1\leq |V_B\cap I|,|V_B'\cap I|$</span>, since <span class="math-container">$v_1,w_2 \in I$</span>, and <span class="math-container">$|V_B\cap I|,|V_B'\cap I| \leq n-k$</span> since in <span class="math-container">$B'$</span> each partition lost <span class="math-container">$k$</span> vertices.</p>
<p>Since we are solving <span class="math-container">$\mathcal{O}(n^{k+1})$</span> instances of independent set, each in polynomial time, a time bound of <span class="math-container">$\mathcal{O}(n^{k+c})$</span> with small <span class="math-container">$c$</span> follows. Simply using Hopcroft–Karp algorithm would give <span class="math-container">$c=3.5$</span>, but by reusing computation from previous iterations, or by greedly initialyzing the algorithm with all edges of type <span class="math-container">$u_1u_2$</span> still in <span class="math-container">$B'$</span>, it should not be hard to make <span class="math-container">$c$</span> smaller.</p>
<p>Concerning Question 2, note that the running time is exponential in <span class="math-container">$k$</span>, hence the algorithm would not be polynomial in the general case, since it would take time <span class="math-container">$\mathcal{O}(n^3n^{n - \beta(n)})$</span>.</p>

CC BY-SA 4.0
2023-08-14T20:20:29.177Z
2023-08-14T20:20:29.177Z
Vinicius dos Santos
<p>Given a graph <span class="math-container">$\Gamma=(V,E)$</span> with vertex set <span class="math-container">$V$</span> and edge set <span class="math-container">$E$</span> a <span class="math-container">$\textit{three partition}$</span> is decomposition of <span class="math-container">$V$</span> into a triple <span class="math-container">$(V_1, S, V_2)$</span> such that vertices of <span class="math-container">$V_1$</span> are only incident to vertices in <span class="math-container">$V_1$</span> and <span class="math-container">$S$</span> and similar for <span class="math-container">$V_2$</span>. In other words, by removing the vertices in <span class="math-container">$S$</span> from <span class="math-container">$\Gamma$</span> one ends up with two disjoint graphs. Let <span class="math-container">$n=|V|$</span> and <span class="math-container">$\beta: \mathbb{N}\rightarrow \mathbb{R}_{&gt;0}$</span>. In its easiest form the <span class="math-container">$\textit{vertex separator problem (VSP)}$</span> is to find a triple <span class="math-container">$(V_1, S, V_2)$</span> with</p>
<ol>
<li><span class="math-container">$(V_1,S,V_2)$</span> is a three partition of <span class="math-container">$\Gamma$</span>.</li>
<li><span class="math-container">$|V_1|, |V_2|\leq \beta(n)$</span></li>
<li>The three partition is minimal among all three partitions satisfying 2., i.e. <span class="math-container">$|S|\leq |R|$</span> for all three partitions <span class="math-container">$(W_1, R,W_2)$</span> with <span class="math-container">$|W_1|, |W_2|\leq \beta(n)$</span>.</li>
</ol>
<p>It is known that for general graphs and <span class="math-container">$\beta(n)$</span> the problem is NP-hard. However, in <a href="https://link.springer.com/article/10.1007/s10107-005-0574-7" rel="nofollow noreferrer">Polyhedral VSP</a> it is stated that for <span class="math-container">$\beta(n)=n-k$</span> for some positive integer <span class="math-container">$k$</span> the problem is in fact solvable in polynomial time. They give a solution by mapping <span class="math-container">$\Gamma$</span> to a bipartite graph <span class="math-container">$B_\Gamma= ((V_B, V^\prime_B), E_B)$</span>: For each vertex <span class="math-container">$v\in V$</span> one has vertices <span class="math-container">$v_1\in V_B$</span>, <span class="math-container">$v_2\in V^\prime_B$</span> and an edge <span class="math-container">$(v_1,v_2)\in E_B$</span>. For an edge <span class="math-container">$e=(v, w)\in E$</span> there are edges <span class="math-container">$(v_1,w_2)$</span>, <span class="math-container">$(w_1,v_2)\in E_B$</span>. Solving the VSP on <span class="math-container">$\Gamma$</span> with <span class="math-container">$\beta(n)=n-k$</span> is now equivalent to finding an independent set <span class="math-container">$I$</span> in <span class="math-container">$B_\Gamma$</span> s.th. <span class="math-container">$|V_B\cap I|, |V_B^\prime \cap I| \leq n-k$</span>. The claim is that such an independent set can be found in <span class="math-container">$\mathcal{O}(n^3n^k)$</span> time, but it isn't said how an algorithm for this looks like.</p>
<p><strong>Question 1:</strong> 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 <span class="math-container">$|V_B\cap I|, |V_B^\prime \cap I|\leq n-k$</span> the independent set <span class="math-container">$I$</span> doesn't need to be maximal in the first place I think.</p>
<p><strong>Question 2:</strong> 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 <span class="math-container">$\beta(n)$</span>?</p>

<graph-algorithms><partition-problem><bipartite-graphs>
Complexity and Algorithm for specific Vertex Separator Problem
user69635
# Complexity and Algorithm for specific Vertex Separator Problem

(Asked by: username_0 on 2023-07-11)

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](https://link.springer.com/article/10.1007/s10107-005-0574-7) 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)$?

**Tags:** graph-algorithms, partition-problem, bipartite-graphs


---

## 1 answers

### Answer by username_1 on 2023-08-14. Score: 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)})$.


---

