Showing 2026Show all
2 papers · 1 filter
cs.DS2026
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…
cs.DS2026
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…