Removing cycles from an undirected connected bipartite graph in a special manner

Question

Consider an undirected connected bipartite graph (with cycles) $G = (V_1,V_2,E)$, where $V_1,V_2$ are the two node sets and $E$ is the set of edges connecting nodes in $V_1$ to those in $V_2$. We assume that $|V_1|=v_1$, $|V_2|=v_2$ and $|E|=e$.

Then $(e-v_1-v_2+1)$ edges need to be removed to make $G$ a spanning tree, we refer to this set of removed edges as $C$. We define $x_i$ as the decrease in the degree of $i$th node in $V_1$ due to choice of $C$ and subsequent removal of edges (i.e., $x_1+x_2+\cdots+x_{v_1}=e-v_1-v_2+1$).

We may have multiple choices for $C$ (the number of choices equals the number of spanning trees). I am interested in finding a choice of $C$ that minimizes $\max x_i$. In particular, I want to know if the problem is NP-hard or if there is a polynomial-time (in $v_1,v_2,e$) algorithm that can generate the desired choice of $C$.

Answer 1

[edited]

It seems this question is NP-Complete.

The general idea: In a graph which is a 3-regular graph minus an edge, a spanning tree that minimizes $\max x_i$ is (more or less) an Hamiltonian Path. Some more work is needed in order to make it an Hamiltonian Cycle; finding an Hamiltonian Cycle in a 3-regular bipartite graph is NP-complete.

Assume there is an algorithm for finding such a set $C$ for any bipartite graph. Consider only the subclass of graphs with $v_1 = v_2$, that are also 3-regular.

• The reduction:

Consider a 3-regular bipartite graph $G$. Add two vertices to the graph, $a_1\in V_1$, $a_2 \in V_2$. We repeat the rest for every choice of an edge $(b_1,b_2) \in E$: Split $(b_1,b_2)$ into the two edges $(a_1, b_2)$ and $(b_1, a_2)$; mark the new graph as $G'=(V,E')$. Run the algorithm on $G'$ to find a set $C$ of edges that minimizes $\max x_i$. If the value returned is $1$, then $E' \setminus C$ induces an Hamiltonian Cycle in $G$; if a value greater than $1$ is always returned, no such cycle exists in $G$.

• Correctness:

From the new vertices, $a_1$ and $a_2$, the algorithm cannot remove an edge, as it will leave them disconnected. From any other vertex, it must remove at one edge in average, as every other vertex has degree 3.

The algorithm can find a set $C$ with $\min \max x_i = 1$ iff its complement $E' \setminus C$ is an Hamiltonian Path connecting $b_1$ and $b_2$; this path induces an Hamiltonian Cycle in $G$.

Finding an Hamiltonian Cycle in a 3-regular bipartite graphs is NP-Complete (see this article), which completes the proof.