Find a simple path visiting all marked vertices

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:

• Does this problem have a well-known name?

• Are there any good approximation algorithms, heuristics, or simple reductions to problems I might know more about?

• Where can I find this problem discussed in the literature?

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

• Instead of tree we have path.

• 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

1. Published by Foundation of Computer Science, New York, USA. (doi)

StackExchange Computer Science Q#14390, answer score: 3