A procedure by induction to get maximum spanning bipartite graph (same vertex set as $G$ and the maximum possible number of edges) from given graph $G$:

Given a planar graph $G$, we need two disjoint sets $V_1$ and $V_2$. We define $V_2=V \setminus V_1$ where $V = V(G)$. In the following, $H$ is the bipartite subgraph with $V(H)=V_1 \sqcup V_2$ and $E(H) = K_{V_1,V_2} \cap E(G)$ where $K_{V_1,V_2}$ is the complete bipartite graph on $V_1$, $V_2$.

  1. Start with first $i$ vertices of $V$ in vertex set $V_{01} \subseteq V$ and then $V_{02} = V \setminus V_{01}$

  2. In iteration $i$, let our current chosen vertex set be $V_{i1}$

  3. If $\exists x \in V_{i1}$ such that $d_{H}(x) \lt \frac12 d_{G}(x)$, then consider the bipartite spanning graph $H'$ with $V(H') = V_{i1}' \sqcup V_{i2}'$ where $V_{i1}' = V_{i1} \setminus x$, $V_{i2}'= V_{i2} \sqcup x$, $E(H') = K_{V_{i1}',V_{i2}'} \cap E(G) $ This makes $\vert E(H') \geq E(H) \vert$. We are basically moving vertex $x$ which satisfies above property from $V_{i1}$ to $V_{i2}$.

  4. Similarly do for $ V_{i2}$. If $\exists x \in V_{i2}$ such that $d_{H}(x) < \frac{1}{2} d_{G}(x) $, move vertex $x$ to $V_{i1}$. Go to step 2.

  5. Repeat until $(\forall x \in V(H))\, d_{H}(x) \geq \frac{1}{2} d_{G}(x)$

  6. After this $V_1 = V_{i1}$ and $V_2 = V_{i2}$. We are using the property that a spanning bipartite subgraph $H$ from $G$ is maximal in terms of the total number of edges only when $H$ with $V(H) = V_{1} \sqcup V_{2}$ satisfies the property that $$(\forall x \in V(G))\, d_{H}(x) \geq \frac{1}{2} d_{G}(x)$$

Analysis of this procedure:

  1. Could somebody help me analyze this algorithm?

  2. Can I assume I know the degrees of the vertices in the bipartite graph $H$, in the intermediate steps?

    2.1. If I can assume so, then each induction iteration has $2n$ steps. And, in the worst case, could there be $n!$ permutations of induction iteration (Any permutation of $i$ vertices is possible for the first vertex set). Is the worst-case upperbound $O(n!\times n)$?


2 Answers 2

  1. We cannot analyze your algorithm since it is, as currently presented, not an algorithm to start with. In particular, you did not specify what is the starting value of $i$, in the very first iteration.

  2. Surely, when you have $V_{i1}$ and $V_{i2}=V\setminus V_{i1}$, it is easy to compute the degrees of the vertices in $H$.

    2.1. IMHO, even after you fix some starting value of $i$ for the first iteration, there cannot be any guarantee that your algorithm would stop. Since, swapping vertices between $V_{i1}$ and $V_{i2}$ does not necessarily decrease the number of "bad" vertices, i.e. those vertices $x$ for which $d_H(x)\le \frac12d_G(x)$.


In answer to your comment:

By maximum spanning bipartite graph I mean same vertex set as given graph and the maximum number of edges possible. Is the complexity $O(n^3)$ correct for this algorithm? If so it would solvable in P time.

No, that problem, also known as Bipartite Edge Deletion, or Edge Bipartization, is:

Given a graph $G = (V, E)$ and an integer $k$, is it possible to delete at most $k$ edges $E'$ such that $G' = (V, E \setminus E')$ is bipartite,

which is NP-complete.

It happens to be "equivalent" to the "vertex deletion" version of the problem, which is also known as Odd Cycle Transversal.


Your Answer

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

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