115 citations · 430 across the 53 of their papers we have counts for
61 papers
Lossy Kernelization for (Implicit) Hitting Set Problems
Fedor V. Fomin, Tien-Nam Le, Daniel Lokshtanov +3
We re-visit the complexity of kernelization for the -Hitting Set problem. This is a classic problem in Parameterized Complexity, which encompasses several other of the most well…
Maximum Independent Set when excluding an induced minor: and
Édouard Bonnet, Julien Duron, Colin Geniet +2
Dallard, Milanič, and Štorgel [arXiv '22] ask if for every class excluding a fixed planar graph as an induced minor, Maximum Independent Set can be solved in polynomial time, a…
Clique covers of H-free graphs
Tung Nguyen, Alex Scott, Paul Seymour +1
It takes cliques to cover all the edges of a complete bipartite graph , but how many cliques does it take to cover all the edges of a graph if has no $…
Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
Marthe Bonamy, Édouard Bonnet, Hugues Déprés +5
A graph is -free if it does not contain pairwise vertex-disjoint and non-adjacent cycles. We prove that "sparse" (here, not containing large complete bipartite g…
Twin-width VII: groups
Édouard Bonnet, Colin Geniet, Romain Tessera +1
Twin-width is a recently introduced graph parameter with applications in algorithmics, combinatorics, and finite model theory. For graphs of bounded degree, finiteness of twin-widt…
Twin-width VIII: delineation and win-wins
Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim +3
We introduce the notion of delineation. A graph class is said delineated if for every hereditary closure of a subclass of , it holds that $\ma…