Ken-ichi Kawarabayashi (Ph. D)

Professor, National Institute of Informatics
E-mail: k_keniti_at_nii.ac.jp

Research Interests:

Discrete Math and Theoretical Computer Science. More precisely, Graph theory, Combinatorics and Algorithm, in particular, Paths, Cycles, Connectivity, Factor, Coloring, Subdivisions, Minors, Surfaces, Hadwiger's Conjecture, Linkage Problem, Planar graphs, Graphs on Surfaces, and Perfect graphs and its application. Also Graph Algorithm and Combinatorial Optimization and Approximation algorithm for NP-hard problems.

Born in 1975 at Tokyo, Japan

Graduated from high school (Seiko Gakuin) in March 1994

Undergraduate Student at Keio University April 1994 - March 1998

Master Student at Keio University April 1998 - March 2000

Master's Degree 1999 from Keio University : title :Paths and Cycles in Graphs.

Doctor Student at Keio University April 2000 - March 2001

Ph.D. 2000 from Keio University : title : A Study on Hamiltonian Cycles and Related Topics.

Research Fellow of the Japan Society for the Promotion of Science, April 2000 - March 2003

Fujiwara Prize 2000 (for an outstanding graduate student in Keio University.)

Visiting Research Scholar at Vanderbilt University, April 2001- Aug 2002

Takebe Prize 2001 from Japanese Mathematics Society (for outstanding young Japanese mathematician.)

Research Fellow (Post Doc) at Princeton Univ. Aug 2002 - Aug 2003

Assistant Professor of Tohoku Univ. Aug 2003 -- March 2006.

Associate Professor of National Institute of Informatics, April 2006 -- October 2009.

Professor of National Institute of Informatics, November 2009--.

Inoue Research Award for Young Scientists 2003

Kirkman Prize 2003 from ICA (The Institute of Combinatorics and its Application.)

Research Fellowship from Sumitomo Foundation.

Visiting Professor of University of the Southern Denmark, July-October 2005.

JSPS research fellowship.

Research Fellowship from C&C Foundation

Research Fellowship for sabbatical 2007--2008 from the Japan Society for the Promotion of Science.

Young Researchers Prize from Ministry of Education, Culture, Sports, and Science and Technology , 2006 April.

Research Fellowship from Inamori Foundation, 2006.

Research Fellowship from Kayamori Foundation, 2007.

Best Paper from The 17th International Symposium on Algorithms and Computation (ISAAC 2006)

Japan IBM Science Prize in Computer Science, November, 2008.

Inoue Research Award, 2009, February.

Funai Research (special) Award,, 2011, March.

Click here for my CV.

Editorial Work:

1. Siam Journal on Discrete Mathematics, Editor.
2. Journal of Graph Theory, Editor.
3. Discrete Mathematics and Theoretical Computer Science, Editor.
4. International Journal of Combinatorics, Editor.

Program Committee:

1. SODA11, Annual ACM-SIAM Symposium on Discrete Algorithms, 2011.
2. Siam Discrete Math Conference, 2010.
3. "New Trends on Structure Graph Theory" (with B. Mohar, B. Reed and P. Seymour), to be held at the Banff International Research Station, Sept. 5--10 in 2010.
4. 35th International Symposium on Mathematical Foundations of Computer Science (MFCS 2010), August, 2010.
5. Kyoto Prize Satellite Workshop in Tokyo, November 16 - 18, 2010, Tokyo Tech Front, Tokyo Institute of Technology, Japan.
6. 3rd Pacific Workshop on Discrete Mathematics, Dec. 7--10, 2010, Tokai University Pacific Center, Hawaii.
7. Shonan meeting on Graph Algorithm and Combinatorial Optimization.
8. Second Bertinoro workshop on Graphs and Algorithm, Bertinoro, 2011, Dec.
9. SODA12, Annual ACM-SIAM Symposium on Discrete Algorithms, (I am on local program committee)2012.

Conference I plan to attend:

