Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
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 Nov 24 '12 at 18:09
Good point. :-) –  Vinicius dos Santos Nov 24 '12 at 19:56
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 Nov 24 '12 at 20:24
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 Nov 24 '12 at 20:30
See also cstheory.stackexchange.com/questions/1215/… 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 Nov 25 '12 at 2:24

1 Answer 1

up vote 20 down vote accepted

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.

share|improve this answer
"...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 Nov 24 '12 at 21:25
@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 Nov 24 '12 at 22:14
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 Nov 25 '12 at 3:04
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 Nov 25 '12 at 5:41
@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 Nov 25 '12 at 13:33

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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