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 m…