Publications

Manuscripts

[10] An 11/6-Approximation Algorithm for Vertex Cover on String Graphs
with Paweł Rzążewski.
[9] Temporal Valued Constraint Satisfaction Problems
with Manuel Bodirsky and Žaneta Semanišinová.
[8] On the twin-width of smooth manifolds
with Kristóf Huszár.
[7] Treewidth Inapproximability and Tight ETH Lower Bound
[6] Sparse Induced Subgraphs of Large Treewidth
[5] Treewidth is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor
with Jędrzej Hodor, Tuukka Korhonen, Tomáš Masařík.
[4] Graphs without a 3-connected subgraph are 4-colorable
with Carl Feghali, Tung Nguyen, Alex Scott, Paul Seymour, Stéphan Thomassé, and Nicolas Trotignon.
[3] A tamed family of triangle-free graphs with unbounded chromatic number
with Romain Bourneuf, Julien Duron, Colin Geniet, Stéphan Thomassé, and Nicolas Trotignon.
[2] Twin-width VII: groups
with Colin Geniet, Romain Tessera, and Stéphan Thomassé.
[1] Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)
with O-joung Kwon and David Wood.

Conferences

[62] Adjacency Labeling Schemes for Small Classes
with Julien Duron, John Sylvester, Viktor Zamaraev. ITCS, 2025.
[61] Symmetric Difference (Degeneracy) and Signed Tree Models
with Julien Duron, John Sylvester, and Viktor Zamaraev. MFCS, 2024.
[60] Tight Bounds on Adjacency Labels for Monotone Graph Classes
with Julien Duron, John Sylvester, Viktor Zamaraev, and Maksim Zhukovskii. ICALP, 2024.
[59] Factoring Pattern-Free Permutations into Separable ones
with Romain Bourneuf, Colin Geniet, and Stéphan Thomassé. SODA, 2024.
[58] Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes
with Julien Duron, John Sylvester, Viktor Zamaraev, and Maksim Zhukovskii. SODA, 2024.
[57] PACE Solver Description: RedAlert - Heuristic Track
with Julien Duron. IPEC, 2023 (PACE).
[56] Stretch-width
with Julien Duron. IPEC, 2023.
[55] Treewidth is NP-Complete for Cubic Graphs (and related results)
with Hans L. Bodlaender, Lars Jaffke, Dušan Knop, Paloma T. Lima, Martin Milanič, Sebastian Ordyniak, Sukanya Pandey, and Ondřej Suchý. IPEC, 2023.
[54] Maximum Independent Set when excluding an induced minor: K1 + tK2 and tC3 ⊎ C4
with Julien Duron, Colin Geniet, Stéphan Thomassé, and Alexandra Wesolek. ESA, 2023.
[53] Cutting Barnette graphs perfectly is hard
with Julien Duron and Dibyayan Chakraborty. WG, 2023.
[52] Twin-width V: linear minors, modular counting, and matrix multiplication
with Ugo Giocanti, Patrice Ossona de Mendez, and Stéphan Thomassé. STACS, 2023.
[51] Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width
with Pierre Bergé, Hugues Déprés, and Rémi Watrigant. STACS, 2023.
[50] Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
Marthe Bonamy, Hugues Déprés, Louis Esperet, Colin Geniet, Claire Hilaire, Stéphan Thomassé, and Alexandra Wesolek. SODA, 2023.
[49] Twin-width VIII: delineation and win-wins
with Dibyayan Chakraborty, Eun Jung Kim, Noleen Köhler, Raul Lopes, and Stéphan Thomassé. IPEC, 2022.
[48] Model Checking on Interpretations of Classes of Bounded Local Cliquewidth
with Jan Dreier, Jakub Gajarský, Stephan Kreutzer, Nikolas Mählmann, Pierre Simon, and Szymon Toruńczyk. LICS, 2022.
[47] Deciding twin-width at most 4 is NP-complete
with Pierre Bergé and Hugues Déprés. ICALP, 2022.
[46] Twin-width IV: ordered graphs and matrices
with Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, and Szymon Toruńczyk. STOC, 2022.
[45] Twin-width VI: the lens of contraction sequences
with Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé. SODA, 2022.
[44] Twin-width and polynomial kernels
with Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, and Rémi Watrigant. IPEC, 2021.
[43] 4 vs 7 sparse undirected unweighted Diameter is SETH-hard at time n4/3
ICALP, 2021.
[42] Twin-width III: Max Independent Set, Min Dominating Set, and Coloring
with Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. ICALP, 2021.
[41] Inapproximability of Diameter in super-linear time: Beyond the 5/3 ratio
STACS, 2021.
[40] Twin-width II: small classes
with Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. SODA, 2021.
[39] Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth
with Benjamin Bergougnoux, Nick Brettell, and O-joung Kwon. IPEC, 2020.
[38] Maximum Clique in Disk-Like Intersection Graphs
with Nicolas Grelier and Tillmann Miltzow. FSTTCS, 2020.
[37] Twin-width I: tractable FO model checking
with Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. FOCS, 2020.
[36] An algorithmic weakening of the Erdős-Hajnal conjecture
with Stéphan Thomassé, Xuan Thang Tran, and Rémi Watrigant. ESA, 2020.
[35] Grundy Coloring & friends, Half-Graphs, Bicliques
with Pierre Aboulker, Eun Jung Kim, and Florian Sikora. STACS, 2020.
[34] Maximum Matchings in Geometric Intersection Graphs
with Sergio Cabello and Wolfgang Mulzer. STACS, 2020.
[33] When Maximum Stable Set can be solved in FPT time
with Nicolas Bousquet, Stéphan Thomassé, and Rémi Watrigant. ISAAC, 2019.
[32] Parameterized Streaming Algorithms for Min-Ones d-SAT
with Akanksha Agrawal, Arindam Biswas, Nick Brettell, Radu Curticapean, Dániel Marx, Tillmann Miltzow, Venkatesh Raman, and Saket Saurabh. FSTTCS, 2019.
[31] Metric Dimension Parameterized by Treewidth
with Nidhi Purohit. IPEC, 2019.
[30] Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP
with Yoichi Iwata, Bart M. P. Jansen, and Łukasz Kowalik. ESA, 2019.
[29] Constraint Generation Algorithm for the Minimum Connectivity Inference Problem
with Diana-Elena Fǎlǎmaş and Rémi Watrigant. SEA, 2019.
[28] EPTAS for Max Clique on Disks and Unit Balls
with Marthe Bonamy, Nicolas Bousquet, Pierre Charbit, and Stéphan Thomassé. FOCS, 2018.
[27] Parameterized Complexity of Independent Set in H-free graphs
with Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, and Rémi Watrigant. IPEC, 2018.
[26] The PACE 2018 Parameterized Algorithms and Computational Experiments Challenge: The Third Iteration
with Florian Sikora. IPEC, 2018.
[25] Optimality Program in Segment and String graphs
with Paweł Rzążewski. WG, 2018.
[24] QPTAS and Subexponential Algorithm for Maximum Clique on Disks
with Panos Giannopoulos, Eun Jung Kim, Paweł Rzążewski, and Florian Sikora. SoCG, 2018.
[23] Orthogonal Terrain Guarding is NP-complete
with Panos Giannopoulos. SoCG, 2018.
[22] Designing RNA secondary structures is NP-hard
with Paweł Rzążewski and Florian Sikora. RECOMB, 2018.
[21] On the Parameterized Complexity of Red-Blue Points Separation
with Panos Giannopoulos and Michael Lampis. IPEC, 2017.
[20] Generalized feedback vertex set problems on bounded-treewidth graphs
with Nick Brettell, O-joung Kwon, and Dániel Marx. IPEC, 2017.
[19] The Parameterized Complexity of Positional Games
with Serge Gaspers, Antonin Lambilliotte, Stefan Rümmele, and Abdallah Saffidine. ICALP, 2017.
[18] Approximation Algorithm of the Art Gallery Problem
with Tillmann Miltzow. SoCG, 2017.
[17] Fine-grained complexity of coloring unit disks and balls
with Csaba Biró, Dániel Marx, Tillmann Miltzow, and Paweł Rzążewski. SoCG, 2017.
[16] Complexity of Token Swapping and its Variants
with Tillmann Miltzow and Paweł Rzążewski. STACS, 2017.
[15] Parameterized Hardness of Art Gallery Problems
with Tillmann Miltzow. ESA, 2016.
[14] Fixed-parameter Approximability of Boolean MinCSPs
with László Egri, and Dániel Marx. ESA, 2016.
[13] Parameterized vertex deletion problems for hereditary graph classes with a block property
with Nick Brettell, O-joung Kwon, and Dániel Marx. WG, 2016.
[12] The Complexity of Playing Durak
IJCAI, 2016.
[11] Time-Approximation Trade-offs for Inapproximable Problems
with Michael Lampis and Vangelis Th. Paschos. STACS, 2016.
[10] A 0.821-ratio purely combinatorial algorithm for maximum k-vertex cover in bipartite graphs
with Bruno Escoffier, Vangelis Th. Paschos, and Georgios Stamoulis. LATIN, 2016.
[9] The Graph Motif problem parameterized by the structure of the input graph
with Florian Sikora. IPEC, 2015.
[8] Complexity of grundy coloring and its variants
with Florent Foucaud, Eun Jung Kim, and Florian Sikora. COCOON, 2015.
[7] Draws, Zugzwangs, and PSPACE-completeness in the Slither Connection Game
with Florian Jamain and Abdallah Saffidine. ACG, 2015.
[6] On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism
with Faisal N. Abu-Khzam and Florian Sikora. IWOCA, 2014.
[5] On the Complexity of General Game Playing
with Abdallah Saffidine. CGW, 2014.
[4] Multi-parameter complexity analysis for constrained size graph problems
with Bruno Escoffier, Vangelis Th. Paschos, and Émeric Tourniaire. IPEC, 2013.
[3] On subexponential and fpt-time inapproximability
with Bruno Escoffier, Eun Jung Kim, and Vangelis Th. Paschos. IPEC, 2013.
[2] On the complexity of trick-taking card games
with Florian Jamain and Abdallah Saffidine. IJCAI, 2013.
[1] Havannah and twixt are pspace-complete
with Florian Jamain and Abdallah Saffidine. CG, 2013.

