# Are there $\ell$ edge-disjoint $s$-$t$-paths such that at least $k$ of them are internally disjoint? Complexity

Given an undirected graph, two vertices $$s$$ and $$t$$, and two integers $$k$$,$$l$$ - what is the complexity of finding $$\ell$$ edge-disjoint $$s$$-$$t$$-paths such that at least $$k$$ of them are pairwise internally disjoint? Being internally disjoint means that the paths are vertex disjoint except for $$s$$ and $$t$$.

I know that deciding whether there is a certain amount of edge- or vertex disjoint paths can be solved polynomially with max flow algorithms, but this problem seems way harder. I know it is in $$\mathsf{NP}$$, however i can't figure out whether it is $$\mathsf{NP}$$-hard... or is there even some polynomial algorithm?

• Yes, the first interpretation, there should be a set of $k$ paths that are all pairwise internally disjoint. Sorry for the confusion, i now clarified it in the question. Commented Mar 14 at 9:26
• This is related to the Beineke-Harary mixed connectivity conjecture. Checking if a graph is $(l, k)$ connected is NP-complete (But even if the conjecture was true, I still says nothing since the conjecture does not claim an equivalence) Commented Mar 15 at 15:24
• Yeah, the problem is actually motivated by the Beineke-Harary Conjecture Commented Mar 16 at 12:30