Two from cubic subgraph hardness

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.

• 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)? Oct 26 '20 at 21:06
• @QuanquanLiu, the subgraph does not need to be induced. There is also no lower bound on the size of the subgraph. Oct 27 '20 at 0:56
• I guess we require the graph to be non empty or else the problem is trivial Oct 27 '20 at 11:59

1 Answer

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