Journals

[42] Twin-width III: Max Independent Set, Min Dominating Set, and Coloring
with Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. SIAM J. Comput., 2024.
[41] Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes
with Julien Duron, John Sylvester, Viktor Zamaraev, and Maksim Zhukovskii. SIAM J. Comput., 2024.
[40] Twin-width IV: ordered graphs and matrices
with Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, and Szymon Toruńczyk. Journal of the ACM, 2024.
[39] Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
Marthe Bonamy, Hugues Déprés, Louis Esperet, Colin Geniet, Claire Hilaire, Stéphan Thomassé, and Alexandra Wesolek. Journal of Combinatorial Theory, Series B, 2024.
[38] Cutting Barnette graphs perfectly is hard
with Julien Duron and Dibyayan Chakraborty. TCS, 2024.
[37] Twin-width and permutations
with Jaroslav Nešetřil, Patrice Ossona de Mendez, Sebastian Siebertz, and Stéphan Thomassé. Logical Methods in Computer Science, 2024.
[36] Neighbourhood complexity of graphs of bounded twin-width
with Florent Foucaud, Tuomo Lehtilä, and Aline Parreau. European Journal of Combinatorics, 2024.
[35] Maximum Matchings in Geometric Intersection Graphs
with Sergio Cabello and Wolfgang Mulzer. Discrete & Computational Geometry, 2023.
[34] Twin-width can be exponential in treewidth
with Hugues Déprés. Journal of Combinatorial Theory, Series B, 2023.
[33] Grundy Coloring & friends, Half-Graphs, Bicliques
with Pierre Aboulker, Eun Jung Kim, and Florian Sikora. Algorithmica, 2023.
[32] Twin-width II: small classes
with Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Combinatorial Theory, 2022.
[31] Twin-width and polynomial kernels
with Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, and Rémi Watrigant. Algorithmica, 2022.
[30] 4 vs 7 sparse undirected unweighted Diameter is SETH-hard at time n4/3
ACM Transactions on Algorithms, 2022.
[29] Twin-width I: tractable FO model checking
with Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Journal of the ACM, 2022.
[28] The Complexity of Mixed-Connectivity
with Sergio Cabello. Annals of Operations Research, 2021.
[27] Metric Dimension Parameterized by Treewidth
with Nidhi Purohit. Algorithmica, 2021.
[26] Parameterized Intractability of Even Set and Shortest Vector Problem
with Arnab Bhattacharyya, László Egri, Suprovat Ghoshal, Karthik C.S., Bingkai Lin, Pasin Manurangsi, and Dániel Marx. Journal of the ACM, 2021.
[25] EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
with Marthe Bonamy, Nicolas Bousquet, Pierre Charbit, Panos Giannopoulos, Eun Jung Kim, Paweł Rzążewski, Florian Sikora, and Stéphan Thomassé. Journal of the ACM, 2021.
[24] The Inverse Voronoi Problem in Graphs II: Trees
with Sergio Cabello, Bojan Mohar, and Hebert Pérez-Rosés. Algorithmica, 2021.
[23] Parameterized Complexity of Independent Set in H-free graphs
with Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, and Rémi Watrigant. Algorithmica, 2020.
[22] Parameterized Hardness of Art Gallery Problems
with Tillmann Miltzow. ACM Transactions on Algorithms, 2020.
[21] The Inverse Voronoi Problem in Graphs I: Hardness
with Sergio Cabello, Bojan Mohar, and Hebert Pérez-Rosés. Algorithmica, 2020.
[20] Designing RNA secondary structures is NP-hard
with Paweł Rzążewski and Florian Sikora. JCB, 2020.
[19] Orthogonal Terrain Guarding is NP-complete
with Panos Giannopoulos. JoCG, 2019.
[18] Generalized feedback vertex set problems on bounded-treewidth graphs
with Nick Brettell, O-joung Kwon, and Dániel Marx. Algorithmica, 2019.
[17] On the Parameterized Complexity of Red-Blue Points Separation
with Panos Giannopoulos and Michael Lampis. JoCG, 2019.
[16] Optimality Program in Segment and String graphs
with Paweł Rzążewski. Algorithmica, 2019.
[15] Fine-grained complexity of coloring unit disks and balls
with Csaba Biró, Dániel Marx, Tillmann Miltzow, and Paweł Rzążewski. JoCG, 2018.
[14] Complexity of grundy coloring and its variants
with Florent Foucaud, Eun Jung Kim, and Florian Sikora. Discrete Applied Mathematics, 2018.
[13] Complexity of Token Swapping and its Variants
with Tillmann Miltzow and Paweł Rzążewski. Algorithmica, 2018.
[12] Time-Approximation Trade-offs for Inapproximable Problems
with Michael Lampis and Vangelis Th. Paschos. JCSS, 2018.
[11] Purely Combinatorial Approximation Algorithms for Maximum k-Vertex Cover in Bipartite Graphs
with Bruno Escoffier, Vangelis Th. Paschos, and Georgios Stamoulis. Discrete Optimization, 2018.
[10] On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism
with Faisal N. Abu-Khzam and Florian Sikora. TCS, 2017.
[9] The Graph Motif problem parameterized by the structure of the input graph
with Florian Sikora. Discrete Applied Mathematics, 2017.
[8] Sparsification and subexponential approximation
with Vangelis Th. Paschos. Acta Informatica, 2017.
[7] Dual parameterization and parameterized approximability of subset graph problems
with Vangelis Th. Paschos. RAIRO, 2017.
[6] Multiparameterizations for max k-set cover and related satisfiability problems
with Vangelis Th. Paschos and Florian Sikora. RAIRO, 2016.
[5] On the Complexity of Connection Games
with Florian Jamain and Abdallah Saffidine. TCS, 2016.
[4] A Note on Edge Isoperimetric Numbers and Regular Graphs
with Florian Sikora. IJFCS, 2016.
[3] Multi-parameter Analysis for Local Graph Partitioning Problems: Using Greediness for Parameterization
with Bruno Escoffier, Vangelis Th. Paschos, and Émeric Tourniaire. Algorithmica, 2015.
[2] On subexponential and fpt-time inapproximability
with Bruno Escoffier, Eun Jung Kim, and Vangelis Th. Paschos. Algorithmica, 2015.
[1] Parameterized (in)approximability of subset problems
with Vangelis Th. Paschos. Operations Research Letters, 2014.

Workshops and other contributions

[9] Twin-width and permutations
with Jaroslav Nešetřil, Patrice Ossona de Mendez, Sebastian Siebertz, and Stéphan Thomassé. EUROCOMB, 2023.
[8] The Importance of Rank in Trick-Taking Card Games
with Abdallah Saffidine.
[7] Fine-grained complexity of coloring unit disks and balls
with Csaba Biró, Dániel Marx, Tillmann Miltzow, and Paweł Rzążewski. EuroCG, 2017.
[6] Parameterized Hardness of Art Gallery Problems
with Tillmann Miltzow. EuroCG, 2016.
[5] An Approximation Algorithm for the Art Gallery Problem
with Tillmann Miltzow. EuroCG, 2016.
[4] Flip Distance to a Non-crossing Perfect Matching
with Tillmann Miltzow. EuroCG, 2016.
[3] Complexité des Jeux (in french)
with Abdallah Saffidine. Invited article in Bulletin de la ROADEF, 2014.
[2] Using greediness for parameterization
ECCO, 2013.
[1] Balance between time complexity and approximation ratio.
ROADEF, 2013.

Last modified: 2024-09-27