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

$\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$ 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$ Oct 27, 2020 at 0:56
  • $\begingroup$ I guess we require the graph to be non empty or else the problem is trivial $\endgroup$ Oct 27, 2020 at 11:59

1 Answer 1

1
$\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 and acknowledge you have read our privacy policy.

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