8
$\begingroup$

While discussing the question I had asked here, @NealYoung and I encounter another problem, which is to judge complexity of the problem below:

Given a connected undirected graph, finding a maximum-size subset of the edges such that every vertex has degree at most two.

I have found some paper on complexity of relative problems. Most of them added more constraint on the original one. FOS03 added "with no odd cycles" and proved that it is NP-hard. CTW07 implied that the variant added "with no 3-cycle" is P referring to another paper (which I failed to find). But I have been unable to judge complexity of the original problem. So how to judge it? Thanks.

Improve this question
$\endgroup$
14
$\begingroup$

The generalized problem (such that each vertex $v$ has degree at most $b_v$) is called the $b$-matching problem. Chapter 31 of Schrijver's book is devoted to the subject. It can be solved in strongly polynomial time.

The case that $b_v=2$ for every vertex $v$ has been studied, particularly for providing lower bounds for the traveling salesman problem.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Yeah I see. Thank you for your answer! Maybe you can also give some suggestion about the former question linked on the top? $\endgroup$ – RIC_Eien May 22 '13 at 12:31
  • 9
    $\begingroup$ @RIC_Eien: My comment is not really serious, but it seems that you are very happy with the answer. If so, why can you not accept it? $\endgroup$ – user13667 Jun 9 '13 at 13:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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