27

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

Glorfindel
  • 359
  • 1
  • 4
  • 10
Vinicius dos Santos
  • 1,868
  • 12
  • 21
  • 3
    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
  • 1
    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 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 Nov 25 '12 at 02:24
  • 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 Nov 25 '12 at 10:11
  • 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 Apr 21 '13 at 16:51
  • 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 May 01 '13 at 00:06
  • 1
    @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 Jan 29 '20 at 05:01

1 Answers1

27

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.

David Eppstein
  • 50,990
  • 3
  • 170
  • 278
  • "...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
  • 1
    @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
  • 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 Nov 25 '12 at 02:01
  • @NealYoung Sure, but if the hardness follows from just one specific value of k, I would prefer to state this value explicitly. – Tyson Williams Nov 25 '12 at 02:51
  • 1
    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 03:04
  • 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 Nov 25 '12 at 03:14
  • 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 Nov 25 '12 at 05:01
  • 2
    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 05:41
  • 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 Nov 25 '12 at 10:07
  • 3
    @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