0
$\begingroup$

Consider the following two problems:

A. Given a directed graph and a parameter $k$, determine if it contains a path (not necessarily simple) of length $k$.

B. Given a directed graph, two vertices $s,t$ and a parameter $k$, determine if the graph contains a path from $s$ to $t$ (not necessarily simple) of length $k$.

How can I reduce problem B to problem A?

I know that I can make a DFS tree at height $k$ with repeating vertices, however it solves the problem directly rather than by reduction.

Improve this question
$\endgroup$
4
  • $\begingroup$ What kind of reduction are you looking for? $\endgroup$ – Steven Oct 22 '20 at 16:22
  • $\begingroup$ k is a constant, and I need to convert graph G to G' s.t by giving a solution to A I can find a solution to B by run the algorithm on G' $\endgroup$ – daniTo Oct 22 '20 at 16:37
  • 1
    $\begingroup$ Are you sure you're not interested in a reduction in the other direction? $\endgroup$ – Yuval Filmus Oct 22 '20 at 17:22
  • $\begingroup$ I'm sure. The opposite it's much easier. $\endgroup$ – daniTo Oct 22 '20 at 18:31
1
$\begingroup$

Since $k$ is a constant you can solve $B$ in polynomial-time by exploring all $O(n^{k-1})$ paths of length $k$ starting from $s$ and ending in $t$, as you point out.

At this point the reduction is trivial: If the answer to an instance $\langle G, s, t\rangle$ of $B$ is "yes" then the corresponding instance of $A$ is $G$. If the answer to the instance $\langle G, s, t \rangle$ is "no", then the instance of $A$ is the empty graph.

Improve this answer
$\endgroup$
5
  • $\begingroup$ The problem that is directe solution and I need reduction I starting to believe that there's is typo at the assignment. thank you anyway $\endgroup$ – daniTo Oct 22 '20 at 19:53
  • $\begingroup$ Formally, this is a reduction... $\endgroup$ – Steven Oct 22 '20 at 19:54
  • $\begingroup$ This "solve-it-up-front" reduction is legitimate because $k$ is not part of the input, so $O(n^{k-1})$ is polynomial in $n$ (and you're allowed to spend that much time converting the problem instance from $B$ to $A$). If you want a reduction that allows $k$ to be part of the input, I can't see one. Problem $A$ gives you very little flexibility: For a digraph containing a cycle, the answer is YES for every $k$. If you restrict inputs to DAGs, then assuming $k \le n$, a reduction that attaches an $n$-path before $s$, and another $n$-path after $t$, and increases $k$ by $2n$, would work. $\endgroup$ – j_random_hacker Oct 24 '20 at 17:26
  • 1
    $\begingroup$ If $k$ is part of the input and is polynomially bounded w.r.t. the size of $G$ then you can reduce $B$ to $A$. A rough sketch of the idea is to create $k$ "layers" where the first layer contains only $s$, the last layer contains only $t$, and the intermediate $k-2$ layers are copies of $G$. The edge edges of $G$ are rewirted to only go from one layer to the next. $\endgroup$ – Steven Oct 24 '20 at 17:35
  • 1
    $\begingroup$ Ah of course, making a nice DAG out of copies! I was thinking too narrowly. I think this is probably the solution the question was looking for -- and perhaps OP wrote "k is a constant" without that actually being in the question, and without realising the implications. $\endgroup$ – j_random_hacker Oct 26 '20 at 23:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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