27
$\begingroup$

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

Improve this question
$\endgroup$
9
  • 3
    $\begingroup$ 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$. :-) $\endgroup$
    – William Macrae
    Commented Nov 24, 2012 at 18:09
  • $\begingroup$ Good point. :-) $\endgroup$
    – Vinicius dos Santos
    Commented Nov 24, 2012 at 19:56
  • $\begingroup$ 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. $\endgroup$
    – William Macrae
    Commented Nov 24, 2012 at 20:24
  • 1
    $\begingroup$ 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$.) :-) $\endgroup$
    – Neal Young
    Commented Nov 24, 2012 at 20:30
  • 1
    $\begingroup$ @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. $\endgroup$
    – Cyriac Antony
    Commented Jan 29, 2020 at 5:01

1 Answer 1

Reset to default
27
$\begingroup$

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.

Improve this answer
$\endgroup$
10
  • $\begingroup$ "...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. $\endgroup$
    – Tyson Williams
    Commented Nov 24, 2012 at 21:25
  • 1
    $\begingroup$ @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$.) $\endgroup$
    – Neal Young
    Commented Nov 24, 2012 at 22:14
  • 1
    $\begingroup$ 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, ..."? $\endgroup$
    – Tyson Williams
    Commented Nov 25, 2012 at 3:04
  • 2
    $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Commented Nov 25, 2012 at 5:41
  • 3
    $\begingroup$ @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. $\endgroup$
    – Tyson Williams
    Commented Nov 25, 2012 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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