Curriculum Vitae
Personal Dates
Name:
Birthday/-Place:
Citizenship:
Married in 2003.

Ken-ichi Kawarabayashi
May 1975 in Tokyo, Japan
Japan

Current Position and Address
Professor & Deputy Director of General
National Institute of Informatics
2-1-2 Hitotsubashi, Chiyoda-ku
Tokyo 101-8430, Japan
Education
April 2000 - March 2001,

April 1998 - March 2000,

April 1994 - March 1998,

Ph. D. in Mathematics, Keio University,
Research Area: Combinatorics and Graph Theory.
Thesis: A Study on Hamiltonian Cycles and Related topics
Adviser: Professor K. Ota.
Master Course in Mathematics, Keio University.
Thesis: Paths and Cycles in Graphs.
Adviser: Professor K. Ota.
B.S. in Mathematics, Keio University.
Thesis: Circuits through independent edges.
Adviser: Professor H. Enomoto and Professor K. Ota.

Academic Degrees
B.Sci. 1997. (Mathematics),
M.Sci. 1999. (Mathematics),
Dr.Sci. 2000. (Mathematics),

Keio University (1998, March)
Keio University (2000, March)
Keio University (2001, March)

Employment
April 2000 - March 2003
April 2001 - August 2002
September 2002 - July 2003
August 2003 - March 2006
April 2006 – Oct. 2009
Nov. 2009 – present.
April 2019 – March 2021t.

Research Fellow of the Japan Society for the Promotion of Science
Visiting Scholar of Vanderbilt University
Post Doctor Fellow. Adviser: Professor P. Seymour.
Assistant Professor of Tohoku University.
Associate Professor of National Institute of Informatics (NII)
Professor of National Institute of Informatics (NII)
Deputy Director General of National Institute of Informatics (NII)Award
1. Takebe Prize (for an outstanding young Japanese mathematician.) in 2001.
2. Inoue Research Award for Young Scientists 2003
1

3. Kirkman Prize (from the Institute of Combinatorics and its Applications), in 2003.
4. Young Researchers prize from Japan Society for the Promotion of Science in 2006.
5. Best Paper Award of 17th International Symposium on Algorithms and Computation (ISAAC
2006).
6. IBM Japan Science prize in Computer Science, 2008.
7. Inoue Research Award, 2009, February.
8. Funai Research (special) Award, 2011, March.
9. Best Paper Award from SODA’13.
10. JSPS prize, 2013.
11. Japanese Academy Medal, 2013.
12. Mathematics Annual Spring Prize from Japan Mathematics Society, 2015, March.
13. Associate Member of Science Council of Japan (2017–).
14. Fulkerson prize 2021 (jointly with Mikkel Thorup)
Program Officer
1. Research Adviser, ACT-I, Future of Informatics, Japan Science and Technology Agency(JST)(2016–)
2. Research Supervisor(Program Director), ACT-X, Frontier of mathematics and information
science, Japan Science and Technology Agency(JST) (2019–)
3. Adviser, A-Step program, Japan Science and Technology Agency(JST) (2020–)
4. Member of Research Center for Science Systems(Program Officer of JSPS), JSPS (2018–)
Chair of Committee
1. General co-chair, ACM-SIAM Symposium on Discrete Algorithms, (SODA’12).
2. Japan Conference on Combinatorics and its Applications 2014, General Chair.
3. General chair, ISAAC’15, Nagoya.
4. Japan Conference on Combinatorics and its Applications 2016, General Chair.
5. Academic chair of Shonan Meeting (2018–)
6. Japan Conference on Combinatorics and its Applications 2018, General Chair.
7. Research Supervisor(Program Director), ACT-X, Frontier of mathematics and information
science, Japan Science and Technology Agency(JST) (2019–)
Organization Committee21. Organizer, International conference on Graph Theory and Combinatorics, Japan, June 2005.
2. Organizer, Graph Minor Minisymposium, Siam Discrete Math Conference June 2006.
3. Organizer, Graph Minor and Structure Graph Theory Minisymposium, CANADAM 2007.
4. Organizer, International conference on Graph Theory and Combinatorics, Japan, June 2007.
5. Organizer, Graph Minors. Banff. BIRS 2008, October.
6. Organizer, Winter School on Graphs and Algorithm, RIMS, Kyoto Univ. 2008, Dec.
7. Organizer, Bertinoro workshop on Graphs and Algorithm, Bertinoro, 2009, Dec.
8. Organizer, New Trends in Structure Graph Theory, Banff. BIRS, 2010, September.
9. Organizer, Kyoto Prize Satellite Workshop in Tokyo, November, 2010, Tokyo.
10. Organizer, 3rd Pacific Workshop on Discrete Mathematics, Hawai, December, 2010.
11. Organizer, Shonan meeting on Graph Algorithm and Combinatorial Optimization, Shonan,
Feb., 2011.
12. Organizer, Second Bertinoro workshop on Graphs and Algorithm, Bertinoro, 2011, Dec.
13. Organizing Committee, ISAAC 2011, Yokohama, Dec.
Programm Committee and Are Chairs
PC chair: The Shonan meeting (2018–)
Tier 1 Conferences: SODA’11, VLDB’16, SODA’17, STOC’17, FOCS’18, IJCAI’20(Area
Chair), FOCS’20, IJCAI’21(Area Chair), SODA’22
Other conferences: Siam Discrete Math Conference 2010, MFCS’10, ESA’13, TAMC’13,
IPEC’14, APPROX’14, WALDAN’15, SISP’16, ICALP’16, IJCAI’18(SPC), ALNEX’19, ICALP’22
Editor of Journals
1. Algorithmica, Editor (2013–)
2. Journal of Graph Algorithm and Applications, Editor (2014–2018)
3. Siam Journal of Discrete Mathematics, Editor (2010–2016).
4. Journal of Graph Theory, Editor (2008–).
5. Discrete Mathematics and Theoretical Computer Science, Editor (2009–).
6. Graphs and Combinatorics, Editor (2014–).
7. TheoretiCS, Editor (2021–)

3

Grant1999 - 2002
2003 - 2006
2004 - 2006
2005 - 2007
2006 - 2008
2007–20092008
2009 - 2016
2012–2018
2014–2018
2015–2020
2018–2023
2018–2023
2019–2023
2021–2025

The Japan Society for the Promotion of Science for Young Scientists.
The Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research
Sumitomo Foundation
C & C Foundation
Inamori Foundation
Kayamori Foundation
Inoue Foundation
The Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research
JST ERATO Kawarabayashi Large Graph Project
IMPACT Yamamoto Project
NEDO Iot project
The Japan Society for the Promotion of Science, Kiban S.
NEDO AI project
SIP Material information science
The Japan Society for the Promotion of Science, Gakuhen A.

