2
$\begingroup$

The Problem

For a given graph $G$, the cubic subgraph problem asks if there is a subgraph where every vertex has degree 3. The cubic subgraph problem is NP-hard even in bipartite planar graphs with maximum degree at most 4.

Suppose we have an oracle that decides if a bipartite graph contains a "two from cubic subgraph". Can we solve the cubic subgraph problem in polynomial time?

Here "two from cubic" means every vertex is of degree 3 except for two degree 2 vertices.

I would also be happy if there was another way to (dis)prove that two from cubic subgraph is NP-hard.

Some Remarks

One variant I explored is if we are allowed to pick which of the two vertices have degree 2. Then for a given graph $G$ and $uv\in E(G)$, we can ask if $G-uv$ has a two from cubic subgraph with special vertices $u, v$ to solve the cubic subgraph problem. This variant is thus NP-hard. However, I have been unable to find a reduction for the original problem.

One other thing to note is that given a two from cubic subgraph oracle, it is pretty easy to find a two from cubic subgraph: While there is a vertex $v$ such that $G-v$ has a two from cubic subgraph, delete $v$.

We could also relax the restrictions on the problem. For example, is the two from 4-regular subgraph problem NP-hard? Two from 4-regular means every vertex has degree 4 except for two vertices of degree 3. Even any useful facts about two from cubic subgraph or two from 4-regular graphs would be appreciated.

Finally, this point might be a bit off-topic, but we could potentially phrase this as a graph editing problem. "Is there a sequence of edges/vertex deletions leading to a two from cubic subgraph?" I am not familiar with these types of questions but thought it could be an interesting approach.

crossposted from https://math.stackexchange.com/questions/3867470/two-from-cubic-subgraph-hardness

Improve this question
$\endgroup$
3
  • $\begingroup$ Quick clarification on the precise definition of the cubic subgraph problem: is this for induced subgraphs? Also does it require a lower bound on the size of the subgraph (i.e. subgraphs of size larger than a K_4--the smallest induced subgraph that works)? $\endgroup$
    – Quanquan Liu
    Commented Oct 26, 2020 at 21:06
  • $\begingroup$ @QuanquanLiu, the subgraph does not need to be induced. There is also no lower bound on the size of the subgraph. $\endgroup$
    – prohibited graph minor
    Commented Oct 27, 2020 at 0:56
  • $\begingroup$ I guess we require the graph to be non empty or else the problem is trivial $\endgroup$
    – prohibited graph minor
    Commented Oct 27, 2020 at 11:59

1 Answer 1

Reset to default
1
$\begingroup$

A formal proof has been produced. See https://arxiv.org/abs/2105.07161

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .