Wheel subgraph problem [duplicate]

Question

This question already has an answer here:

• Reducing from Hamiltonian Cycle problem to the Graph Wheel problem [duplicate] 1 answer

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.

Answer 1

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.

Answer 2

As has been noted, Saeed Amiri's solution is quite correct. The problem seems to be that you are misapprehending what needs to be shown to prove NP-completeness.

Of course you have to show that the problem is in NP, but from other posts I gather that's no issue.

The sticking point lies with the reduction from an NP-hard problem. Given an NP-hard problem $A$ and a problem $B$, if we can construct a polynomial time computable function $f$ such that for every instance $a$ of $A$ there exists some instance $b$ of $B$ such that $a$ is a Yes-instance if and only if $b$ is a Yes-instance.

Note the for every and there exists some parts. This means $f$ maps every instance of $A$ to something, but it says nothing about how many instances of $B$ are the result of some mapping. That is, it's perfectly fine to have $b' \in B$ such that there is no $a' \in A$ where $b' = f(a')$.

To put it another way, if we take $f(A)$ to be the image of $A$ under $f$, then it's okay that $f(A) \subset B$, it's not necessary that $f(A) = B$.

A third way, $f$ doesn't need to be a surjection (or even an injection).

So for your problem, Saeed Amiri's reduction takes any instance of Hamiltonian Cycle and produces some instance of the Wheel Subgraph Problem. It just happens that the only instances it pick out are those where $k=n$, but this doesn't matter, the reduction is enough to show NP-hardness (and hence with membership in NP, completeness).

If you then want to change your problem to force $k < n$, then a tiny modification to Saeed's proof is enough, we add a second new vertex, with no neighbours. If you want to place further restrictions on $k$, then Sasho Nikolov's answer is fantastic.

An alternate route to understanding this might be to think of the "proof by restriction" technique. This states that if $A'$ is a subproblem of $A$, and $A'$ is NP-hard, then $A$ is also NP-hard. Most reductions use this implicitly, as we have done here. Hamiltonian Cycle is NP-hard, we map that to a subproblem of the Wheel Subgraph Problem (where $n=k$), so this is also NP-hard, and hence the Wheel Subgraph Problem is in general NP-hard (as one of its subproblems is).