Collaboration with Industry
NTT, Hitachi, NEC, Yahoo Japan, IBM
Research Interests
Discrete Mathematics and Theoretical Computer Science. Graph Theory, Graph Algorithm, Experimental and Scalable Algorithm, Graph Database, Combinatorial Optimization, Machine Learning,
Quantum Computing.
List of publications
1. Top Journals in Math(Mostly in Discrete Math) and Computer Science.
2. Respectful Journals in Math(Discrete Math) and Computer Science.
3. General Journals(Outside Math and CS)
4. Tier 1 Conference Proceedings in CS.
5. Respectful Conference Proceedings in CS.
6. Other papers.
1. Top Journals in Math(Discrete Math) and Computer Science
1. One or two disjoint circuits cover independent edges; Lovász-Woodall Conjecture, J. Combin.
Theory Ser. B 84 (2002) 1–44.
2. Contractible edges and triangles in k-connected graphs, J. Combin. Theory Ser. B 85 (2002)
207–221.
3. Subgraphs of Graphs on Surfaces with High Representativity, (with A. Nakamoto and K. Ota),
J. Combin. Theory Ser. B. 89 (2003) 207–229.
44. Cycles through prescribed vertex set in n-connected graphs, J. Combin. Theory Ser. B. 90(2004) 315–323.
5. Orientable and non-orientable genera for some complete tripartite graphs, (with C. Stephen
and X. Zha), Siam J. Discrete Math. 18 (2005) 479-487.
6. Any 7-chromatic graph has a K7 -minor or a K4,4 -minor, (with B. Toft), Combinatorica 25(2005) 327–353.
7. Improvement of the theorem of Duchet and Meyniel on Hadwiger’s Conjecture (with B. Toft),
J. Combinatorial Theory Ser. B. 96 (2005), 152–167.
8. Non-zero disjoint cycles in highly connected graphs (with P. Wollan), J. Combin. Theory Ser.
B. 96 296–301.
9. A pair of forbidden subgraphs and perfect matchings (with S. Fujita, C. Luchessi, K. Ota, M.
Plummer and A. Saito), J. Combin. Theory Ser. B. 96 315–324.
10. 2-connected spanning subgraphs with low maximum degree in locally planar graphs, (with M.
Ellingham), J. Combin. Theory Ser. B. 97 (2007) 401–412.
11. On the connectivity of minimum and minimal counterexamples to Hadwiger’s Conjecture, J.
Combin. Theory Ser. B. 97 (2007), 144–150.
12. A relaxed version of Hadwiger’s conjecture for list-coloring (with B. Mohar), J. Combin. Theory
Ser. B. 97 (2007), 647–651.
13. Some remarks on the odd Hadwiger’s conjecture, (with Z. Song), Combinatorica 27 (2007),
429–438.
14. Non-separating cycles consisting of contractible edges in k-connected graphs, (with Y. Egawa
and K. Inoue), Siam J. Discrete Math, 21 (2007), 1061–1070.
15. On the matching extendability of graphs in surfaces, (with R.E.L. Aldred and M.D. Plummer),J. Combin. Theory Ser. B. 98 (2008), 105–115.
16. Connectivity keeping edges in graphs of large minimum degree (with S. Fujita), J. Combin.
Theory Ser. B, 98 (2008), 805–811.
17. A weaker version of Lovász’ path removable conjecture (with O. Lee, B. Reed and P. Wollan),
J. Combin. Theory Ser. B., 98, (2008) 972–979.
18. Locally planar graphs are 5-choosable (with M. DeVos and B. Mohar), J. Combin. Theory Ser.
B, 98, (2008) 1215–1232.
19. K6 -minor in triangulations in the Klein bottle (with R. Mukae and A. Nakamoto), Siam. J.
Discrete Math, 23 (2009), 96–108.
20. Removable paths in non-bipartite graphs (with O. Lee and B. Reed), J. Combin. Theory Ser.
B, 99 (2009), 30–38.
21. On the number of 4-contractible edges in 4-connected graphs (with K. Ando, Y. Egawa and
M. Krisell), J. Combin. Theory Ser. B, 99 (2009), 97–109.
522. N -flips in even triangulations on surfaces (with A. Nakamoto and Y. Suzuki), J. Combin.
Theory Ser. B, 99 (2009), 229–246.
23. Linear Connectivity forces large complete bipartite minors (with T. Bohme, J. Maharry and
B. Mohar), J. Combin. Theory Ser. B, 99 (2009), 557–582.
24. 6-critical graphs on the Klein bottle (with D. Kral, J. Kyncl, and B. Lidicky), Siam J. Discrete
Math, 23 (2009), 372–383.
25. Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner’s Contraction(with E. Demaine and M. Hajiaghayi), Algorithmica, 54 (2009), 142–180.
26. Decomposing planar graphs of girth 5 into a forest and an independent set, (with C. Thomassen),
J. Combin. Theory Ser. B 99 (2009), 674–684.
27. Note on coloring graphs without odd-Kk -minors, J. Combin. Theory Ser. B 99 (2009), 738–
741.
28. Highly parity linked graphs, (with B. Reed), Combinatorica 29 (2009), 215–225.
29. Star-coloring and Acyclic-coloring of locally planar graphs (with B. Mohar), Siam. J. Discrete
Math. 24 (2010), 56–71.
30. A simple algorithm for 4-coloring 3-colorable planar graphs (with K. Ozeki), Theoretical Computer Science, 411 (2010), 2619–2622.
31. Non-separating even cycles in highly connected graphs (with S. Fujita), Combinatorica 30,(2010), 565–580.
32. Algorithms for finding an induced cycle in planar graphs (with Y. Kobayashi), Combinatorica,
30, (2010), 715–734.
33. Non-separating subgraphs after deleting many disjoint paths (with K. Ozeki), J. Combin.
Theory Ser. B 101, (2011), 54–59.
34. Matching extension versus representativity in 5-connected embedded graphs (with S. Negami,
M. Plummer and Y. Suzuki), J. Combin. Theory Ser. B 101 (2011), 206–213.
35. Packing cycles through prescribed vertex set (with N. Kakimura and D. Marx), J. Combin.
Theory Ser. B 101, (2011), 54–59.
36. A Multi-Round Generalization of the Traveling Tournament Problem and its Application to
Japanese Baseball (with R. Hoshino), European Journal of Operational Research, 215 (2011),
481–497.
37. Scheduling Bipartite Tournaments to Minimize Total Travel Distance (with R. Hoshino), Journal of Artificial Intelligence Research, 42 (2011), 91–124.
38. Three-coloring triangle-free planar graphs in linear time (with Z. Dvorak and R. Thomas),
ACM transaction on Algorithms 7 No. 41 (2011).
39. Improved Algorithm for the Half-Disjoint Paths Problem (with Y. Kobayashi), Siam J. Discrete
Math, 25 (2011), 1322–1330.
6

40. A Linear Time Algorithm for the Induced Disjoint Paths Problem in Planar Graphs (with Y.
Kobayashi), Journal of Computer and System Sciences 78, (2012), 670–680.
41. The disjoint paths problem in quadratic time (with Y. Kobayashi and B. Reed), J. Combin.
Theory Ser. B 102 (2012), 424–435.
42. The Erdos-Posa property for clique minors in highly connected graphs (with R. Diestel and P.
Wollan), J. Combin. Theory Ser. B, 102 (2012), 454–469.
43. Linkless and flat embeddings in 3-space (with S. Kreutzer and B. Mohar), Discrete and Computational Geometry 47, (2012), 731–755.
44. From the plane to higher surfaces, (with C. Thomassen), J. Combin. Theory Ser. B 102(2012), 852–868.
45. Fixed-parameter tractability for the subset feedback set problem and the S-cycle packing problem (with Y. Kobayashi), J. Combin. Theory Ser. B 102 (2012), 1020–1034.
46. Packing Cycles through Prescribed Vertices under Modularity Constraints (with N. Kakimura),
Advance in Applied Math 49 (2012), 97–110.
47. Generating Approximate Solutions to the Traveling Tournament Problem using a Linear Distance Relaxation (with R. Hoshino), Journal of Artificial Intelligence Research 45 257-286,(2012).
48. On the excluded minor structure theorem for graphs of large treewidth (with R. Diestel, T.
Muller and P. Wollan), J. Combin. Theory Ser. B, 102 1189-1210 (2012).
49. Packing Directed Circuits through Prescribed Vertices Bounded Fractionally (with N. Kakimura),Siam. J. Discrete Math 26, 1121–1133, (2012).
50. An O(log n)-approximation algorithm for the disjoint paths problem in Eulerian planar graphs(with Y. Kobayashi), ACM transaction on Algorithms 9 No. 16.
51. A simpler proof for the two disjoint odd cycles theorem (with K. Ozeki), J. Combin. Theory,
Ser. B 103, 313–319 (2013).
52. Connectivities for k-knitted graphs and for minimal counterexamples to Hadwiger’s Conjecture(with G. Yu), J. Combin. Theory, Ser. B, 103 320–326 (2013).
53. Graph Theory and Sports Scheduling (with R. Hoshino), Notices of the American MathematicalSociety 60, 6 (2013) 726-731.
54. Half-Integral Packing of Odd Cycles through Prescribed Vertices (with N. Kakimura), Combinatorica 33 549–572 (2013).
55. An Approximation Algorithm for the Bipartite Traveling Tournament Problem (with R. Hoshino),
Mathematics of Operation Research, 38 720-728 (2013).
56. Spanning closed walks and TSP in 3-connected planar graphs (with K. Ozeki), J. Combin.
Theory Ser. B 109 1-33 (2014).

7

57. Removable paths and cycles with parity constraints (with O. Lee and B. Reed), J. Combin.
Theory Ser. B 106 115-133 (2014).
58. Minimum degree conditions for vertex-disjoint even cycles in large graphs (with S. Chiba, S.
Fujita, T. Sakuma), Advance in Applied Mathematics, 54 105–120 (2014).
59. 4-connected projective-planar graphs are hamiltonian-connected (with K. Ozeki), J. Combin.
Theory Ser. B, 112, 39–66, (2015).
60. Fixed-parameter tractability for subset feedback set problems with parity constraints (with N.
Kakimura) Theor. Comput. Sci. 576 61-76 (2015).
61. Subdivision of K5 containing no K23 (with J. Ma and X. Yu), J. Combin. Theory Ser. B, 113(2015), 18–67.
62. The edge disjoint paths problem in Eulerian graphs and 4-edge-connected graphs (with Y.
Kobayashi), Combinatorica, 35 (2015), 477–495.
63. The edge density of critical digraphs (with R. Hoshino), Combinatorica, 35 (2015), 619–631.
64. Edge-colouring seven-regular planar graphs (with Maria Chudnovsky, Katherine Edwards, Paul
Seymour), J. Combin. Theory Ser. B, 115 (2015), 276–302.
65. Packing T-joins in six-regular planar graphs (with Z. Dvroak and D. Kral), J. Combin. Theory
Ser. B, 116 (2016), 287–375.
66. Non separating subgraphs in highly connected graphs (with S. Fujita), J. Combin. Theory Ser.
B, 117 (2016), 1–21.
67. 5-connected toroidal graphs are hamiltonian-connected (with K. Ozeki), SIAM J. Discrete
Math., 30 (2016), 112–140.
68. Edge-disjoint Odd Cycles in 4-edge-connected Graphs (with Y. Kobayashi), J. Combin. Theory
Ser. B, 119 (2016), 12–27.
69. Coloring immersion-free graphs (with N. Kakimura), J. Combin. Theory Ser. B, 121, (2016),
284-307.
70. An Improved Approximation Algorithm for the Edge-Disjoint Paths Problem with Congestion
Two (with Y. Kobayashi), ACM transaction on Algorithms, 13 No. 5, (2016).
71. Coloring 3-colorable graphs with less than n1/5 colors (with M. Thorup), J. ACM, 64, 2017,
Article No. 4.
72. Packing Edge-disjoint S-cycles with Parity Constraints in 4-edge-connected Graphs (with N.
Kakimura and Y. Kobayashi), SIAM Journal on Discrete Mathematics 31, 766–782 (2017).
73. A new proof for the weak structure theorem (with P. Wollan and R. Thomas), J. Combin.
Theory Ser. B, 129 (2018), 204–238.
74. K6 minors in large 6-connected graphs (with S. Norine, R. Thomas and P. Wollan), J. Combin.
Theory Ser. B, 129 (2018), 158–203.
8

75. Packing edge-disjoint complete immersions in 4-edge-connected graphs (with N. Kakimura), J.
Combin. Theory Ser. B, 131 (2018), 138–169.
76. ClassiNet – Predicting Missing Features for Short-Text Classification (with D. Bollegala, M.
Alsuhaibani and T. Maehara), ACM Transactions on Knowledge Discovery from Data (TKDD),
Volume 12 Issue 5, July 2018, Article No.55.
77. All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs(with Y. Kobayashi), SIAM J. Comp. 47, (2018) 1483—1504.
78. Extreme-Value-Theoretic Estimation of Local Intrinsic Dimensionality(with Oussama Chelly,
Laurent Amsaleg, Teddy Furon, Stéphane Girard, Michael Houle, Michael Nett), Data Mining
and Knowledge Discovery(DAMI), 32 1768–1805, 2018.
79. Deterministic edge-connectivity of a simple graph in near-linear time (with M. Thorup), J.
ACM, 66, Article No. 4, 2019.
80. K6 minors in 6-connected graphs of bounded tree-width (with S. Norine, R. Thomas and P.
Wollan), J. Combin. Theory Ser. B, 136 1–32, (2019).
81. Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid
minor (with Y. Kobayashi), J. Combin. Theory Ser. B 141, 145–160, (2020).
82. Model-Checking on Ordered Structures (with K. Eickmeyer, J. van den Heuvel, S. Kreutzr, P.
Ossona de Mendez, M. Pilipczuk, D. Quiroz, R. Rabinovich, and S. Siebertz) Transactions on
Computational Logic 21 28 (2020).
83. Minimum Violation Vertex Maps and Their Applications to Cut Problems (with C Xu), SIAM
Journal on Discrete Mathematics 34 (2020) (4), 2183–2207.
84. Optimal Distributed Covering Algorithms (with G. Even, R. Ben Basat and G. Schwartzman),Distributed computing, 2021, 1–11.
85. Additive non-approximability of chromatic number in proper minor-closed classes (with Z.
Dvorak), to appear in J. Combin. Theory Ser. B.
86. Rooted topological minors on four vertices (with K. Hayashi), to appear in J. Combin. Theory
Ser. B.
87. A Polynomial Excluded-Minor Approximation of Treedepth (with Ben Rossman), to appear in
J. European Math. Society.
88. K3,k -minors in large 7-connected graphs, (with T. Bohme, J. Maharry and B. Mohar), toappear in J. Combin. Theory Ser. B.
2. Respectful Journals in Math(Discrete Math) and Computer Science
1. Hamiltonian Cycles in Factor-Critical Graphs, (with A. Saito and K. Ota), Discrete Math 240(2001) 71–82.
2. Path Factor in Claw-Free Graphs, (with K. Ando, Y. Egawa, A. Kaneko, H. Matsuda), Discrete
Math 243 (2002) 195–200.
9

3. K4− -factor in graphs, J. Graph Theory 39 (2002) 111–128.
4. Path-factor in cubic graphs, (with H. Matsuda, Y. Oda and K. Ota), J. Graph Theory 39(2002) 188–193.
5. Graph partition into paths containing specified vertices, Discrete Mathematics 248 (2002)
271–278.
6. Hamiltonian Cycles in n-extendable graphs, (with A. Saito and K. Ota), J. Graph Theory 40(2002) 75–82.
7. On separable self-complementary graphs (with A. Nakamoto, Y. Oda, K. Ota, S. Tazawa andM. Watanabe), Discrete Math. 257 (2002) 165–168.
8. On a hamiltonian cycle in which specified vertices are not isolated, (with A. Kaneko, K. Ota,
and K. Yoshimoto), Discrete Math. 258 (2002) 85–91.
9. 2-connected 7-coverings in 3-connected graph on surfaces, (with A. Nakamoto and K. Ota), J.
Graph Theory 43 (2003) 26–36.
10. Some forbidden subgraph conditions for a graph to have a k-contractible edge, (with K. Ando),
Discrete Math 267 (2003) 3–11.
11. Cycles Having the Same Modularity, (with K. Ando, M. Hagita, A. Kaneko, M. Kano, and A.
Saito), Discrete Math. 265 (2003) 23–30.
12. On two equimatchable graph classes (with M. Plummer and A. Saito), Discrete Math 266(2003) 263–274.
13. Covering vertices of a graph by k vertex disjoint cycles, (with Y. Egawa, M. Hagita and H.
Wang), Discrete Math 270 (2003) 114–124.
14. Vertices of degree 6 in 6-contraction-critical graphs, (with K. Ando and A. Kaneko), Discrete
Math 273 (2003) 55–69.
15. K-Linked Graphs with Girth Condition, J. Graph Theory 45 (2004) 48–50.
16. Vertex-Disjoint Cycles Containing Specified Vertices in a Bipartite Graph, (with H. Enomoto,G. Chen, D. Lou, K. Ota, and A. Saito.) J. Graph Theory.46 (2004) 145–166.
17. A theorem on paths in locally planar triangulations, European J. Combin. 25 (2004), 781–784.
18. Rooted minor problems in highly connected graphs, Discrete Math. 287 (2004), 121–123.
19. Detecting Even Holes, (with M. Chudnovsky and P. Seymour), J. Graph Theory, 48 (2005)
85-111.
20. Nonseparating paths with two prescribed endvertices in 4-connected graphs, (with O. Lee and
X. Yu), Annals of Combinatorics 9 (2005) 47-56.
21. On Structure of k-connected graphs without Kk -minor, (with R. Luo, J. Niu and C.Q. Zhang),
Europ. J. Combinatorics 26 (2005) 293-308.
1022. Graph Minors and Linkage Problem I, (with G. Chen, R. Gould, F. Pfender and B. Wei), J.
Graph Theory 49 (2005) 75-91.
23. Acute triangles in 4-connected maximal plane graphs, (with A. Nakamoto, Y. Oda and M.
Watanabe), Discrete Math 292 (2005) 95–106.
24. Some properties of 5-contraction critical graphs, (with K. Ando and A. Kaneko), Graph andCombin. 21 (2005) 27–37.
25. Existence of two long cycles (with Y. Egawa, S. Fujita and H. Wang), Discrete Math. 205(2005), 154–169.
26. Dominating number in cubic graphs with large girth (with M. Plummer and A. Saito), J. Graph
Theory 52 (2006) 1–6.
27. On sufficient degree conditions for a graph to be k-linked, (with A. Kostochka and G. Yu).
Combinatorics, Probability and Computing 15 (2006), 685–694.
28. Chords of longest circuits in locally planar graphs (with J. Niu and C. Q. Zhang), Europ. J.
Combinatorics 28 (2007) 315–321.
29. The Erdos-Posa property for orientable surface (with A. Nakamoto), Discrete Math 307 (2007),
764–768.
30. Some recent progress and applications on Graph Minor Theory, A survey (with B. Mohar),Graph and Combinatorics 23 (2007), 1–46.
31. Rooted minor problems in graphs (with L. Jorgensen), J. Graph Theory 55 (2007) 191–207.
32. Independence number and clique minors (with Z. Song), J. Graph Theory 56 (2007), 219–226.
33. Contractible edges in minimally k-connected graphs, (with K. Ando and A. Kaneko), Discrete
Math 308 (2008), 597–602.
34. Fractional coloring and the odd Hadwiger’s conjecture (with B. Reed), Europ. J. Combinatorics
29 (2008), 411–417.
35. Contractible elements in k-connected graphs not containing some specified graphs, (with S.
Fujita) J. Graph Theory 58 (2008), 97–109.
36. A weakening of the odd Hadwiger’s conjecture, Combin. Prob. Computing, 17 (2008), 815–
821.
37. Long cycles without hamiltonian paths (with K. Ozeki and T. Yamashita), Discrete Math.,
308, (2008), 5899–5906.
38. Note on non-separating and removable cycles in highly connected graphs (with S. Fujita),
Discrete Applied Math, 159 (2009), 398–399.
39. List-coloring graphs without K4,k -minors, Discrete Applied Math, 157, (2009), 659–662.
40. Bounding the size of equimatchable graphs of fixed genus (with M. Plummer), Graphs andCombinatorics 25 (2009), 91–99.
1141. Dominating sets in triangulations on surfaces (with T. Honjo and A. Nakamoto), J. Graph
Theory, 63 (2010), 17–30.
42. Double-critical graphs and complete minors (with A. S. Pedersen and B. Toft), Electric J.
Combinatorics, R87, (2010).
43. Contractible small subgraphs in k-connected graphs (with S. Fujita), Graphs and Combinatorics
26 (2010), 499–511.
44. A note on traversing specified vertices in graphs embedded with large representativity (withM. Plummer), Discrete Math (Carsten Thomassen’s 60) 310 (2010), 2655-2661.
45. Contractible triples in highly connected graphs (with S. Fujita), Annals of Combinatorics 14(2010), 457–465.
46. Immersing small complete graphs (with M. DeVos, B. Mohar and H. Okamura), Ars Mathematica Contemporanea 3 (2010) 139–146.
47. Toughness of Ka,t -minor-free graphs (with G. Chen, Y. Egawa, B. Mohar, K. Ota), Electric J.
Combinatorics, P148.
48. 2- and 3-factors of graphs on surfaces (with K. Ozeki), J. Graph Theory, 67 (2011), 306–315.
49. The Erdős-Lovász Tihany Conjecture and complete minors (with A. Pedersen and B.Toft), J.
Combinatorics 2 (2011), 572–592.
50. Minimally contraction-critical 6-connected graphs (with K. Ando and S. Fujita), Discrete Mathematics 302 (2012), 671–679.
51. Minors in 5-connected non-planar large graphs (with J. Maharry), J. Graph Theory 78 (2012),
128–141.
52. Sub-exponential Graph Coloring Algorithm for Stencil-based Jacobian Computations (withMichael Lülfesmann), Journal of Computational Science 11 1-11 (2014).
53. A connected subgraph maintaining high connectivity (with S. Fujita), Eur. J. Comb. 35,
245-255 (2014).
54. Reply trees in Twitter: data analysis and branching process models (with R. Nishi, T. Takaguchi, K. Oka, M. Maehara, M. Toyoda and N. Masuda). Social Netw. Analys. Mining 6(1):
26:1-26:13 (2016)
55. Matching extension missing vertices and edges in triangulations of surfaces (with M. Plummer
and K. Ozeki), Journal of Graph Theory, 85 249–257, (2017).
56. Triangle-free graphs of tree-width t are d(t + 3)/2e-colorable (with Z. Dvorak), Europ. J.
Combin. 66, 95–100, (2017).
57. Existence of outsiders as a characteristic of online communication networks (with T. Takaguchi,
T. Maehara, and M. Toyoda), Network Science 6, 431–447 (2018).
3. General Journals(Outside Math and CS), Science, Science Adv., PRE. PLOS,
Scientific reports etc
121. Uncertain behaviours of integrated circuits improve computational performance (Chihiro Yoshimura,
Masanao Yamaoka, Masato Hayashi, Takuya Okuyama, Hidetaka Aoki, and Hiroyuki Mizuno),
Scientific reports 2015; 5: 16213.
2. A coherent Ising machine for 2000-node MAX-CUT problems (with Takahiro Inagaki, Yoshitaka Haribara, Koji Igarashi, Tomohiro Sonobe, Shuhei Tamate, Toshimori Honjo, Alireza
Marandi, Peter L. McMachon, Takeshi Umeki, Koji Enbutsu, Osamu Tadanaga, Hirokazu
Takenouchi, Kazuyuki Aihara, Kyo Inoue, Shoko Utsunomiya and Hiroki Takesue), Science.
DOI: 10.1126/science.aah4243.
3. Iterative Approach for the Global Estimation of Sentence Similarity (with T. Kajiwara, D. Bollegala, Y. Yoshida), PLOS ONE 12(9): e0180885. https://doi.org/10.1371/journal.pone.0180885.

