Efficient algorithm for graph problem

Question

Let $D=(V,E)$ be a directed graph, $S,T\subset V$ and $f:V\rightarrow \{1,\ldots, k\}$ a positive, bounded weight-function and $l\in \mathbb{N}$, find a path $v_1,\ldots, v_l\in V$ with $v_1\in S$ and $v_l \in T$ of minimal cost $\sum_{i=1}^lf(v_i)$.

The length of the path has to be precisely $l$. However, an algorithm that finds the best solution for a path of length $1, 2, \ldots, l$ would be even better.

I use Simplex (Gurobipy, if you are curious) to solve this problem. I think my formulation can be improved, but I am looking for other approaches or known problems to which this can be reduced. I can provide more information about the size of $V, E, k,\ldots$ if needed.

I don't know if this falls more into the jurisdiction of stack overflow. In that case, I'll repost the question there.

Edit: In case you are curious, the original problem is about the Italian Dominating Number.

Edit: The solution is in general not simple. Also, I'm looking for an optimal solution, not a heuristic.

Answer 1

If $v_1$ and $v_l$ are fixed then constructing a minimum weight breadth-first tree of height $l{-}1$ and finally optimally attach vertex $v_l$.

Iterating over all candidate pairs of $v_1$ and $v_l$ would then yield the optimal solution.

Minimum weight breadth first trees seem to be the method of choice for controlling the number of edges of paths.

Addendum:

having learned that the paths need not be simple, we can reduce the fixed-cardinality shortest path to an ordinary shortest path problem as follows:

if we require a shortest path with exactly $l{-}1$ edges and the additional constraint that the start-vertex must be from a subset $S$ and the terminal vertex from a subset $T$ of $V$, we can achieve this as follows:

• add a super-startvertex $\mathrm{A}$ and a super-terminalvertex vertex $\Omega$, that's analogous to RobPratts idea for solving the problem via cost-flows (but we are reducing the problem to an ordinary shortest path problem).

• generate $n$ sets $V_1=S,V_2=V,\,\dots,\,V_{l{-}1}=V,V_l=T$ of vertices, each dedicated for path whose number of edges equal the index of the vertex set.

• put the vertices of $S=V_1$ in the adjacency list of $\mathrm{A}$ and put $\Omega$ in the adjacency lists of vertices in $V_l=T$

• replace the adjacency lists of vertices from $V_i$ with the corresponding vertices (i.e. with the same label) from $V_{i+1}$

• calculate in the so generated graph the shortes path from $\mathrm{A}$ to $\Omega$

In case $S$ and $T$ are not disjoint, that would also be able generate a closed cycle as an answer; if that is not desired, it must be ruled out otherwise.

Answer 2

A standard approach for handling a choice of sources and a choice of sinks is to introduce a supersource $s$ with a zero-cost arc to each $v\in S$ and a supersink $t$ with a zero-cost arc from each $v\in T$. Now find a path from $s$ to $t$. The successor of $s$ is your $v_1$, and the predecessor of $t$ is your $v_\ell$.

Answer 3

The normal A* algorithm can be modified to quit only at a path of the desired length. As @RobPratt suggested, two new vertices can avoid multiple sinks and sources.

Answer 4

If one is interested only in finding the minimal cost, then transfer-matrix method over the tropical semiring $R$ will do the job. Namely, consider the line digraph $G:=L(D)$ and its weighted adjacency matrix over $R$, raise it to the power $l-2$, and "sum up" (in $R$) the entries corresponding to the pairs of possible start and end edges in $G$ (corresponding to pairs of vertices from $S\times T$ in $D$) multiplied by their costs.