4
$\begingroup$

Problem: Suppose we had a directed graph $G(V,E)$ with strictly positive edge weights, a nonempty set $A$ (special vertices) such that $A \subseteq V$, a positive integer $C$, and a starting vertex $S \in V$. Find the shortest path starting at $S$ and containing at least $C$ vertices in $A$ (cycles are OK). If no path exists, output -INF or +INF. Polynomial time algorithms only (in $V$, $E$, and $C$).

My attempt: If there are at least $C$ vertices in $A$ that I want to find, then maybe I could replicate the graph $C$ times, where each replicated graph is like a layer. So when running Dijkstra, if I step into a special vertex, that vertex connects me to its counterpart in the next layer. If there are 10 vertices in the graph and I want to find when I step into the special vertices 3 times, then there will be 30 total vertices because each layer contains the identical looking 10 vertices.

I have issues translating this idea to any sort of (pseudo) code. Perhaps my idea isn't even valid; in that case, any help would be appreciated in proposals of a different solution.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Path is a standard term implying that no vertex appears more than once, so even though you say "cycles are OK" (which implies that a vertex can occur more than once), this is a bit confusing. The standard term for describing a path that allows a vertex to appear more than once is a walk. $\endgroup$ – j_random_hacker Mar 9 '18 at 14:20
4
$\begingroup$

The Hamitonian path problem is reducible to your problem. Given a directed graph $G(V,E)$, set $C=|V|$ (number of nodes), $A = V$, and weight of each edge is equal to $1$. Thus, this instance of the problem requires to find a shortest path containing all vertices. Since it asks to find the shortest path, cycles are not allowed, and since it asks to include all vertices, the path visits all vertices once. This is a Hamiltonian path. So, your problem is NP-complete meaning it is unlikely to find a polynomial time algorithm. In this case you should try approximation algorithms or Linear/Integer programming algorithms.

Note (on @user53923's comment): There is a chance to get a path with a cycle, from the problem from the question, which is shortest including all vertices. But in this case we could check in polynomial time if the path has a cycle and if it has then simply reject. This would mean the graph does not have a Hamiltonian path, otherwise it would return it since its length would be shorter from that containing a cycle.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ As far as I understand, cycles are in principle allowed (and note that a shortest path containing all vertices is not necessarily simple). But if you verify whether the problem from the question finds a path of length exactly $|V|-1$, the reduction is correct I think. $\endgroup$ – user53923 Sep 20 '17 at 7:47
  • 1
    $\begingroup$ @user53923, good point! There is a chance to get a path with a cycle which is shortest including all vertices. But in this case we could check in polynomial time if the path has a cycle and if it has then simply reject. This would mean the graph does not have a Hamiltonian path, otherwise it would return it since its length would be shorter from that containing a cycle. $\endgroup$ – fade2black Sep 20 '17 at 8:14
  • $\begingroup$ I think your reasoning is incorrect. Even if the graph contains no HP, it might nevertheless contain a walk (in which vertices and edges may appear more than once) of length $|V|-1$, so in this case your reduced instance would return YES when the correct answer is NO. Example: $E = \{ab, ac, cd, dc, ce\}$ contains 5 vertices and a walk of length 4 ($a \rightarrow c \rightarrow d \rightarrow c \rightarrow e$) but no HP (because of $b$). $\endgroup$ – j_random_hacker Mar 9 '18 at 14:08
  • $\begingroup$ Also, checking whether the returned walk is a HP or not doesn't help: there is no reason for the algorithm to "prefer" to return a HP if both an HP and a non-HP walk of length $|V|-1$ exist (they are both the same length). So if you check the particular returned walk and report "NO" when you find it is a non-HP, you could be returning the wrong answer -- an HP may exist as well. $\endgroup$ – j_random_hacker Mar 9 '18 at 14:12
2
$\begingroup$

The problem can be solved in polynomial time if we interpret this condition:

Find the shortest path starting at $S$ and containing at least $C$ vertices in $A$ (cycles are OK)

... in the following way: find the shortest path containing at least $C$ occurrences of vertices from $A$. That would include, for instance, the path $(S, a_1, a_2, a_1)$ for $C=3$ and $a_i \in A$. You can't reduce this problem to Hamiltonian path problem, so it doesn't contradict the answer by @fade2black. Probably your interview assumed this interpretation.

Algorithm

Before doing anything, let's assume we've found the distances between any two vertices $u, v \in V$, let's call it $d[u, v]$ (Floyd–Warshall algorithm is polynomial).

Suppose $C = 1$. Since the weights are positive, the shortest path must end with a vertex from $A$ (by going further we'll only make the path longer). Hence, we are interested in $\min_{a \in A} d[s, a]$. Let's view it as a base and call it

$$D_1(a) = d[s, a],$$

the solution for all ending vertices for $C = 1$.

Next, we can compute $D_{n+1}$ from $D_{n}$. Like before, the shortest path that contains $n+1$ vertices from $A$ must end with some $a \in A$. In addition, for the previous vertex on that path $a'$ the following holds:

  • the path from $S$ to $a'$ is optimal (containing $n$ vertices from $A$);
  • the path from $a'$ to $a$ is optimal.

Hence,

$$D_{n+1}(a) = \min_{a' \in A} (D_n(a') + d[a', a])$$

Note: we never check how many unique vertices from $A$ are on the path and count only the occurrences.

In total, the algorithm does $C$ cycles that compute $|V|$ values, each requiring finding minimum of $|V|$ values. The result is thus $O(|V|^3 + C \cdot |V|^2) = O(|V|^3).$

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ +1. You can tighten this a bit: Dijkstra, in time $O(|E|+|V|\log|V|)$, is enough for the first phase, since we only need the distance from $S$ to every other vertex. In the second phase, for each of the $C-1$ iterations, it suffices to find the minimum by checking each edge between two vertices in $A$, i.e. in $O(C \min(|E|, |A|^2))$ time. One more thing: The reduction attempted by fade2black is from Hamiltonian Path to this problem. $\endgroup$ – j_random_hacker Mar 9 '18 at 14:36
  • 1
    $\begingroup$ You're right, the reduction is the other way around. Concerning the speed-up: the minimum distance $d[a', a]$ isn't necessarily the edge, it can include vertices not from $A$, that's why we need the minimum distance between any pair. Or am I missing anything? $\endgroup$ – Maxim Mar 9 '18 at 15:11
  • 1
    $\begingroup$ Whoops, you're absolutely right about $d[a', a]$ not necessarily being a single edge. In that case, as you say it would be best to spend $O(n^3)$ "up front" on Floyd-Warshall to calculate all these $d[\cdot, \cdot]$ values, and then we only need $O(C|A|^2)$ time for the final $C-1$ iterations (which admittedly isn't much better than $O(C|V|^2)$). $\endgroup$ – j_random_hacker Mar 9 '18 at 21:49

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.