Technical Report CS0601

Title: ON DISJOINT PATHS PROBLEM$ IN GRAPHS (Extended Version of TR#585)
Authors: E. Korach, N. SoleI and A. Tal
Abstract: The vertex disjoint connecting paths problem is defined as follows: Given an undirected graph G=(V,E) and k pairs of vertices of V - (source,sink), find whether G contains k internally vertex disjoint paths, one connecting each pair. Karp has shown that this problem is NP-complete (even when all sources and sinks are distinct), and Robertson and Seymour solved this problem where the number of paths is constant. For graphs with bounded tree-width we solve in polynomial time a version of this problem: k is a part of the input and only the number of sinks in a vertex is bounded. We also solve some more problems related to the disjoint connecting paths problem on graphs with bounded tree-width.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1990
To the main CS technical reports page

Computer science department, Technion