5
$\begingroup$

Let $G = (V, E)$ be a connected graph and let $M\subseteq V$. We say that a vertex $v$ is marked if $v\in M$. The problem is to find a simple path in $G$ that visits the maximum possible number of marked vertices. The associated decision problem is: is there a simple path that visits every $v\in M$?

The problem is obviously more general than the problem of finding a Hamiltonian path in an arbitrary graph, so it is NP-hard.

I see no obvious strategy; one can't simply disregard the unmarked vertices, since they (and their incident edges) may be part of the optimal path. Indeed, omitting them may disconnect the graph completely.

My questions:

  1. Does this problem have a well-known name?
  2. Are there any good approximation algorithms, heuristics, or simple reductions to problems I might know more about?
  3. Where can I find this problem discussed in the literature?
$\endgroup$
3
$\begingroup$

This problem is close to Steiner tree problem, just by two restriction:

  1. Instead of tree we have path.
  2. Is not necessary to have shortest path which contains required node.

There is a recent work1 on similar topic, the only difference with your problem statement is they are looking for shortest path which contains all required vertices. They name it Steiner Path problem.

1: Shanti Swaroop Moharana, Ankit Joshi, and Swapnil Vijay. Steiner path for trees. International Journal of Computer Applications, August 2013. Published by Foundation of Computer Science, New York, USA. (doi)

$\endgroup$
  • $\begingroup$ That paper seems to be only considering steiner paths on trees, not on general connected graphs, as the OP specified. $\endgroup$ – Chiel ten Brinke Apr 21 '17 at 10:00
2
$\begingroup$

The nearest neighbor method is often used as a heuristic for different problems. Sometimes the method gives an effective approximation algorithm as well. You could employ it here as well. Here's a skeleton for a heuristic method that maintains a stack $S$ of vertices representing the resulting simple path. Let $F$ be a set containing forbidden vertices, that is, vertices that have already been used in our final path. $F$ should be a data structure supporting fast insertion and lookup, such as a hash table or even a bitvector.

  1. Pick a start node $s_0 \in M$ and let $S := \{s_0\}$, and $F = \emptyset$.
  2. Choose a successor $s_i$ to $\text{top}(S)$, and try to find a path $s_{i-1} \leadsto s_i$ avoiding vertices in $F$. If a path is found, insert the vertices on the path $s_{i-1} \leadsto s_i$ to $F$.
  3. Repeat step 2 until no successor can be found

For a more concrete implementation, consider the following:

  1. Let $\text{Per}_M(G)$ be the marked periphery, that is, the marked vertices with highest eccentricity. Pick the start node $s_0$ such that $s_0 \in \text{Per}_M(G)$.
  2. Using BFS, find the closest vertex to $\text{top}(S)$, where $S$ is the stack maintaining the path. Push the successor to the stack $S$. If a vertex $v$ is forbidden, i.e. $v \in F$, then the BFS won't visit it.
  3. Repeat step 2 until no successor can be found.

I'll argue for the concrete implementation above:

  1. You can think of picking the start vertex $s_0$ from the "convex hull" of $M$. Roughly, the idea is that you only need to expand the path into one direction, thus maximizing the "freedom of movement".
  2. BFS seems like the simplest idea; alternatively one could experiment with other search methods, such as bidirectional search or randomized DFS. A randomized DFS might be a bad choice when there's only a few elements in $F$, then it's possible it'll produce very long paths between two marked vertices. On the other hand, running a randomized DFS -based heuristic resembles the idea of random restarts, which has been very effective in say SAT/CSP solvers or local search methods.

If you are able to find any additional properties of your input graphs and/or $M$, it might very well help you in tuning this heuristic.

$\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.