<p>Here's a reasonably natural one: on an input $(G,k)$, determine whether $G$ has a connected regular subgraph with at least $k$ edges. For 3-regular graphs this is trivial, but if max degree is 3 and the input is connected, not a tree, and not regular, then the largest such subgraph is the longest cycle, so the problem is NP-complete.</p>

CC BY-SA 3.0
2012-11-24T21:25:30.430Z
"...then the solution is either the longest cycle or a maximum matching...". How does your claim depend on k?  It is not true for all k.
Tyson Williams
CC BY-SA 3.0
2012-11-24T22:14:52.767Z
@Tyson, it only needs to be hard for one $k$ to be hard, right?  E.g. take $k=n$.  David, do you need to stipulate that the subgraph should be connected?  (Otherwise, any cycle cover (not just a Hamiltonian cycle) will have $n$ edges, and determining the existence of a cycle cover is in $P$.)
Neal Young
CC BY-SA 3.0
2012-11-25T02:01:25.840Z
Sorry, by "the solution" I meant the regular subgraph with the most edges. Either that subgraph has at least k edges, or none does. And as Neal says, $k=n$ works, and thanks for the "connected" correction.
David Eppstein
CC BY-SA 3.0
2012-11-25T02:51:53.797Z
@NealYoung Sure, but if the hardness follows from just one specific value of k, I would prefer to state this value explicitly.
Tyson Williams
CC BY-SA 3.0
2012-11-25T03:04:15.627Z
David, a maximum matching (of size greater than 1) in G is not a connected subgraph of G. Do you mean to say "...either the longest cycle or a single edge, ..."?
Tyson Williams
CC BY-SA 3.0
2012-11-25T03:14:13.453Z
Yes, the matching part was left over from when I forgot that I needed to require it to be connected to avoid 2-factor polynomiality. Again, thanks for the correction.
David Eppstein
CC BY-SA 3.0
2012-11-25T05:01:17.383Z
But you can't completely remove it. If the graph is a path, then the largest such subgraph is a single edge since there are no cycles.
Tyson Williams
CC BY-SA 3.0
2012-11-25T05:41:23.947Z
Ok, ok. Today doesn't seem to be a good day for me to be rigorous — too much turkey probably. I added some language to rule out this special case.
David Eppstein
CC BY-SA 3.0
2012-11-25T10:07:34.117Z
A lot of critical comments.  I've got one more: why the solution cannot be a 3-regular graph?  If the graph is Hamiltonian, the (G,n) case of your problem is "YES", but it might be "YES" even it is not Hamiltonian.  The NP-completeness seems not *that* obvious.
Yixin Cao
CC BY-SA 3.0
2012-11-25T13:33:54.823Z
@YininCao Since the graph is connected but not regular, there is no way to pick a 3-regular subgraph. Suppose it were. Then there exist a vertex that was not selected since the graph is not regular. Since the graph is connected, this vertex is connected to some 3-regular vertex that was selected. But that means there exists a vertex of degree 4, a contradiction.
Tyson Williams
CC BY-SA 3.0
2012-11-24T20:55:23.013Z
2012-11-25T05:40:28.067Z
2012-11-25T05:40:28.067Z
David Eppstein
<p>Cubic graphs are graphs where every vertex has degree 3. They have been extensively studied and I'm aware that several NP-hard problems remain NP-hard even restricted to subclasses of cubic graphs, but some others get easier. A superclass of cubic graphs is the class of graphs with maximum degree $\Delta \leq 3$.</p>

<blockquote>
  <p>Is there any problem that can be solve in polynomial time for cubic graphs but that is NP-hard for graphs with maximum degree $\Delta \leq 3$?</p>
</blockquote>

CC BY-SA 3.0
2012-11-24T18:09:48.423Z
Degenrate answer that shows there can be different complexities (though neither is NP-Hard): Finding $\delta$ is constant time on cubic graphs but linear on graphs with $\Delta \le 3$. :-)
William Macrae
CC BY-SA 3.0
2012-11-24T19:56:30.067Z
Good point. :-)
Vinicius dos Santos
CC BY-SA 3.0
2012-11-24T20:24:56.953Z
For bad choices of encodings it can even be $NP$-hard when $\Delta \le 3$, but it will be much more valuable to find a problem that doesn't rely on a poor encoding, and even better if that problem is  a well-studied one.
William Macrae
CC BY-SA 3.0
2012-11-24T20:30:50.227Z
To expand on William's comment, here is an artificial problem.  *Given a graph $G$, does the degree sequence of $G$, interpreted as the encoding of an instance of 3-SAT, represent a satisfiable instance?*  (Assuming the encoding is such that the all-3 degree sequence represents a satisfying assignment for every $n$.) :-)
Neal Young
CC BY-SA 3.0
2012-11-25T02:24:26.497Z
See also http://cstheory.stackexchange.com/questions/1215/np-hard-problems-on-trees for more inspiration (e.g., problems that are hard on trees of max degree 3, but trivial if there are no leaf nodes).
Jukka Suomela
CC BY-SA 3.0
2012-11-25T10:11:28.740Z
What's the complexity of MAXIMUM ADJACENCY MATCHING (equivalent to Xuong Tree problem) on graphs of maximum degree 3?  I'm sure it's polynomial-solvable in 3-regular graphs.
Yixin Cao
CC BY-SA 3.0
2013-04-21T16:51:50.397Z
I have a quick related question: Vertex cover is known to be hard on max degree 3 planar graphs. Is it known that vertex cover is hard on cubic planar graphs?
101011
CC BY-SA 3.0
2013-05-01T00:06:18.127Z
I think you should ask this as a new question, and link this older question if you think it's related enough.
Vinicius dos Santos
CC BY-SA 4.0
2020-01-29T05:01:22.370Z
@101011 Vertex cover (and MaxIS) are NP-complete even for cubic planar graphs (see GT1 and GT20 in Garey and Johnson). There is a paper that claim that the problem remains NP-complete even with the further restriction of 3-connectedness.
Cyriac Antony
<graph-theory><graph-algorithms><np-hardness>
Is there a problem that is easy for cubic graphs but hard for graphs with maximum degree 3?
Vinicius dos Santos
# Is there a problem that is easy for cubic graphs but hard for graphs with maximum degree 3?

