The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable

被引：32

作者：

Cygan, Marek ^{[1
]}

Marx, Daniel ^{[2
]}

Pilipczuk, Marcin ^{[1
]}

Pilipczuk, Michal ^{[3
]}

机构：

[1] Univ Warsaw, Inst Informat, PL-00325 Warsaw, Poland

[2] Hungarian Acad Sci, Insti Comp Sci & Control, Budapest, Hungary

[3] Hungarian Acad Sci, Insti Comp Sci & Control, Budapest, Hungary

来源：

2013 IEEE 54TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS) | 2013年

关键词：

disjoint paths; fixed parameter tractability; planar graphs; directed graphs; GRAPH MINORS; WIDTH;

D O I：

10.1109/FOCS.2013.29

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Given a graph G and k pairs of vertices (s(1), t(1)),..., (s(k), t(k)), the k-Vertex-Disjoint Paths problem asks for pairwise vertex- disjoint paths P-1,..., P-k such that Pi goes from s(i) to t(i). Schrijver [SICOMP'94] proved that the k-Vertex- Disjoint Paths problem on planar directed graphs can be solved in time n(O(k)). We give an algorithm with running time 2(2O(k2)) . n(O(1)) for the problem, that is, we show the fixed-parameter tractability of the problem.

引用

页码：197 / 206

页数：10

共 29 条

[1]

Adler I, 2011, LECT NOTES COMPUT SC, V6755, P110, DOI 10.1007/978-3-642-22006-7_10

[2] The DAG-width of directed graphs [J].