0
$\begingroup$

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)

$\endgroup$
7
  • 1
    $\begingroup$ 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? $\endgroup$
    – D.W.
    Mar 21 at 7:57
  • $\begingroup$ I meant a walk. $\endgroup$
    – hmmmmmmm
    Mar 21 at 10:27
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Mar 21 at 21:35
  • $\begingroup$ Please proof-read your question. I notice multiple grammatical and spelling errors. $\endgroup$
    – D.W.
    Mar 21 at 22:28
  • $\begingroup$ 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) $\endgroup$
    – D.W.
    Mar 21 at 22:29

1 Answer 1

1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ I don't understand. In your first paragraph, are the "forbidden" paths, what I call P? I feel like your answer only makes sense if we only consider simple paths, but I'm not considering only simple paths. Unless I am misunderstanding. $\endgroup$
    – hmmmmmmm
    Mar 20 at 21:57
  • $\begingroup$ Hmm, I think I have a solution now. If we remove all the paths of P, then we just need to check what is the longest path we can find. And after we remove all the paths in P, our graph will be acyclic. Because if there was a cycle with no subpath in P, we could create an infitely long path in P. So in a DAG we can find the longest path in polynomial time, and that +1 will be the answer. $\endgroup$
    – hmmmmmmm
    Mar 20 at 22:08
  • 1
    $\begingroup$ @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. $\endgroup$
    – D.W.
    Mar 21 at 8:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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