Research

I would rather have today's algorithms on yesterday's computers than vice versa. — Phillipe Toint

The purpose of computing is insight, not numbers. — Richard Hamming

Research interests

  • algorithms in graph classes
  • structural graph theory
  • algorithms for NP-hard problems
  • geometric representations of graphs
  • graph homomorphisms

Research projects

  • I was an investigator in the project: Sequences covering sets and achromatic colorings of graphs (OPUS, 2012/05/B/ST1/00652, PI: Zbigniew Lonc).
  • I was an investigator in the project: New data intensive algorithms and structures for GPU processors (SONATA, 2012/07/D/ST6/0248, PI: Krzysztof Kaczmarski).
  • I was an investigator in the ERC Starting Grant PARAMTIGHT (PI: Daniel Marx).
  • I was an investigator in the LMS Grant under the scheme Research in pair Scheme 4 (PI: Daniel Paulusma).
  • I was the principal investigator in the project: Complexity of graph homomorphism problems in special classes of graphs (MINIATURA2, 2018/02/X/ST6/00145).
  • I was an investigator in the ERC Starting Grant CUTACOMBS (PI: Marcin Pilipczuk).
  • I was the principal investigator in the project: Optimality program in graph homomorphism problems (SONATA 14, 2018/31/D/ST6/00062).
  • I was an investigator in the ERC Starting Grant BOBR (PI: Michał Pilipczuk).
  • I am the principal investigator in the project: From dense graphs to sparse ones and back again (SONATA-BIS 14, 2024/54/E/ST6/00094).

PhD students

Present

Paweł Rafał Bieliński, Warsaw University of Technology

Past

Karolina Okrasa, Warsaw University of Technology

  • Topic: Graph homomorphism: from structure to algorithms
  • Co-supervisor: Zbigniew Lonc
  • Defense date: 12 March 2024, with honors

Marta Piecyk, Warsaw University of Technology

  • Topic: Graph homomorphisms -- exploring the boundaries of tractability
  • Co-supervisor: Zbigniew Lonc
  • Defense date: 30 May 2025, with honors

Other

I am an editor of Graphs and Combinatorics .

  • Erdős number: 2 (Paul Erdős - Adrian Bondy/Jaroslav Nesetril)
  • Bacon number: 4 (Kevin Bacon - John Malkovich - Małgorzata Rożniatowska - Tomasz Gęsikowski)
  • Bryś number: 1 (Krzysztof Bryś)
  • Erdős-Bacon-Bryś number: 7

I am a participant of Seminarium Kombinatoryka, Teoria Grafów i Zbiorów Uporządkowanych .

Cooperation

