1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Should the paths be edge disjoint? How big is your "maximum length of a path" (I'll call that $k$)? $\endgroup$ Aug 19, 2023 at 3:19
  • $\begingroup$ Sorry for the delayed reply. k would be <20, typically 10-15. The resulting paths would be node- disjoint (and therefore path disjoint) - no two paths should share nodes $\endgroup$
    – user69908
    Aug 21, 2023 at 18:17
  • $\begingroup$ How big are the problem instances you want to solve? $\endgroup$
    – Neal Young
    Aug 22, 2023 at 13:17
  • $\begingroup$ I'm trying to solve similar problem and asked a question here cstheory.stackexchange.com/questions/53375/…. The domain I'm trying to solve is close ended unlike yours. Code is a graph, in code, I'm trying to find ways to reduce it down to its grammar, visualise data flow, control flow, ultimately reduce it down to custom grammar and perform code refactor. $\endgroup$
    – Vetrivel
    Sep 30, 2023 at 17:47

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.