著者

KAWARABAYASHI Ken-ichi

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション

巻号頁・発行日

vol.104, no.339, 2004-10-08

---

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.