4. Learning Linear Transformations between Counting-based and Prediction-based Word Embeddings (with D. Bollegala and K. Hayashi), PLoS ONE 12(9): e0184544. https://doi.org/10.1371/journal.po
5. Coherent Ising Machines – Optical Neural Networks operating at the Quantum Limit (withYoshihisa Yamamoto, Kazuyuki Aihara, Timothee Leleu, Satoshi Kako, Martin Fejer, Kyo
Inoue, and Hiroki Takesue), npj Quantum Information 3 (1), 49.
6. Jointly Learning Word Embeddings Using a Corpus and a Knowledge Base (with D. Bollegala,
M. Alsuhaibani and T. Maehara), PLoS ONE 13(3): e0193094.
7. Experimental investigation of performance differences between Coherent Ising Machines anda quantum annealer (with Ryan Hamerly, Takahiro Inagaki, Peter L McMahon, Davide Venturelli, Alireza Marandi, Tatsuhiro Onodera, Edwin Ng, Carsten Langrock, Kensuke Inaba,Toshimori Honjo, Koji Enbutsu, Takeshi Umeki, Ryoichi Kasahara, Shoko Utsunomiya, Satoshi
Kako, Robert L Byer, Martin M Fejer, Hideo Mabuchi, Dirk Englund, Eleanor Rieffel, Hiroki
Takesue, Yoshihisa Yamamoto), Science advances 2, eaau0823.
8. Binary optimization by momentum annealing (with Takuya Okuyama, Tomohiro Sonobe, andMasanao Yamaoka), Physical Review E 100 (1), 012111 (2019)
9. 100,000-spin coherent Ising machine, to appear in Science advances.
4. Tier 1 Conferences in CS.
STOC, FOCS, SODA, SIGMOD, VLDB, ICDE, NIPS, KDD, ICML, NeurIPS, ICLR, ACL,AAAI, IJCAI, LICS, ICALPS, SOCG
1. Algorithmic Graph Minor Theory; Decomposition, Approximation and Coloring, (with E. D.
Demaine, M. Hajiaghayi), 46th Annual Symposium on Foundations of Computer Science(FOCS 2005) (2005) 637–646.
2. Approximating the chromatic number and the list-chromatic number of minor-closed family ofgraphs and odd-minor-closed family of graphs, STOC’06, 401–416.
3. Half integral packing, Erdős-Pósa property and Graph minors, ACM-SIAM Symposium on
Discrete Algorithms (SODA’07) 1187–1196.

13

4. Computing crossing number in linear time (with B. Reed), 39th ACM Symposium on Theoryof Computing (STOC’07), 382–390.
5. A nearly linear time algorithm for half-integral disjoint paths packing (with B. Reed), ACMSIAM Symposium on Discrete Algorithms (SODA’08), 446–454.
6. Graph and Map isomorphism and all polyhedral embeddings in linear time (with B. Mohar),40th ACM Symposium on Theory of Computing (STOC’08), 471–480.
7. Improved upper bounds on the crossing number (with V. Dujmovic, B. Mohar and D. Wood),
SOCG’08, 375–384.
8. A simpler linear time algorithm for embedding graphs on a surface and for bounded tree-widthgraphs (with B. Mohar and B. Reed), 49th Annual Symposium on Foundations of Computer
Science (FOCS 2008) (2008), 771–780.
9. Algorithms for finding an induced cycle in planar graphs and bounded genus graphs (with Y.
Kobayashi), ACM-SIAM Symposium on Discrete Algorithms, (SODA’09), 1146–1155.
10. Additive approximation algorithms for list-coloring minor-closed class of graphs (with E. Demaine and M. Hajiaghayi), ACM-SIAM Symposium on Discrete Algorithms, (SODA’09), 1166–
1175.
11. Three-coloring triangle-free planar graphs in linear time (with Z. Dvorak and R. Thomas),
ACM-SIAM Symposium on Discrete Algorithms, (SODA’09), 1176–1182.
12. A nearly linear time algorithm for the half integral parity disjoint paths packing problem (with
B. Reed), ACM-SIAM Symposium on Discrete Algorithms , (SODA’09), 1183–1192.
13. List-Color-Critical Graphs on a Fixed Surface (with B. Mohar), ACM-SIAM Symposium on
Discrete Algorithms, (SODA’09), 1166–1175.
14. Hadwiger’s Conjecture is decidable (with B. Reed), the 41st ACM Symposium on Theory ofComputing (STOC’09) 445–454.
15. Planarity allowing few error vertices in linear time, 50th Annual Symposium on Foundationsof Computer Science (FOCS 2009), 639–648.
16. Recognizing a totally odd K4 -subdivision, parity 2-disjoint rooted paths and a parity cycle
through specified elements (with Z. Li and B. Reed), ACM-SIAM Symposium on Discrete
Algorithms, (SODA’10), 318–328.
17. Decomposition, Approximation, and Coloring of Odd-Minor-Free Graphs (with E. Demaineand M. Hajiaghayi), ACM-SIAM Symposium on Discrete Algorithms, (SODA’10), 329–344.
18. The edge disjoint paths problem in Eulerian graphs and 4-edge-connected graphs (with Y.
Kobayashi), ACM-SIAM Symposium on Discrete Algorithms, (SODA’10), 345–353.
19. An (almost) Linear Time Algorithm For Odd Cycles Transversal (with B. Reed), ACM-SIAM
Symposium on Discrete Algorithms, (SODA’10), 365–378.

