1
$\begingroup$

Suppose we have digraph G, set of its vertices W and two (possibly equal) vertices s and f. I'm looking for an algorithm which will solve the following problem: whether there is path from s to f passing through all vertices from W; if yes, return any of such paths. By "path" i mean path in the most general sense: repetitions of edges and vertices are allowed.

Unfortunately no information about graph is known: it needn't be connected in any sense, it might have oriented cycles, etc.

My idea was to modificate DFS somehow but i didn't manage to proceed. Any ideas and hints will be highly appreciated. Thanks in advance.

$\endgroup$
2
$\begingroup$

Decompose the graph into strongly connected components. You get a DAG, each vertex of which represents a strongly connected component. Let $S,F$ be the strongly connected components containing $s,f$. There is a path from $s$ to $f$ if there is a path from $S$ to $F$ in the decomposition (this includes the case $S=F$). Any such path can only pass through (genuine) vertices in the connected components that appear on the path from $S$ to $F$ in the decomposition, and conversely we can arrange it to pass through all of them (since you allow the paths not to be simple). This leads to a simple criterion for your problem – can you state it?

$\endgroup$

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.