2
$\begingroup$

I stumbled upon the following problem during my research.

I have a bipartite graph, and I want to determine the minimum number of edges to to remove so that the maximum path length in the resulting graph is 2.

Is this problem NP-hard? I was trying to come up with a polynomial time algorithm (and failed) and also tried to prove its NP-hardness, but also having a hard time.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Figured out this is indeed NP-hard. This is equivalent to finding the maximum spanning star forest in a bipartite graph, which in turn is as hard as finding the minimum dominating set in a bipartite graph, which is NP-hard.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Did you by any chance created two accounts? If yes please follow this. Could you elaborate your answer? $\endgroup$
    – Evil
    Apr 13, 2016 at 0:24

Your Answer

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

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