1
$\begingroup$

I have an unweighted undirected graph and I have to find if there exists a path between two vertices $u,v$ that visits set of specific nodes $A$. $A$ can contain $1-10$ nodes. No node can be visited more than once.

I thought about finding all paths between $u,v$ and then check if those paths contain vertices from $A$. I optimized it by not considering those paths in which no of vertices is less than cardinality of $A$. But this doesn't affect much. If $A$ has only one then it's useless.

As suggested in comments, I want to start with 1 node in $A$ to simplify it. I will try to extend it to multiple vertices on my own.

There's another way if we precalculate path between every pair of nodes and then check if we have a path passing through $A$ but the time complexity will be very costly.

I was thinking if it can be done using lower bounds max-flow : The lower bound max-flow algorithm computes a flow, which must include all the edges that have a positive $(>0)$ lower bound value. If only one edge has a positive lower bound, the flow computed by the algorithm can be used to build a simple path, which includes such edge. The “edge” instance of the problem can be transformed into its “node” equivalent by first splitting the include-node into two half-nodes, i.e., $n_1$ and $n_2$. All incoming edges to the original node converge to $n_1$. All outgoing edges of the original node emerge from $n_2$. A directed edge $e_l$ from $n_1$ to $n_2$ is added with a positive lower bound value. All other (original) edges of the network have zero lower bound. Now, applying the lower bound max-flow algorithm to this flow network, a feasible flow from source to destination can be found such that $e_l$ is included in at least one of the (flow) augmenting paths.

Then on merging $n_1$and $n_2$ the simple path can be traced. But I couldn't think of code or that matter a code to implement it.

EDIT: The problem here lies about how to make it a simple path so as to not to repeat vertices.

So is there any an efficient way to do this (maybe polynomial or less)?

$\endgroup$
  • $\begingroup$ Welcome to CS.SE! As usual, a good problem-solving strategy is to start with simpler versions of the problem. Suppose your set $A$ contained only one node. Could you find an efficient algorithm in that case? Next... What if your set contained only two nodes? Could you find an efficient algorithm for that case? What's the fastest algorithm you can find? Next... Can you generalize that to an arbitrary number of nodes? I suggest spending some more time thinking on this, then editing the question to show how much progress you've made along these lines and at what point you got stuck. $\endgroup$ – D.W. Jun 16 '17 at 21:17
  • $\begingroup$ I didn't understand how your flow-based algorithm would work. The output of the maximum flow algorithm might be a flow that is not a simple path, but that contains places where the flow splits. It's not clear to me how you plan to handle that (or why you think that cannot happen). $\endgroup$ – D.W. Jun 16 '17 at 21:19
  • $\begingroup$ @D.W. Thanks, I will edit my question according to my progress. And about max flow, that's exactly the problem. It only solved for including the specific node but I couldn't think how not to repeat vertices. I'm stuck at that point. $\endgroup$ – Sam Thornton Jun 16 '17 at 21:22
  • $\begingroup$ I don't think max-flow is a useful approach (for the reasons I hinted at); I don't see how to surmount the problems that I hinted at in my second comment. Instead, I suggest that you follow the approach I mentioned in my first comment. When I was talking about "progress", I meant "progress following that approach". $\endgroup$ – D.W. Jun 16 '17 at 21:24
  • $\begingroup$ @D.W. Oh, I got it. I'm still trying to figure something out. $\endgroup$ – Sam Thornton Jun 17 '17 at 12:10

Your Answer

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

Browse other questions tagged or ask your own question.