Here is a possibly incomplete list of my co-authors.

  1. Tara Abrishami
  2. Akanksha Agrawal
  3. Noga Alon
  4. Marcin Anholcer
  5. Maciej Bartkowiak
  6. Paweł Rafał Bieliński
  7. Csaba Biró
  8. Václav Blažej
  9. Jan Bok
  10. Marthe Bonamy
  11. J. Adrian Bondy
  12. Édouard Bonnet [picture, Lugano 2016, with Till Miltzow]
  13. Bartłomiej Bosek
  14. Nicolas Bousquet
  15. Marcin Briański
  16. Valentin E. Brimkov
  17. Michal Čertík
  18. Pierre Charbit
  19. Hubie Chen
  20. Maria Chudnovsky
  21. Joanna Chybowska-Sokół
  22. Sebastian Czerwiński
  23. Jadwiga Czyżewska
  24. Konrad K. Dąbrowski
  25. James Davies
  26. Michał Dębski
  27. Dariusz Dereniowski
  28. Cemil Dibek
  29. Michael Gene Dobbins
  30. Xiying Du
  31. Pavel Dvořák
  32. Keith Edwards
  33. László Egri
  34. Barış Can Esmer
  35. William S. Evans
  36. Carl Feghali
  37. Andreas Emil Feldmann
  38. Jiří Fiala
  39. Foivos Fioravantes
  40. Jacob Focke
  41. Jakub Gajarský
  42. Valentin Garnero
  43. Peter Gartland
  44. Panos Giannopoulos
  45. Jan Goedgebeur
  46. Jochen Pascal Gollin
  47. Jakob Greilhuber
  48. Carla Groenland [picture, Gułtowy 2019]
  49. Jarosław Grytczuk
  50. Grzegorz Gutowski
  51. Sepehr Hajebi
  52. Nadzieja Hodur
  53. Tomáš Hons
  54. Shenwei Huang
  55. Lars Jaffke
  56. Bart M. P. Jansen
  57. Nikola Jedličková
  58. Matthew Johnson
  59. Jorik Jooken
  60. Konstanty Junosza-Szaniawski [picture, Orléans 2012, with Mathieu Liedloff and Dieter Kratsch] [picture, Berlin 2011, with Sławek Kwasiborski and Armin Fügenschuh]
  61. Krzysztof Kaczmarski
  62. Sean Kafer
  63. Eun Jung Kim
  64. Jason King
  65. Sándor Kisfaludi-Bak
  66. Linda Kleist
  67. Felix Klesen
  68. Kacper Kluk
  69. Łukasz Kowalik
  70. Jan Kratochvíl [picture, Prague 2010]
  71. Monika Krawczyk
  72. Mateusz Krzyziński
  73. Erik Jan van Leeuwen
  74. Mathieu Liedloff
  75. Paloma T. de Lima
  76. Daniel Lokshtanov
  77. Zbigniew Lonc [picture, Istanbul 2016, with Michael Lampis and Nick Brettell]
  78. Katarzyna Łyczek
  79. Konrad Majewski
  80. Isja Mannens
  81. Dániel Marx
  82. Tomáš Masařík
  83. Jana Masaříková
  84. Rose McCarty
  85. Martin Milanič
  86. Tillmann Miltzow
  87. Pedro Montealegre-Barba
  88. Natasha Morrison
  89. Peter Muršič
  90. Irene Muzi
  91. Paweł Naroski [picture, Budapest 2016]
  92. Maria Nazarczuk
  93. Jesper Nederlof
  94. Jaroslav Nešetřil
  95. Amir Nikabadi
  96. JD Nir
  97. Dariusz Nogalski
  98. Sergey Norin
  99. Karolina Okrasa
  100. George Osipov
  101. Dorota Osula
  102. Giacomo Paesani
  103. Daniël Paulusma
  104. Martin Pergel
  105. Marta Piecyk
  106. Astrid Pieterse
  107. Marcin Pilipczuk
  108. Michał Pilipczuk
  109. Monika Pilśniak
  110. Magdalena Prorok
  111. Piotr Przymus
  112. Ashutosh Rai
  113. Amadeus Reinald
  114. Peter Rossmanith
  115. Noushin Saeedi
  116. Saket Saurabh
  117. Oliver Schaudt
  118. Alex D. Scott
  119. Paul D. Seymour
  120. Roohani Sharma
  121. Chan-Su Shin
  122. Florian Sikora
  123. Marek Sokołowski
  124. Manuel Sorge
  125. Uéverton S. Souza
  126. Jack Spalding-Jamieson
  127. Sophie Spirkl
  128. Kenny Štorgel
  129. Michał Stronkowski
  130. Ondřej Suchý
  131. Matthew Szczepankiewicz
  132. Joshua Terhaar
  133. Stéphan Thomassé
  134. Szymon Tur
  135. Kristina Vušković
  136. Magnus Wahlström
  137. Bartosz Walczak
  138. Krzysztof Węsek
  139. Alexandra Wesolek
  140. Albert Wolant
  141. Alexander Wolff
  142. Meirav Zehavi
  143. Mingxian Zhong
  144. Johannes Zink
  145. Stanislav Živný
  146. Aneta Żuk