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.
