-1
$\begingroup$

This question already has an answer here:

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.

$\endgroup$

marked as duplicate by user742, Pål GD, vonbrand, Luke Mathieson, frafl May 12 '13 at 8:34

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ -1 If you want to discuss about my answer you can leave a comment there, also I answered your comment. This is really duplicated. Also this problem is really as easy as I wrote, just one simple idea is enough (adding one vertex and connect it to all others), you should change your way of thinking about NP-Completeness proof. $\endgroup$ – user742 May 10 '13 at 20:23
  • 2
    $\begingroup$ Let $k = n$. QED. $\endgroup$ – Pål GD May 10 '13 at 21:22
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for your input.I am interested in proving that this problem is NP-Complete. It appears that main challenge here is figuring out how to properly translate the problem into well known NP-Complete problem. Hamiltonian cycle approach, despite looking promising, seems to be an inefficient approach that has lead me and others into confusion. I am confident in the existence of laconic NP-Complete proof mainly because this whole problem is just an exercise and it has a nice solution (which I can't yet figure out). $\endgroup$ – 372 May 12 '13 at 4:15
  • 1
    $\begingroup$ I don't know what you are talking about: Saeed's reduction with a simple padding trick shows the problem to be NP-complete for all $k = n^{\Theta(1)}$. The problem has an $\exp(O(k)) n^{O(1)}$ time algorithm, so it's unlikely to be NP-complete for $k = n^{o(1)}$ (it would contradict ETH if it were). In short, the simple reduction + padding settles the NP-completeness! $\endgroup$ – Sasho Nikolov May 12 '13 at 7:11
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ When he says that some vertex $u$ is center of $W_{n+1}$, how does he check whether a vertex is indeed center ? I ask this question because if there is no polynomial way of finding a center of wheel then the proof is wrong. $\endgroup$ – 372 May 12 '13 at 9:28
  • 1
    $\begingroup$ @AdamPflepinsky you don't need to know where the wheel is. What you need to know is that if (using the names from the question) $G$ has a Hamiltonian cycle, then $G'$ has a $W_{n+1}$ as a subgraph and vice versa. Purely existential. The reduction doesn't say anything about how to find it, just that the wheel is there if and only if the Hamiltonian cycle is. Hence if you could find the wheel in polynomial time, then you could find the cycle in polynomial time. $\endgroup$ – Luke Mathieson May 12 '13 at 9:37
  • $\begingroup$ In fact, the whole point of the proof is to show that it's unlikely that there is a polynomial time algorithm for identifying a wheel in a graph (even when you know all the vertices in the graph are in it). $\endgroup$ – Luke Mathieson May 12 '13 at 9:44

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