4
$\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 to MO: https://mathoverflow.net/questions/374391/two-from-cubic-subgraph-hardness

$\endgroup$
2
  • 1
    $\begingroup$ Is the subgraph required to be spanning? $\endgroup$ Oct 15 '20 at 21:27
  • $\begingroup$ @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 :) $\endgroup$ Oct 15 '20 at 21:36
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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