[Solved]: Wheel subgraph problem

Problem Detail: 

In the following two threads I specified the question in the wrong way (easier to solve that way). Proving that finding wheel subgraphs is NP-complete

Reducing from Hamiltonian Cycle problem to the Graph Wheel problem

My sincere apologies.. I hope moderators will let me post this final version of the question.

In reality the question is different and much harder: is there a way to determine whether a graph $G$ with $n$ vertices has a subgraph that is a wheel $W_{k}$ ? Is possible to show that this is NP-Complete problem ?

The follwig solution offered by Saeed Amiri seems to only work if the problem is to determine whether the entire graph is a wheel.

We will add one extra vertex $v$ to the graph $G$ and we make new graph $G'$, such that $v$ is connected to the all other vertices of $G$, then $G$ has a Hamiltonian cycle if and only if $G'$ has a $W_{n+1}$, is easy to check that if $G$ has a Hamiltonian cycle then $G'$ has a $W_{n+1}$ wheel (just set $v$ as a center), on the other hand, if $G'$ has a $W_{n+1}$ then there are two possibility:

1. $v$ is the center of $W_{n+1} \rightarrow G $ has a Hamiltonian cycle.
2. Another vertex $u$ is the center of $W_{n+1}$ in $G'$, but both $deg(u) = deg(v) = n$ so we can change the labeling of this two vertices (actually they are equivalence under isomorphic), now we have again first possibility.

P.S: By $W_n$ I mean the wheel with $n$ vertex.

It seems that Hamiltonian Cycle approach is wrong because with this approach we are forced to think of the cycles across entire set of vertices. Since the problem is asking do determine presence of subset graph $W_{k}$ the strategy needs to be different.

Asked By : 372

Answered By : Sasho Nikolov

If there are no restrictions on $k$, then the problem of deciding whether $W_k$ is a subgraph of $G$ contains the problem of deciding whether $W_n$ is a subgraph of $G$ as a special case, which implies that the problem is NP-hard. Maybe you are interested in how the hardness of the problem depends on $k$? Here is the complete picture:

• When $k = n^c$ for a constant $c$, the problem remains NP-hard by a padding trick: you can reduce the Hamiltonian cycle problem on graphs of $k$ vertices to the problem of deciding whether $W_k$ is a subgraph of $G$ (which has $n$ vertices) by executing Saeed's reduction and adding $n-k$ isolated vertices;

• When $k = \omega(\log n)$, an algorithm that decides $G$ contains $W_k$ as a subgraph in polynomial time would imply an algorithm that solves 3SAT in subexponential time (because the reduction from 3SAT to Hamiltonian cycle has only linear blowup, as does Saeed's reduction); this would contradict the exponential time hypothesis;

• When $k = O(\log n)$ there exists a polynomial time (deterministic, and a simpler randomized one) algorithm that decides whether $W_k$ is a subgraph of $G$. This is consequence of the beautiful color coding method of Alon, Yuster and Zwick, which allows you to decide whether $H$ is a subgraph of $G$ for any $H$ of constant treewidth and $O(\log n)$ vertices; in your case $W_k$ has treewidth at most 3 (I think it's exactly 3, but have not verified that).

• In general, the algorithm above decides whether $W_k$ is a subgraph of $G$ in time $C^k n^{O(1)}$ for some constant $C$. This implies that, assuming the exponential time hypothesis, the problem is not NP-hard for $k = n^{o(1)}$.

You can understand the Alon, Yuster and Zwick result without using treewidth. There is a simple modification of their algorithm for finding a path of length $k$ that works for finding $W_k$.

Notice the above completely resolves the hardness of finding $W_k$ inside $G$ as a function of the size of $k$: the problem is NP-hard for polynomial $k$, NP-intermediate under the exponential time hypothesis for $k$ superlogarithmic but subpolynomial, and in P for $k$ at most logarithmic.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11942