# Complexity of determining spanning bipartite graph

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

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

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.
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,