2
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ I don't see it. $x_i$ is the degree of the complement of the tree. How do you know the complement of the tree is even connected? $\endgroup$ Mar 2, 2013 at 23:57
  • $\begingroup$ @Brendan, you are right. I'll try to edit the answer accordingly. $\endgroup$
    – Ami Paz
    Mar 3, 2013 at 22:59
  • $\begingroup$ Nice; that seems to work. There is one issue though. The standard definition of NP-completeness uses many-one reductions (an instance of one problem is reduced to a single instance of another) but you have established a Turing reduction (reduction to a polynomial-sized sequence of instances). As far as I know, it is an open question if the NP-complete class is larger if defined with Turing reductions. $\endgroup$ Mar 4, 2013 at 2:35
  • $\begingroup$ Yes, it is not a standard reduction but a Turing one. I also thought more about this fact after writing, and it seems trying two edges sharing a vertex is enough. It will still be a Turing reduction, but at least a cleaner one... $\endgroup$
    – Ami Paz
    Mar 4, 2013 at 10:18
  • $\begingroup$ Thank u for the answers, Ami and Brendan. Just to be sure, does this Turing reduction approach imply the problem (that I asked) is NP-hard or NP-complete or something else? I apologize if my question is silly, since I don't have much knowledge about complexity theory. $\endgroup$
    – adas
    Mar 4, 2013 at 20:28

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.