The Edge-Disjoint Paths Problem is NP-Complete for Partial k-Trees.

Xiao Zhou, Takao Nishizeki

Browse the full ISAAC paper archive.