<p>What you are asking for has been studied in the general graph setting under the term &quot;length bounded flows and cuts&quot;. See the following paper which shows NP-Completeness and hardness of approximation.</p>
<p>@article{baier2010length,
title={Length-bounded cuts and flows},
author={Baier, Georg and Erlebach, Thomas and Hall, Alexander and K{&quot;o}hler, Ekkehard and Kolman, Petr and Pangr{'a}c, Ond{\v{r}}ej and Schilling, Heiko and Skutella, Martin},
journal={ACM Transactions on Algorithms (TALG)},
volume={7},
number={1},
pages={1--27},
year={2010},
publisher={ACM New York, NY, USA}
}</p>

CC BY-SA 4.0
2024-08-04T03:28:12.670Z
It looks like I may have misunderstood the OPs question.  I assumed that one wants to remove the fewest edges from G such that in the residual graph the shortest s-t path has length at least k. The OP's question seems different on a second look.
Chandra Chekuri
CC BY-SA 4.0
2024-08-02T15:15:45.107Z
2024-08-02T15:15:45.107Z
Chandra Chekuri
<p>Consider the following problem.
Given a directed acyclic graph <span class="math-container">$G=(V,E)$</span> with a designated source vertex <span class="math-container">$s\in V$</span> and sink vertex <span class="math-container">$t\in V$</span>, and natural number <span class="math-container">$k$</span>.</p>
<p>Find a smallest set <span class="math-container">$E'\subseteq E$</span> of edges, such that every path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> contains at least <span class="math-container">$k$</span> edges from <span class="math-container">$E'$</span> (if such a set <span class="math-container">$E'$</span> exists)?
Or, as a decision problem, is there such a set <span class="math-container">$E'$</span> of size smaller than <span class="math-container">$m$</span>?</p>
<p>For <span class="math-container">$k=1$</span> this seems to be solvable as a min-cut/max-flow problem and hence seems polynomial. But what about <span class="math-container">$k&gt;1$</span>? Is it still polynomial, or NP Complete?</p>
<p>It seems to be a kind of variation on edge cover, covering paths instead of vertices and generalized to covering <span class="math-container">$k$</span> times, but I cannot find related problems, perhaps I am missing the right keywords.</p>
<p>I am also interested in the following generalization of the problem with edge weights. In particular, should the above problem be polynomially solvable, then is the following also (pseudo-)polynomial?</p>
<p>Given a double edge-weighted directed acyclic graph <span class="math-container">$G=(V,E,w_1,w_2)$</span> with a designated source vertex <span class="math-container">$s\in V$</span> and sink vertex <span class="math-container">$t\in V$</span> and a natural number <span class="math-container">$W$</span>. Both edge weights map to non-negative integers. (We may assume that for all <span class="math-container">$e\in E$</span>, <span class="math-container">$w_2(e)\leq w_1(e)$</span>.)</p>
<p>What is a smallest set <span class="math-container">$E'\subseteq E$</span> of edges, such that for each path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span>, the sum of <span class="math-container">$w_2$</span>-weights for the edges from <span class="math-container">$E'$</span> and <span class="math-container">$w_1$</span>-weights for the other edges amounts to a total weight of at most <span class="math-container">$W$</span> (if such a set <span class="math-container">$E'$</span> exists).</p>
<p>I.e., for every path <span class="math-container">$\pi\subseteq E$</span> from <span class="math-container">$s$</span> to <span class="math-container">$t$</span>:
<span class="math-container">$$
\sum_{e\in \pi\cap E'} w_2(e) + \sum_{e\in \pi\cap (E\backslash E')} w_1(e) \leq W
$$</span></p>
<p>Any insights, keywords, or directions to algorithmic solutions are appreciated.</p>

<time-complexity><directed-acyclic-graph><covering-problems>
Complexity of a variation of edge cover for paths
Marc Geilen
# Complexity of a variation of edge cover for paths

(Asked by: username_0 on 2024-08-02)

Consider the following problem.
Given a directed acyclic graph $G=(V,E)$ with a designated source vertex $s\in V$ and sink vertex $t\in V$, and natural number $k$.

Find a smallest set $E'\subseteq E$ of edges, such that every path from $s$ to $t$ contains at least $k$ edges from $E'$ (if such a set $E'$ exists)?
Or, as a decision problem, is there such a set $E'$ of size smaller than $m$?

For $k=1$ this seems to be solvable as a min-cut/max-flow problem and hence seems polynomial. But what about $k>1$? Is it still polynomial, or NP Complete?

It seems to be a kind of variation on edge cover, covering paths instead of vertices and generalized to covering $k$ times, but I cannot find related problems, perhaps I am missing the right keywords.

I am also interested in the following generalization of the problem with edge weights. In particular, should the above problem be polynomially solvable, then is the following also (pseudo-)polynomial?

Given a double edge-weighted directed acyclic graph $G=(V,E,w\_1,w\_2)$ with a designated source vertex $s\in V$ and sink vertex $t\in V$ and a natural number $W$. Both edge weights map to non-negative integers. (We may assume that for all $e\in E$, $w\_2(e)\leq w\_1(e)$.)

What is a smallest set $E'\subseteq E$ of edges, such that for each path from $s$ to $t$, the sum of $w\_2$-weights for the edges from $E'$ and $w\_1$-weights for the other edges amounts to a total weight of at most $W$ (if such a set $E'$ exists).

I.e., for every path $\pi\subseteq E$ from $s$ to $t$:
$$
\sum\_{e\in \pi\cap E'} w\_2(e) + \sum\_{e\in \pi\cap (E\backslash E')} w\_1(e) \leq W
$$

Any insights, keywords, or directions to algorithmic solutions are appreciated.

**Tags:** time-complexity, directed-acyclic-graph, covering-problems

---

## 1 answers

### Answer by username_1 on 2024-08-02. Score: 3

What you are asking for has been studied in the general graph setting under the term "length bounded flows and cuts". See the following paper which shows NP-Completeness and hardness of approximation.

@article{baier2010length,
title={Length-bounded cuts and flows},
author={Baier, Georg and Erlebach, Thomas and Hall, Alexander and K{"o}hler, Ekkehard and Kolman, Petr and Pangr{'a}c, Ond{\v{r}}ej and Schilling, Heiko and Skutella, Martin},
journal={ACM Transactions on Algorithms (TALG)},
volume={7},
number={1},
pages={1--27},
year={2010},
publisher={ACM New York, NY, USA}
}

> **Comments:**
> **username_1**: It looks like I may have misunderstood the OPs question.  I assumed that one wants to remove the fewest edges from G such that in the residual graph the shortest s-t path has length at least k. The OP's question seems different on a second look.  

---

