6 papers
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…
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…
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…
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…
Graph Reconstruction with Connectivity Queries
Kacper Kluk, Hoang La, Marta Piecyk
We study a problem of reconstruction of connected graphs where the input gives all subsets of size k that induce a connected subgraph. Originally introduced by Bastide et al. (WG 2…