4 papers
Optimal Path Partitions in Subcubic and Almost-subcubic Graphs
Tomáš MasaÅÃk, MichaÅ WÅodarczyk, Mehmet Akif Yıldız
We consider the problem of partitioning the edges of a graph into as few paths as possible. This is a~subject of the classic conjecture of Gallai and a recurring topic in combinato…
Protrusion Decompositions Revisited: Uniform Lossy Kernels for Reducing Treewidth and Linear Kernels for Hitting Disconnected Minors
Roohani Sharma, MichaÅ WÅodarczyk
Let F be a finite family of graphs. In the F-Deletion problem, one is given a graph G and an integer k, and the goal is to find k vertices whose deletion results in a graph with no…
Going Beyond Surfaces in Diameter Approximation
MichaÅ WÅodarczyk
Calculating the diameter of an undirected graph requires quadratic running time under the Strong Exponential Time Hypothesis and this barrier works even against any approximation b…
Losing Treewidth In The Presence Of Weights
MichaÅ WÅodarczyk
In the Weighted Treewidth- Deletion problem we are given a node-weighted graph and we look for a vertex subset of minimum weight such that the treewidth of is at…