5 papers
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…
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…
Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
Kacper Kluk, Jesper Nederlof
We give unconditional parameterized complexity lower bounds on pure dynamic programming algorithms - as modeled by tropical circuits - for connectivity problems such as the Traveli…
On coarse tree decompositions and coarse balanced separators
Tara Abrishami, Jadwiga Czyżewska, Kacper Kluk +3
It is known that there is a linear dependence between the treewidth of a graph and its balanced separator number: the smallest integer such that for every weighing of the verti…
Faster diameter computation in graphs of bounded Euler genus
Kacper Kluk, Marcin Pilipczuk, MichaÅ Pilipczuk +1
We show that for any fixed integer , there exists an algorithm that computes the diameter and the eccentricies of all vertices of an input unweighted, undirected -vert…