Tag Info

1

What is $K$? If $K$ is constant then this problem is in $P$. The number of paths with source s is less than $\binom{n-1}{K} \in O(n^K)$. So one can enumerate these paths in polynomial time. At first, we will construct an algorithm, that finds one path from s to t with length $\ge K$ function has_paths(G,s,t,K): { for all paths (s=v_1,v_2,...v_{K_1}) in G\{t}...

1

The provided answer is not valid to the question, as far as I know. Your rebuttal that there could be some other clever certificate is totally reasonable. However, is it possible that you misunderstood the question? The question may be asking why this problem is not straightforwardly in NP-complete, in which case the "obvious" certificate would ...

0

A mapping $f$ from instances of a decision problem $A$ to instances of a decision problem $B$ is a reduction if $x \in A$ iff $f(x) \in B$. In your case, instances of both problems are of the form $(G,k)$. Such instances are Yes instances if there is a clique-cover of $G$ of size at most $k$. Thus a function mapping $(G,k)$ to $(G',k')$ is a reduction ...

1

Though your definition of $E$ is not clear. I am assuming that $E = \{(x,y) \mid x \in W \textrm{ and } y \in W'\} \, \cup \{(x,y) \mid x,y \in W \textrm{ and } (x,y) \notin F\}$. In other words, $E$ contain all edges between sets $W$ and $W'$, and the edges that are not in $F$. Proof Forward Direction: Suppose $H$ contains a clique of size at most $k$. Let ...

Top 50 recent answers are included