1. EuroComb 2011, European Conference on Combinatorics, Graph Theory and Applications, Aug 29-Sep 2, Budapest, Hungary
2. FOCS 2011 The 52nd Annual Symposium on Foundations of Computer Science (FOCS'11) at Hotel Zoso in Palm Springs, California, October 23-25.
3. Second Bertinoro workshop on Graphs and Algorithm, Bertinoro, 2011, Dec. I am one of organizers.
4. SODA12, Annual ACM-SIAM Symposium on Discrete Algorithms, 2012.
5. Graph Theory at Georgia Tech (honoring Robin Thomas' 50th Birthday), May 7-11.
6. Siam Discrete Math Conference, June 18-21, 2012 Dalhousie University, Halifax, Nova Scotia, Canada.
7. 21st Workshop on Cycles and Colourings (C&C2012)Sep 9-14, High Tatras, Slovakia.
8. 4th Pacific Workshop on Discrete Mathematics, Dec. 4--7, 2012, Tokai University Pacific Center, Hawaii.
9. Oberwolfach, Graph Theory, Jan. 13-18.
10. Shonan meeting on Parameterized Complexity May, 2013.

KK's Published Papers here

Recent Papers

1. From the plane to higher surfaces, (with C. Thomassen), to appear in J. Combin. Theory Ser. B.
2. Three-coloring triangle-free planar graphs in linear time (with Z. Dvorak and R. Thomas), to appear in ACM transaction on Algorithms.
3. Minors in 5-connected non-planar large graphs (with J. Maharry), to appear in J. Graph Theory.
4. The disjoint paths problem in quadratic time (with Y. Kobayashi and B. Reed), to appear in J. Combin. Theory Ser. B.
5. The Erdos-Posa property for clique minors in highly connected graphs (with R. Diestel and P. Wollan), to appear in J. Combin. Theory Ser. B.
6. On the excluded minor structure theorem for graphs of large treewidth (with R. Diestel, T. Muller and P. Wollan), to appear in J. Combin. Theory Ser. B.
7. A Multi-Round Generalization of the Traveling Tournament Problem and its Application to Japanese Baseball (with R. Hoshino), to appear in European Journal of Operational Research.
8. Linkless and flat embeddings in 3-space (with S. Kreutzer and B. Mohar), to appear in Discrete and Computational Geometry.
9. Connectivities for k-knitted graphs and for minimal counterexample to Hadwiger's Conjecture (with G. Yu), to appear in J. Combin. Theory Ser. B.
10. The minimum k-way cut of bounded size is fixed-parameter tractable (with M. Thorup), to appear in the 52nd Annual Symposium on Foundations of Computer Science (FOCS 2011).
11. The Graph Minor Algorithm with Parity Conditions (with B. Reed and P. Wollan), to appear in the 52nd Annual Symposium on Foundations of Computer Science (FOCS 2011).
12. An O(log n)-approximation algorithm for the disjoint paths problem in Eulerian planar graphs (with Y. Kobayashi), to appear in ACM transaction on Algorithms.
13. Scheduling Bipartite Tournaments to Minimize Total Travel Distance (with R. Hoshino), Journal of Artificial Intelligence Research.
14. Spanning closed walks and TSP in 3-connected planar graphs (with K. Ozeki), to appear in ACM-SIAM Symposium on Discrete Algorithms, (SODA'12).
15. Erd\H{o}s-P\'osa property and its algorithmic applications --- parity constraints, subset feedback set, and subset packing (with N. Kakimura and Y. Kobayashi), to appear in ACM-SIAM Symposium on Discrete Algorithms, (SODA'12).
16. List-Coloring Graphs without Subdivisions and without Immersions (with Y. Kobayashi, to appear in ACM-SIAM Symposium on Discrete Algorithms, (SODA'12).
17. A Linear Time Algorithm for the Induced Disjoint Paths Problem in Planar Graphs (with Y. Kobayashi), to appear in Journal of Computer and System Sciences.
18. Cliques in Odd-Minor-Free Graphs (with D. Wood), to appear in 18th Computing: the Australasian Theory Symposium.
19. Packing Directed Circuits through Prescribed Vertices Bounded Fractionally (with N. Kakimura), to appear in Siam. J. Discrete Math.
20. Linear min-max relation between the treewidth of $H$-minor-free graphs and its largest grid minor (with Y. Kobayashi), to appear in Symposium on Theoretical Aspects of Computer Science (STACS) 2012.
21. Edge-disjoint Odd Cycles in $4$-edge-connected Graphs (with Y. Kobayashi), to appear in Symposium on Theoretical Aspects of Computer Science (STACS) 2012.
22. Shortest-Path Queries for Complex Networks: Exploiting Low Tree-width Outside the Core, (with T. Akiba and C. Sommer) to appear in EDBT 2012 - 15th International Conference on Extending Database Technology.
23. Fixed-parameter tractability for the subset feedback set problem and the $S$-cycle packing problem (Y. Kobayashi), to appear in J. Combin. Theory Ser. B.
24. The Erd\H{o}s-Lov\'asz Tihany Conjecture and complete minors (with A. Pedersen and B.Toft), to appear in J. Combinatorics.
25. Packing Cycles through Prescribed Vertices under Modularity Constraints (with N. Kakimura), to appear in Advance in Applied Math.
26. The Linear Distance Traveling Tournament Problem (with R. Hoshino), to appear in the Twenty-Sixth AAAI Conference on Artificial Intelligence (AAAI-12).

News:

1. I am on the Local Committee of SODA12, Annual ACM-SIAM Symposium on Discrete Algorithms, 2012.
2. Funai Research (special) Award,, 2011, March.
3. Lovasz wins Kyoto prize 2010!
4. SODA'12 will take place in Kyoto, Japan!
5. As of Nov. 1, 2009, I am Professor of National Institute of Informatics.
6. Inoue Research Award, 2009, February.
7. Japan IBM Science Prize in Computer Science, November, 2008.
8. I am on the Program Committee of SODA11, Annual ACM-SIAM Symposium on Discrete Algorithms, 2011.
9. I am on the Program Committee of Siam Discrete Math Conference, 2010.
10. I am co-organizing a workshop "New Trends on Structure Graph Theory" (with B. Mohar, B. Reed and P. Seymour), to be held at the Banff International Research Station, Sept. 5--10 in 2010.
11. I am co-organizing a workshop "Bertinoro workshop on Graphs and Algorithm", Bertinoro, 2009, Dec.
12. I am on the Program Committee of the 35th International Symposium on Mathematical Foundations of Computer Science (MFCS 2010), August, 2010.
13. Young Researchers Prize from Ministry of Education, Culture, Sports, and Science and Technology (Monka Syo) , 2006 April.
14. Best Paper from The 17th International Symposium on Algorithms and Computation (ISAAC 2006).
15. Winter School for Graphs and Algorithms. This is a part of project RIMS International Project Research 2008 Discrete Structures and Algorithms. I am an organizer. Carsten Thomassen, Bruce Reed, Bojan Mohar, Robin Thomas, Bjarne Toft, R. Ravi, S. Oum, M. Halldorsson, and Mikkel Thorup have agreed to give lectures.