Showing 2025Show all
3 papers · 1 filter
cs.CC2025
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…
cs.DS2025
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…
math.CO2025
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…