Efficient Algorithm for Partitioning a Directed Acyclic Graph into Short Paths

Question

I am working on a problem involving partitioning a directed acyclic graph into distinct multiple paths, each with a maximum length constraint. The goal is to minimize the number of paths (this should below a given number, do not care that much about getting the absolute minimum) while ensuring that the length of each path is below a given threshold (the maximum length constraint). This problem resembles the "Minimum Path Partitioning" problem, which is known to be NP-hard.

I'm seeking advice on efficient algorithms or approximation strategies to tackle this problem. I've considered using a depth-first search (DFS) approach to explore the graph, but I'm open to more advanced techniques. Could anyone recommend heuristic algorithms, approximation approaches, or point me to relevant research in this area? Any insights or guidance would be greatly appreciated.

Answer 1

Claim: There exists an almost linear time approximation algorithm that returns $m$ paths such that $m \leq (2-\frac{1}{k})OPT$ respecting the length conditions. Since you say $k < 20$, this should do fairly well in practice.

Let $P_1^\ast, \ldots, P_{d}^\ast$ be the optimal decomposition of vertex disjoint paths each with length at most $k$.

Observation 1: It must be that $d \geq n/k$

Proof: Each path $P_i^\ast$ has at most $k$ nodes, and in total they have $n$ vertices. So it must be that $d \geq n/k$.

Observation 2: It is possible to get vertex disjoint decomposition $P_1, \ldots, P_c$ such that $c\leq d$ (The paths need not respect the length constraint). The algorithm runs in almost linear time.

Proof: This is known as the minimum path cover in directed acyclic graphs. You can read how to do this on this wikipedia article, but the gist of the argument is that you build a bipartite graph $B(V\cup V, E')$ and connect $uv\in E'$ if and only if $uv \in E$. Then $G'$ has a matching of size $\ell$ if and only if $G$ has vertex-disjoint path cover with $n-\ell$ paths. You can then construct the actual paths from the matching. Since you can solve maximum matching in $\tilde{O}(m^{1+o(1)})$ with max flow, the result follows (in practice, you want to use a specialized maximum matching algorithm on bipartite graphs).

Observation 3: There exists an almost linear time approximation algorithm that returns a decomposition of $m$ paths respecting the length constraint with $m\leq (2-\frac{1}{k})d$.

Proof: Let $P_1, \ldots, P_c$ be the path decomposition from Observation 2. For each path $P_i$ with more than $k$ nodes, we break it into $\lceil \frac{|P_i|}{k} \rceil$ paths in the most obvious way (cake cutting). This gives us a set of vertex-disjoint paths with length at most $k$. However, how many paths do we have? We have

$$\sum_{i=1}^c \lceil \frac{|P_i|}{k} \rceil \leq \sum_{i=1}^c \frac{|P_i|+k-1}{k} = \frac{\sum_{i=1}^c |P_i|}{k} + c - \frac{c}{k} = \frac{n}{k} + (1-\frac{1}{k})c \leq d + (1-\frac{1}{k})d = (2-\frac{1}{k})d$$

The result follows.