<p><em>Claim: There exists an almost linear time approximation algorithm that returns <span class="math-container">$m$</span> paths such that <span class="math-container">$m \leq (2-\frac{1}{k})OPT$</span> respecting the length conditions. Since you say <span class="math-container">$k &lt; 20$</span>, this should do fairly well in practice.</em></p>
<p>Let <span class="math-container">$P_1^\ast, \ldots, P_{d}^\ast$</span> be the optimal decomposition of vertex disjoint paths each with length at most <span class="math-container">$k$</span>.</p>
<p><em>Observation 1: It must be that <span class="math-container">$d \geq n/k$</span></em></p>
<p><em><strong>Proof:</strong></em> Each path <span class="math-container">$P_i^\ast$</span> has at most <span class="math-container">$k$</span> nodes, and in total they have <span class="math-container">$n$</span> vertices. So it must be that <span class="math-container">$d \geq n/k$</span>.</p>
<p><strong>Observation 2:</strong> It is possible to get vertex disjoint decomposition <span class="math-container">$P_1, \ldots, P_c$</span> such that <span class="math-container">$c\leq d$</span> (The paths need not respect the length constraint). The algorithm runs in almost linear time.</p>
<p><em><strong>Proof:</strong></em> This is known as the <a href="https://en.wikipedia.org/wiki/Maximum_flow_problem#Minimum_path_cover_in_directed_acyclic_graph" rel="nofollow noreferrer">minimum path cover in directed acyclic graphs</a>. You can read how to do this on this wikipedia article, but the gist of the argument is that you build a bipartite graph <span class="math-container">$B(V\cup V, E')$</span> and connect <span class="math-container">$uv\in E'$</span> if and only if <span class="math-container">$uv \in E$</span>. Then <span class="math-container">$G'$</span> has a matching of size <span class="math-container">$\ell$</span> if and only if <span class="math-container">$G$</span> has vertex-disjoint path cover with <span class="math-container">$n-\ell$</span> paths.  You can then construct the actual paths from the matching. Since you can solve maximum matching in <span class="math-container">$\tilde{O}(m^{1+o(1)})$</span> with max flow, the result follows (in practice, you want to use a specialized maximum matching algorithm on bipartite graphs).</p>
<p><strong>Observation 3:</strong> There exists an almost linear time approximation algorithm that returns a decomposition of <span class="math-container">$m$</span> paths respecting the length constraint with <span class="math-container">$m\leq (2-\frac{1}{k})d$</span>.</p>
<p><em><strong>Proof:</strong></em> Let <span class="math-container">$P_1, \ldots, P_c$</span> be the path decomposition from Observation 2. For each path <span class="math-container">$P_i$</span> with more than <span class="math-container">$k$</span> nodes, we break it into <span class="math-container">$\lceil \frac{|P_i|}{k} \rceil$</span> paths in the most obvious way (cake cutting). This gives us a set of vertex-disjoint paths with length at most <span class="math-container">$k$</span>. However, how many paths do we have? We have</p>
<p><span class="math-container">$$\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$$</span></p>
<p>The result follows.</p>

CC BY-SA 4.0
2023-08-22T15:53:19.967Z
2023-08-22T15:59:01.737Z
2023-08-22T15:59:01.737Z
user3508551
<p>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 &quot;Minimum Path Partitioning&quot; problem, which is known to be NP-hard.</p>
<p>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.</p>

CC BY-SA 4.0
2023-08-19T03:19:36.373Z
Should the paths be edge disjoint? How big is your "maximum length of a path" (I'll call that $k$)?
user3508551
CC BY-SA 4.0
2023-08-21T18:17:46.873Z
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
user69908
CC BY-SA 4.0
2023-08-22T13:17:54.357Z
How big are the problem instances you want to solve?
Neal Young
CC BY-SA 4.0
2023-09-30T17:47:34.343Z
I'm trying to solve similar problem and asked a question here https://cstheory.stackexchange.com/questions/53375/how-to-reduce-a-code-down-to-its-configuration. 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.
Vetrivel
<graph-theory><graph-algorithms><approximation-algorithms>
Efficient Algorithm for Partitioning a Directed Acyclic Graph into Short Paths
user69908
# Efficient Algorithm for Partitioning a Directed Acyclic Graph into Short Paths

(Asked by: username_0 on 2023-08-18)

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.

**Tags:** graph-theory, graph-algorithms, approximation-algorithms

> **Comments:**
> **username_1**: Should the paths be edge disjoint? How big is your "maximum length of a path" (I'll call that $k$)?  
> **username_0**: 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  
> **username_2**: How big are the problem instances you want to solve?  
> **username_3**: I'm trying to solve similar problem and asked a question here https://cstheory.stackexchange.com/questions/53375/how-to-reduce-a-code-down-to-its-configuration. 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.  

---

## 1 answers

### Answer by username_1 on 2023-08-22. Score: 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](https://en.wikipedia.org/wiki/Maximum_flow_problem#Minimum_path_cover_in_directed_acyclic_graph). 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.


---

