Algorithm Aspect of Graph Minor Theory

概要

論文の詳細を見る
We shall survey recent progress on algorithm aspect of graph minor theory. One of the main results on Graph Minor Project by Robertson and Seymour is the following. Given a graph G and p pairs of vertices of G for fixed p, there is a polynomial time (actually O(n^3) algorithm to decide if there are p mutually disjoint paths of G linking the pair. If p is part of the input of the problem, then this is one of Karp's NP-complete problems, and it remains NP-complete even for planar graphs. We shall first sketch the algorithm, and explain why the correctness needs * 500 pages to prove. Then we shall focus on applications of this result. Topics include tree-width for planar graphs, 2-path problem (2-linked graph), the odd disjoint cycles, the parity paths problems, Kuratowski's theorem for general surface, nearly-k-bipartite graph problem and algorithm aspect of Hadwiger's conjecture.
社団法人電子情報通信学会の論文
2004-10-08