15 papers
Fatness and Flatness
Arnold Filtser, Hung Le, Nikolas Mählmann +2
Fat minors are the metric analog of graph minors that are tailored to the analysis of metric (edge-weighted) graphs and, more generally, metric spaces having a suitable notion of s…
Induced ErdÅs--Pósa property for long holes, long thetas, and beyond
Jadwiga Czyżewska, Tomáš MasaÅÃk, Marcin Pilipczuk +2
The induced ErdÅs--Pósa property in graphs relates the maximum number of pairwise anti-adjacent copies of an object with the minimum number of neighborhoods required to hit all c…
Sparse induced subgraphs in -free graphs of bounded clique number
Maria Chudnovsky, Jadwiga Czyżewska, Kacper Kluk +2
Many natural computational problems, including e.g. Max Weight Independent Set, Feedback Vertex Set, or Vertex Planarization, can be unified under an umbrella of finding the larges…
Coarse Balanced Separators in Fat-Minor-Free Graphs
Ãdouard Bonnet, Hung Le, Marcin Pilipczuk +1
Fat minors are a coarse analogue of graph minors where the subgraphs modeling vertices and edges of the embedded graph are required to be distant from each other, instead of just b…
Pattern-Sparse Tree Decompositions in -Minor-Free Graphs
Dániel Marx, Marcin Pilipczuk, MichaŠPilipczuk
Given an -minor-free graph and an integer , our main technical contribution is sampling in randomized polynomial time an induced subgraph of and a tree decomposi…
A Polynomial Coreset for Furthest Neighbor in Planar Metrics
Kacper Kluk, Hung Le, Wojciech Nadara +3
A furthest neighbor data structure on a metric space and a set answers the following query: given , output maximizing $\mathr…