# 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.

• Is the subgraph required to be spanning? Oct 15 '20 at 21:27
• @MishaLavrov the subgraph does not need to be spanning. I think if we require it to be spanning it is quite easily solved by finding a maximum cardinality 3-matching :) Oct 15 '20 at 21:36