# Complexity of a variation of edge cover for paths

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.