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?

  • $\begingroup$ 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. $\endgroup$
    – tgnome
    Commented Mar 14 at 9:26
  • 1
    $\begingroup$ 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) $\endgroup$
    – caduk
    Commented Mar 15 at 15:24
  • $\begingroup$ Yeah, the problem is actually motivated by the Beineke-Harary Conjecture $\endgroup$
    – tgnome
    Commented Mar 16 at 12:30


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.