# Reductions among two problems related to walks of length $k$

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.

• What kind of reduction are you looking for? – Steven Oct 22 at 16:22
• 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' – daniTo Oct 22 at 16:37
• Are you sure you're not interested in a reduction in the other direction? – Yuval Filmus Oct 22 at 17:22
• I'm sure. The opposite it's much easier. – daniTo Oct 22 at 18:31

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.
• 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. – j_random_hacker Oct 24 at 17:26
• 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. – Steven Oct 24 at 17:35