(Asked by: username_0 on 2012-11-24)

Cubic graphs are graphs where every vertex has degree 3. They have been extensively studied and I'm aware that several NP-hard problems remain NP-hard even restricted to subclasses of cubic graphs, but some others get easier. A superclass of cubic graphs is the class of graphs with maximum degree $\Delta \leq 3$.

> Is there any problem that can be solve in polynomial time for cubic graphs but that is NP-hard for graphs with maximum degree $\Delta \leq 3$?

**Tags:** graph-theory, graph-algorithms, np-hardness

> **Comments:**
> **username_1**: Degenrate answer that shows there can be different complexities (though neither is NP-Hard): Finding $\delta$ is constant time on cubic graphs but linear on graphs with $\Delta \le 3$. :-)  
> **username_0**: Good point. :-)  
> **username_1**: For bad choices of encodings it can even be $NP$-hard when $\Delta \le 3$, but it will be much more valuable to find a problem that doesn't rely on a poor encoding, and even better if that problem is  a well-studied one.  
> **username_2**: To expand on William's comment, here is an artificial problem.  *Given a graph $G$, does the degree sequence of $G$, interpreted as the encoding of an instance of 3-SAT, represent a satisfiable instance?*  (Assuming the encoding is such that the all-3 degree sequence represents a satisfying assignment for every $n$.) :-)  
> **username_3**: See also http://cstheory.stackexchange.com/questions/1215/np-hard-problems-on-trees for more inspiration (e.g., problems that are hard on trees of max degree 3, but trivial if there are no leaf nodes).  
> **username_4**: What's the complexity of MAXIMUM ADJACENCY MATCHING (equivalent to Xuong Tree problem) on graphs of maximum degree 3?  I'm sure it's polynomial-solvable in 3-regular graphs.  
> **username_5**: I have a quick related question: Vertex cover is known to be hard on max degree 3 planar graphs. Is it known that vertex cover is hard on cubic planar graphs?  
> **username_0**: I think you should ask this as a new question, and link this older question if you think it's related enough.  
> **username_6**: @username_5 Vertex cover (and MaxIS) are NP-complete even for cubic planar graphs (see GT1 and GT20 in Garey and Johnson). There is a paper that claim that the problem remains NP-complete even with the further restriction of 3-connectedness.  

---

## 1 answers

### Answer by username_7 on 2012-11-24. Score: 27 | Accepted answer

Here's a reasonably natural one: on an input $(G,k)$, determine whether $G$ has a connected regular subgraph with at least $k$ edges. For 3-regular graphs this is trivial, but if max degree is 3 and the input is connected, not a tree, and not regular, then the largest such subgraph is the longest cycle, so the problem is NP-complete.

> **Comments:**
> **username_8**: "...then the solution is either the longest cycle or a maximum matching...". How does your claim depend on k?  It is not true for all k.  
> **username_2**: @Tyson, it only needs to be hard for one $k$ to be hard, right?  E.g. take $k=n$.  David, do you need to stipulate that the subgraph should be connected?  (Otherwise, any cycle cover (not just a Hamiltonian cycle) will have $n$ edges, and determining the existence of a cycle cover is in $P$.)  
> **username_7**: Sorry, by "the solution" I meant the regular subgraph with the most edges. Either that subgraph has at least k edges, or none does. And as Neal says, $k=n$ works, and thanks for the "connected" correction.  
> **username_8**: @NealYoung Sure, but if the hardness follows from just one specific value of k, I would prefer to state this value explicitly.  
> **username_8**: David, a maximum matching (of size greater than 1) in G is not a connected subgraph of G. Do you mean to say "...either the longest cycle or a single edge, ..."?  
> **username_7**: Yes, the matching part was left over from when I forgot that I needed to require it to be connected to avoid 2-factor polynomiality. Again, thanks for the correction.  
> **username_8**: But you can't completely remove it. If the graph is a path, then the largest such subgraph is a single edge since there are no cycles.  
> **username_7**: Ok, ok. Today doesn't seem to be a good day for me to be rigorous — too much turkey probably. I added some language to rule out this special case.  
> **username_4**: A lot of critical comments.  I've got one more: why the solution cannot be a 3-regular graph?  If the graph is Hamiltonian, the (G,n) case of your problem is "YES", but it might be "YES" even it is not Hamiltonian.  The NP-completeness seems not *that* obvious.  
> **username_8**: @YininCao Since the graph is connected but not regular, there is no way to pick a 3-regular subgraph. Suppose it were. Then there exist a vertex that was not selected since the graph is not regular. Since the graph is connected, this vertex is connected to some 3-regular vertex that was selected. But that means there exists a vertex of degree 4, a contradiction.  

---

