<p>The generalized problem (such that each vertex $v$ has degree at most $b_v$) is called the $b$-matching problem. Chapter 31 of <a href="http://rads.stackoverflow.com/amzn/click/3540443894" rel="nofollow">Schrijver's book</a> is devoted to the subject. It <a href="http://www.sciencedirect.com/science/article/pii/0020019087901785" rel="nofollow">can be solved in strongly polynomial time.</a></p>

<p>The case that $b_v=2$ for every vertex $v$ has been studied, particularly for <a href="http://www.jstor.org/stable/pdfplus/2030652.pdf" rel="nofollow">providing lower bounds for the traveling salesman problem</a>.</p>

CC BY-SA 3.0
2013-05-22T12:31:26.873Z
Yeah I see. Thank you for your answer! Maybe you can also give some suggestion about the former question linked on the top?
RIC_Eien
CC BY-SA 3.0
2013-06-09T13:23:12.243Z
@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?
user13667
CC BY-SA 3.0
2013-05-21T20:46:45.967Z
2015-05-09T23:35:56.310Z
2015-05-09T23:35:56.310Z
Austin Buchanan
<p>While discussing the question I had asked <a href="https://cstheory.stackexchange.com/questions/17412">here</a>, @NealYoung and I encounter another problem, which is to judge complexity of the problem below:</p>

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

<p>I have found some paper on complexity of relative problems. Most of them added more constraint on the original one. <a href="http://fileadmin.cs.lth.se/cs/Personal/Andrzej_Lingas/f-o.pdf" rel="nofollow noreferrer">FOS03</a> added "with no odd cycles" and proved that it is NP-hard. <a href="http://rnc.r.dendai.ac.jp/~chen/papers/max2edge4.pdf" rel="nofollow noreferrer">CTW07</a> 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.</p>

<graph-theory><np-hardness><cc.complexity-theory>
What is complexity of this max-edge subgraph problem?
RIC_Eien
# What is complexity of this max-edge subgraph problem?

(Asked by: username_0 on 2013-05-21)

While discussing the question I had asked [here](https://cstheory.stackexchange.com/questions/17412), @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](http://fileadmin.cs.lth.se/cs/Personal/Andrzej_Lingas/f-o.pdf) added "with no odd cycles" and proved that it is NP-hard. [CTW07](http://rnc.r.dendai.ac.jp/~chen/papers/max2edge4.pdf) 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.

**Tags:** graph-theory, np-hardness, cc.complexity-theory


---

## 1 answers

### Answer by username_1 on 2013-05-21. Score: 14

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](http://rads.stackoverflow.com/amzn/click/3540443894) is devoted to the subject. It [can be solved in strongly polynomial time.](http://www.sciencedirect.com/science/article/pii/0020019087901785)

The case that $b\_v=2$ for every vertex $v$ has been studied, particularly for [providing lower bounds for the traveling salesman problem](http://www.jstor.org/stable/pdfplus/2030652.pdf).

> **Comments:**
> **username_0**: Yeah I see. Thank you for your answer! Maybe you can also give some suggestion about the former question linked on the top?  
> **username_2**: @username_0: 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?  

---

