# How to find smallest n so that all walks of length greater or equal to n include set of paths

If we have a finite (directed) graph G, and a set of walks P in G. And assume that there exists an n so that all walks of lengths greater than n have at least one p in P as subpath, how would we find n? Does anyone know a polynomial time algorithm in |G|?

For example if we have the graph

1 -> 2 -> 3 -> 4

and P = {(2,3)}

n=2, because we have paths of length 1 that don't include (2,3) as subpath, but all paths of length 2 or 3 include the path/edge (2,3).

(also, to be clear, the graph might or might not have cycles, its allowed to have multiple edges and self-loops. When we talk about subpaths (subwalks) p has to appear contiguously. Like if we consider p as a ordered set of edges (u,v...,w), where each edge ends where the next one starts, a subpath (walk) of p is a substring of that ordered list)

• When you write "path", do you mean a simple path, i.e., all vertices are different? Or do you mean a walk/trail, i.e., you allow vertices and/or edges to be repeated?
– D.W.
Mar 21 at 7:57
• I meant a walk. Mar 21 at 10:27
• Please edit your question to clarify, use the appropriate terminology, and define it. Don't just put clarifications in the comments -- we want questions to be clear to someone who encounter them for the first time, and to not have to read the comments.
– D.W.
Mar 21 at 21:35
– D.W.
Mar 21 at 22:28
• Can you provide a self-contained definition of under what conditions you consider p to be a "subpath" of a walk w? For instance, does p have to appear contiguously in w, or is the requirement that each edge in p must also appear in w? (it's like the difference between a substring vs a subsequence)
– D.W.
Mar 21 at 22:29

Current problem is $$\mathrm{NP}$$-hard, because directed Hamiltonian path problem can be reduced to the current one. (Taking the same graph with empty set of forbidden paths, or adding some new arcs and making each of them a forbidden path. Hamiltonian path exists if and only if the answer is at least $$|G|$$.)
On the other hand there are some polynomially solvable cases of the directed Hamiltonian path problem, like acyclic graphs. However it gives only a pseudopolynomial solution for the current problem, if the number of paths is limited by a constant. (Though paths of length $$1$$ may be not counted here, since each such a forbidden path is equivalent to a removed edge.)
• @hmmmmmmm, if $P=\emptyset$ (the empty set), then finding $n$ is equivalent to finding the (length of the) longest path in the graph. Finding the longest path is NP-hard.