1420. Odd cycle packing (with B. Reed), 42nd ACM Symposium on Theory of Computing (STOC’10),
695–704.
21. A shorter proof of the Graph Minor Algorithm - The Unique Linkage Theorem - (with P.
Wollan), 42nd ACM Symposium on Theory of Computing (STOC’10), 687–694.
22. Linkless and flat embeddings in 3-space and the Unknot problem (with S. Kreutzer and B.
Mohar), the 26th Annual ACM Symposium on Computational Geometry (SOCG’10), 97–106.
23. A separator theorem in minor-closed classes (with B. Reed), the 51st Annual Symposium on
Foundations of Computer Science (FOCS’10), 153–162.
24. Contraction Decomposition in H-Minor-Free Graphs and Algorithmic Applications (with E.
Demaine and M. Hajiaghayi), the 43rd ACM Symposium on Theory of Computing (STOC’11),
441–450.
25. A simpler algorithm and shorter proof for the graph minor decomposition (with P. Wollan),the 43rd ACM Symposium on Theory of Computing (STOC’11), 451–458.
26. Finding topological subgraphs is fixed-parameter tractable (with M. Grohe, D. Marx and
P.Wollan), the 43rd ACM Symposium on Theory of Computing (STOC’11), 479–488.
27. Breaking O(n1/2 )-approximation algorithms for the edge-disjoint paths problem (with Y. Kobayashi),the 43rd ACM Symposium on Theory of Computing (STOC’11), 81–88.
28. The Inter-League Extension of the Traveling Tournament Problem and its Application toSports Schedule (with R. Hoshino), the Twenty-Fifth AAAI Conference on Artificial Intelligence (AAAI-11).
29. The Multi-Round Balanced Traveling Tournament Problem (with R. Hoshino), the 21st International Conference on Automated Planning and Scheduling (ICAPS’11), 106–113.
30. The minimum k-way cut of bounded size is fixed-parameter tractable (with M. Thorup), 52nd
Annual Symposium on Foundations of Computer Science (FOCS’11), 160–169.
31. The Graph Minor Algorithm with Parity Conditions (with B. Reed and P. Wollan), 52nd
Annual Symposium on Foundations of Computer Science (FOCS’11), 27–36.
32. Spanning closed walks and TSP in 3-connected planar graphs (with K. Ozeki), ACM-SIAM
Symposium on Discrete Algorithms, (SODA’12), 671–682.
33. Erdős-Pósa property and its algorithmic applications — parity constraints, subset feedback
set, and subset packing (with N. Kakimura and Y. Kobayashi), ACM-SIAM Symposium on
Discrete Algorithms, (SODA’12), 1726–1826.
34. List-Coloring Graphs without Subdivisions and without Immersions (with Y. Kobayashi, ACMSIAM Symposium on Discrete Algorithms, (SODA’12), 1425–1435.
35. The Linear Distance Traveling Tournament Problem (with R. Hoshino), the Twenty-Sixth
AAAI Conference on Artificial Intelligence (AAAI-12).

15

36. Combinatorial coloring of 3-colorable graphs (with M. Thorup), the 53rd Annual Symposium
on Foundations of Computer Science (FOCS’12) 68–75.
37. A Simple Algorithm for the Graph Minor Decomposition - Logic meets Structural Graph Theory (with M. Grohe and B. Reed), ACM-SIAM Symposium on Discrete Algorithms, (SODA’13),
414–431.
38. 5-coloring K3,k -minor-free graphs, ACM-SIAM Symposium on Discrete Algorithms, (SODA’13),
985–1003.
39. Totally odd subdivisions and parity subdivisions: Structures and Coloring, ACM-SIAM Symposium on Discrete Algorithms, (SODA’13), 1013–1029.
40. List-coloring embedded graphs (with Z. Dvorak), ACM-SIAM Symposium on Discrete Algorithms, (SODA’13), 1004–1012.
41. Packing directed cycles through a specified vertex set (with M. Krcal, D. Kral and S. Kreutzer),
ACM-SIAM Symposium on Discrete Algorithms, (SODA’13), 365-377.
42. 4-connected projective planar graphs are hamiltonian-connected (with K. Ozeki), ACM-SIAM
Symposium on Discrete Algorithms, (SODA’13), 378–395.
43. More Compact Oracles for Approximate Distances in Undirected Planar Graphs (with C. Sommer and M. Thorup), ACM-SIAM Symposium on Discrete Algorithms, (SODA’13), 550–561.
44. Testing subdivision-freeness: property testing meets structural graph theory (with Y. Yoshida),
the 43rd ACM Symposium on Theory of Computing (STOC’13), 437–446.
45. Mining for Analogous Tuples from an Entity-Relation Graph (with D, Bollegana, M. Kusumoto
and Y. Yoshida), IJCAI’13.
46. Model Checking for Successor-Invariant First-Order Logic on Minor-Closed Graph Classes(with K. Eickmeyer, and S. Kreutzer), Logic in Computer Science(LICS’13), 134-142.
47. All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs(with Y. Kobayashi). FOCS’13, 187–196.
48. Computing Personalized PageRank Quickly by Exploiting Graph Structures (with T. Maehara,
T. Akiba and Y. Iwata). VLDB 7(12): 1023-1034 (2014).
49. Fast and Accurate Influence Maximization on Large Networks with Pruned Monte-Carlo Simulations (with N. Ohsaka, T. Akiba and Y. Yoshida), AAAI’14, 138-144.
50. Solving the Traveling Tournament Problem by Packing Three-Vertex Paths (with M. Goerigk,
R. Hoshino, S. Westphal) AAAI’14, 2271-2277.
51. Optimal Budget Allocation: Theoretical Guarantee and Efficient Algorithm (with T. Soma, N.
Kakimura, K. Inaba). ICML 2014: 351-359.
52. Scalable similarity search for SimRank (with M. Kusumoto and T. Maehara), Proceedings ofthe 2014 ACM SIGMOD International Conference on Management of Data (SIGMOD 2014),(2014), 325-336.
1653. An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem(with Y. Kobayashi and S. Kreutzer), Proceedings of the 46th ACM Symposium on Theory ofComputing (STOC 2014), (2014) 70-78.
54. Embedding and Canonizing Graphs of Bounded Genus in Logspace (with M. Elberfeld), Proceedings of the 46th ACM Symposium on Theory of Computing (STOC 2014), (2014), 383-392.
55. An Excluded Grid Theorem for Digraphs with Forbidden Minors (with S. Kreutzer), Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA2014), (2014), 72-81.
56. Lagrangian Decomposition Algorithm for Allocating Marketing Channels (D. Hatano, T. Fukunaga, T. Maehara), Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI),(2015), 1144-1150.
57. Learning Word Representations from Relational Graphs (with D. Bollegala, T. Maehara, Y.
Yoshida), Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI), (2015),
2146–2152.
58. Scalable SimRank join algorithm (with T. Maehara and M. Kusumoto), Proceedings of the
31st IEEE International Conference on Data Engineering(ICDE’15), (2015), 603–614.
59. Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time (with M. Thorup),
the 47th ACM Symposium on Theory of Computing (STOC 2015), 665–674.
60. The directed grid theorem (with S. Kreutzer), the 47th ACM Symposium on Theory of Computing (STOC 2015), 655–664.
61. Beyond the Euler characteristic: Approximating the genus of general graphs (with A. Sidiropoulos), the 47th ACM Symposium on Theory of Computing (STOC 2015), 675–0682.
62. Embedding Semantic Relations into Word Representations (with D. Bollegala and T. Maehara),
the 24th International Joint Conference on Artificial Intelligence(IJCAI’15), 1222–1228.
63. Budget Allocation Problem with Multiple Advertisers: A Game Theoretic View (with T. Maehara and T. Yabe), ICML’15, 428–437.
64. Unsupervised Cross-Domain Word Representation Learning, (with Danushka Bollegala and
Takanori Maehara), ACL’15, 730–740.
65. Efficient PageRank Tracking in Evolving Networks, (with Naoto Ohsaka, Takanori Maehara),
KDD’15, 875-884.
66. Real-time Top-R Topic Detection on Twitter with Topic Hijack Filtering (with Kohei Hayashi,
Takanori Maehara, Masashi Toyoda), KDD’15, 417-426.
67. Estimating Local Intrinsic Dimensionality (with Oussama Chelly, Laurent Amsaleg, Teddy
Furon, Stéphane Girard, Michael Houle, Michael Nett), KDD’15, 29–38.
68. Expected Tensor Decomposition with Stochastic Gradient Descent (with T. Maehara and K.
Hayashi), AAAI’16, 1919–1925.
17

69. Joint Word Representation Learning using a Corpus and a Semantic Lexicon (with D. Bollegala,
M. Alsuhaibani and T. Maehara), AAAI’16, 2690–2696.
70. Identifying Key Observers to Find Popular Information in Advance (with T. Konishi, K.
Hayashi, T. Iwata), IJCAI’16, 3761–3767.
71. Adaptive budget allocation for maximizing influence of advertisements (with T. Fukunaga, D.
Hatano), IJCAI’16, 3600–3608.
72. Dynamic Influence Analysis in Evolving Networks (with N. Ohsaka, T. Akiba and Y. Yoshida),
VLDB’16 12 1077–1088.
73. Scalable algorithm for higher-order co-clustering via random sampling (with D. Hatano, T.
Fukunaga, T. Maehara), AAAI’17, 1992–1999.
74. Optimal Pricing for Submodular Valuations with Bounded Curvature (with H. Sumita, Y.
Kawase, T. Tono, T. Maehara), AAAI’17, 622–628.
75. Coarsening Massive Influence Networks for Scalable Diffusion Analysis (with N. Ohsaka, T.
Sonobe, S. Fujita), SIGMOD’17, 635–650.
76. An Improved Approximation Algorithm for the Subpath Planning Problem and Its Generalization (with H. Sumita, Y. Yonebayashi and N. Kakimura), the 26th International Joint
Conference on Artificial Intelligence (IJCAI’17), 4412–4418.
77. Polylogarithmic approximation for minimum planarization (almost) (with A. Sidiropoulos),FOCS’17, 779–788.
78. Efficient Sublinear-Regret Algorithms for Online Sparse Linear Regression (with S. Ito, H.
Sumita, D. Hatano, T. Fukunaga, N. Kakimura, A. Yabe), NIPS’17, 4102–4111.
79. A Polynomial Excluded-Minor Approximation of Treedepth (with B. Rossman), SODA’18,
234–246.
80. Using k-way Co-occurrences for Learning Word Embeddings (with D. Bollegala and Y. Yoshida),
AAAI’18.
81. Think Globally, Embed Locally — Locally Linear Meta-embedding of Words (with D. Bollegala
and K. Hayashi), IJCAI’18, 3970–3976.
82. Causal Bandits with Propagating Inference Reviewer Matching Request (with S. Ito, H. Sumita,
D. Hatano, T. Fukunaga, N. Kakimura, A. Yabe), ICML’18, 5449-5458.
83. Representation Learning on Graphs with Jumping Knowledge Network (with K. Xu, C. Li, Y.
Tian, T. Sonobe, S. Jegelka) ICML’18, 5449-5458.
84. Regret Bounds for Online Portfolio Selection with a Cardinality Constraint (with S. Ito, H.
Sumita, D. Hatano, T. Fukunaga, N. Kakimura), NeurIPS 2018: 10611–10620.
85. Polynomial Planar Directed Grid Theorem (with H. Meike and S. Kreutzer), SODA’19, 1465–
1484.

18

86. Stochastic Submodular Maximization with Performance-Dependent Item Costs (with T. Konishi, T. Fukunaga and S. Fujita), AAAI’19, 1485–1494.
87. Polylogarithmic approximation for Euler genus on bounded degree graphs (with A. Sidiropoulos), STOC’19, 164–175.
88. Cross-Lingual Mapping of Non-Isomorphic Embedding with Iterative Normalization (withMozhi Zhang, Keyulu Xu, Stefanie Jegelka, and Jordan Boyd-Graber), ACL’19, 3180–3189.
89. Oracle-Efficient Algorithms for Online Linear Optimization with Bandit Feedback (with S. Ito,
H. Sumita, D. Hatano, K. Takemura, T. Fukunaga, N. Kakimura), NeurIPS 2019, 10589-10598.
90. Improved Regret Bounds for Bandit Combinatorial Optimization (with S. Ito, H. Sumita, D.
Hatano, K. Takemura, T. Fukunaga, N. Kakimura), NeurIPS 2019, 12027-12036.
91. A nearly 5/3-approximation FPT Algorithm for Min-k-Cut (with B. Lin), SODA’20, 990–999.
92. The directed flat grid theorem(with A. Giannopoulou, S. Kreutzer, and O. Kwon), SODA’20,
239–258.
93. What Can Neural Networks Reason About? (with Keyulu Xu, Jingling Li, Simon S. Du, Mozhi
Zhang, and Stefanie Jegelka), ICLR’20.
94. Delay and Cooperation in Nonstochastic Linear Bandits, (with S. Ito, H. Sumita, D. Hatano,
K. Takemura, T. Fukunaga, N. Kakimura), NeurIPS 2020.
95. Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff
Functions (with S. Ito, H. Sumita, D. Hatano, K. Takemura, T. Fukunaga, N. Kakimura),
AAAI 2021.
96. How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks(with Keyulu
Xu, Jingling Li, Simon S. Du, Mozhi Zhang, and Stefanie Jegelka), ICLR’21.
97. Embeddings of Planar Quasimetrics into Directed `1 and Polylogarithmic Approximation for
Directed Sparsest-Cut (with A. Sidiropoulos), to appear in FOCS’21.
5. Respectful Conferences in CS (* indicated core A, including ICALP, IPCO, STACS,
ALNEX, AISTATS, CIKM, SDM, DISC, EDBT, ECML, FCT, EACL, ISAAC, APPROX., IC3N*.)
1. Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner’s Contraction(with E. Demaine and M. Hajiaghayi), 17th International Symposium on Algorithms andComputation∗ (ISAAC 2006). Lecture Notes in Computer Science, volume 4288, Calcutta,
India, December 18-20, 2006, pages 3-15.
2. The induced disjoint paths problem (with Y. Kobayashi), IP CO0 08∗ , 47–61.
3. An improved algorithm for cycles through elements, IP CO0 08∗ , 374–384.
4. Approximating list-coloring on a fixed surface, ICALP 0 08∗ , 333–344.

19

5. Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs, (with E. Demaine and M. Hajaghayi), 35th International Colloquium on Automata, Languages and Programming (ICALP 0 09)∗ , 316–327.
6. An improved algorithm for the half disjoint paths problem (with Y. Kobayashi), Approx andRandom∗ 2010, 287-297.
7. An O(log n) approximation algorithm for the edge-disjoint paths problem in eulerlian planargraphs and 4-edge-connected planar graphs (with Y. Kobayashi), Approx and Random∗ 2010,274-286.
8. Message duplication reduction in dense mobile social network (with F. Nazir), International
Conference on Computer Communication Networks, (IC3N 0 10)∗ , 1–6.
9. The Distance-Optimal Inter-League Schedule for Japanese Pro Baseball (with R. Hoshino),
the ICAPS 2011 Workshop on Constraint Satisfaction Techniques for Planning and Scheduling
Problems (COPLAS), 71–78.
10. Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus, and Minor-Free Graphs(with P. Klein and C. Sommer), ICALP ∗ 2011, 135–146.
11. Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid minor (with Y. Kobayashi), Symposium on Theoretical Aspects of Computer Science∗ (STACS),
278–289, 2012.
12. Edge-disjoint Odd Cycles in 4-edge-connected Graphs (with Y. Kobayashi), Symposium on
Theoretical Aspects of Computer Science∗ (STACS), 206–217, 2012.
13. Shortest-Path Queries for Complex Networks: Exploiting Low Tree-width Outside the Core,(with T. Akiba and C. Sommer), EDBT ∗ 2012 - 15th International Conference on Extending
Database Technology, 144–155.
14. Balancing the Traveling Tournament Problem for Weekday and Weekend Games(with R.
Hoshino), the Twenty-Fifth Annual Conference on Innovative Applications of Artificial Intelligence (IAAI-13).
15. Approximating Multi Commodity Network Design on Graphs of Bounded Pathwidth andBounded Degree(with K. Eickmeyer), SAGT 2013: 134-145.
16. Coloring 3-colorable graphs with o(n1/5 ) colors (with M. Thorup), Proceedings of the 31st
Symposium on Theoretical Aspects of Computer Science∗ (STACS 2014), (2014), 458—469.
17. Fast Shortest-path Distance Queries on Road Networks by Pruned Highway Labeling (with T.
Akiba, Y. Iwata, Y. Kawata). ALEN EX ∗ 2014, 147-154.
18. Towards the Graph Minor Theorems for Directed Graphs (with S. Kreutzer), ICALP 0 15∗ , 3-10
19. Scalable Sensor Localization via Ball-Decomposition Algorithm (with Y. Kawase and T. Maehara), the 14th IFIP International Conferences on N etworking ∗ 2015, 1–9.
20. Successor-Invariant First-Order Logic on Graphs with Excluded Topological Subgraphs (with
K. Eickmeyer), CSL’16, 18:1-18:15.
20

21. Fully Dynamic Shortest-Path Distance Query Acceleration on Massive Networks. CIKM ∗2016: 1533-1542
22. Maximizing Time-decaying Influence in Social Networks (with N. Ohsaka, Y. Yamaguchi, N.
Kakimura), ECM L∗ PKDD’16, 132–147.
23. FO Model Checking on Map Graphs (with K. Eickmeyer), F CT 0 17∗ , 204–216.
24. Online Regression with Partial Information: Generalization and Linear Projection (with S. Ito,
H. Sumita, D. Hatano, T. Fukunaga, N. Kakimura, A. Yabe), AISTATS’18∗ , 1599–1607.
25. Additive non-approximability of chromatic number in proper minor-closed classes (with Z.
Dvorak), ICALP’18∗ , 1-47: 12.
26. A Deterministic Distributed 2-Approximation for Weighted Vertex Cover in O(log n log ∆/ log2 log ∆)Rounds (with R. B. Basat, G. Even, G. Schwartzman), SIROCCO’18, 226–236.
27. NoSingles: a Space-Efficient Algorithm for Influence Maximization (with D. Dpopova, N. Osaka, A. Thomo) SSDBM ’18, 18:1-18:12
28. Boosting PageRank Scores by Optimizing Internal Link Structure (with N. Osaka, N. Kakimura,
T. Fukunaga, S. Fujita), DAXA’18, 424–439 .
29. Adapting Local Sequential Algorithms to the Distributed Setting (with G. Schwartzman),
DISC 0 18∗ , 35:1-35:17.
30. Intrinsic Dimensionality Estimation within Tight Localities (with L. Amsaleg, O. Chelly, M.
Houle, M. Radovanovic, W. Treeratanajaru), SDM∗ 181–189, 2019.
31. Parameterized Distributed Algorithms (with R. Ben Basat and G. Schwartzman), DISC 0 19∗ ,15.
32. Optimal Distributed Covering Algorithms(with R. Ben Basat, G. Even and G. Schwartzman),
DISC 0 19∗ , 16.
33. Improved Distributed Approximations for Maximum-Weight Independent Set (with S. Khoury,
A. Schild, G. Schwartzman), DISC 0 20∗ , 283–285.
34. RelWalk - A Latent Variable Model Approach to Knowledge Graph Embedding (with Hakimi,
D. Bollegala, Y. Yoshida), EACL0 21∗ , 1551–1565.
35. A Parameter-Free Algorithm for Misspecified Linear Contextual Bandits (with S. Ito, H.
Sumita, D. Hatano, K. Takemura, T. Fukunaga, N. Kakimura), AIST AT S2021∗ 3367-3375.
6. Other papers.
1. Contractible edges in k-connected graph containing no K4− , (with K. Ando and A. Kaneko),
Sut J. mathematics, 36 (2000) 99–103.
2. A Note on Hamiltonian Cycles in (k, n)-Factor-Critical Graphs, Sut J. Mathematics, 36 (2000)
259–266.

21

3. Vertex-Disjoint Cycles Containing Specified Edges in a Bipartite Graph, (with H. Enomoto,G. Chen, D. Lou, K. Ota and A. Saito.) Australasian J. Combinatorics 23 (2001) 37–48.
4. A Survey on Hamiltonian Cycles, Interdisciplinary Information Science 7 (2001) 25–39.
5. Contracting 4-Connected Plane Triangulations into an Octahedron, (with A. Nakamoto, Y.
Oda and M. Watanabe), Lecture Note on Computer Science 2098 (2001) 217–221.
6. Note on contractible edges in k-connected graphs, Australasian J. Combinatorics 24 (2001)
165–168.
7. F -factor and vertex disjoint F in Graphs, Ars Combinatoria 62 (2001) 183–187.
8. Contractible edges and Bowtie in k-connected graphs, (with K. Ando, A. Kaneko and K.
Yoshimoto), Ars Combinatoria 64 (2002) 239–247.
9. Vertex disjoint K4− in graphs, Discuss. Math. Graph Theory 24 (2004) 249–262.
10. On properties of a set of global roundings associated with clique connection of graphs (with K.
Ishikawa and T. Tokuyama), Interdisciplinary Information Science 10 (2004) 159–163.
11. Erdos-Chvatal condition and 2-factors (with G. Chen, R. Gould, K. Ota, I. Schiermeyer, A.
Saito), Discuss. Math. Graph Theory 27 (2007) 401–408.
12. Cliques in Odd-Minor-Free Graphs (with D. Wood), CATS 2012, 133–138.
Plenary and invited Speaker at Conferences
1. The Sixth Annual Paul Erdös Memorial Lecture, One of invited speakers, University of Memphis, March 2002.
2. The Fifth Slovenian Conference in Graph Theory. June. 2003.
3. Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS’07), Chile, Nov.
2007.
4. Cumberland Conference on Combinatorics, Graph Theory and Computing, 2008, May, Vanderbilt Univ. (Dedicated to Mike Plummer’s 70’s birthday.)
5. GRAPH THEORY AT SANDBJERG MANOR, August 17-23, Denmark, 2008. (Dedicated to
Carsten Thomassen’s 60th birthday.)6. Fourth workshop in Graph Classes, Optimization, and Width Parameters, GROW 2009, inBergen, October, 2009.
7. Danish Graph Theory, November, 2009.
8. WALCOM, Workshop on Algorithm and Computation, in New Delhi, India on February 18-20,
2011.
9. Graph Theory 2011, Hotel Koldingfjord in Kolding, Denmark, April 28 - May 1.

2210. 8th Annual Conference on Theory and Applications of Models of Computation (TAMC’11),
Tokyo, May, 2011.
11. EuroComb 2011, European Conference on Combinatorics, Graph Theory and Applications,
Aug 29-Sep 2, Budapest, Hungary.
12. Robin Thomas Festa at Charles University, 2011, Nov.
13. Conference devoted to the 50th birthday of Robin Thomas, Atlanta, 2012 May.
14. SIAM Discrete Math. Conf 2012, June.
15. Graph Theory and Interactions (LMS symposium), Durham, England, UK, 15-25 July 2013.
16. 16th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCG2 2013),
Sept. 17-19, Tokyo University of Science, Kagurazaka, Tokyo, Japan
17. The Japanese Conference on Combinatorics and its Applications (JCCA 2014), Aug 25-29,
University of Tsukuba, Japan.
18. 23rd Workshop on Cycles and Colourings, Sept. 7-12, Novy Smokovec, High Tatras, Slovakia
19. 7th Cracow Conference on Graph Theory, Sept. 14-19, Rytro, Poland.
20. ICALP’15, Plenary
21. Topological graph theory conference in Yokohama, Nov. 2018
22. Waterloo Color, Sept. 2019.
23. Highlights of Algorithms, June, Paris, 2016.
24. DIMAP’10, Wawrick University, December, 2017.
25. Danish Graph Theory Conferences, August, 2018.
26. Waterloo coloring, September, 2019.
27. Australian Combinatorial Conference, December, 201923