7 papers
Exploring Minimal Blocking Sets for Kernelization Lower Bounds for -Minor Deletion
Ahmed Ghazy, Jakob Greilhuber, Tim A. Hartmann
For Vertex Cover, a minimal blocking set of a graph is an inclusion-wise minimal vertex set contained in no minimum vertex cover of . Bougeret et al. [SIDMA 2022] showed tha…
A Uniform Algorithm for Strict NP on Bounded-Treedepth Graphs
Thomas Depian, Robert Ganian, Jakob Greilhuber +2
A classical well-quasi-ordering result guarantees the existence of non-uniform linear-time algorithms for all problems in Strict NP on relational structures of bounded treedepth; h…
Faster Exponential Algorithms for Multi-Machine Scheduling Problems
Anubhav Dhar, Anita Dürr, Ahmed Ghazy +2
Minimizing the weighted completion times () and weighted number of tardy jobs () on multiple identical machines are two classical NP-har…
Where Treewidth and Pathwidth Diverge: Towards a Uniform Kernel for Pathwidth- Deletion
Ahmed Ghazy, Jakob Greilhuber, Tim A. Hartmann +1
For a constant , Pathwidth- Deletion is the problem of deciding whether, for a given graph and integer , there is a set of size at most su…
A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth
Jakob Greilhuber, Roohani Sharma
In this work we study a classic generalization of the Vertex Cover (VC) problem, called the Component Order Connectivity (COC) problem. In COC, given an undirected graph , integ…
The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
Jakob Greilhuber, Dániel Marx
For fixed sets of non-negative integers, the -domination framework introduced by Telle [Nord. J. Comput. 1994] captures many classical graph problems. For a graph $G…
Residue Domination in Bounded-Treewidth Graphs
Jakob Greilhuber, Philipp Schepper, Philip Wellnitz
For the vertex selection problem -DomSet one is given two fixed sets and of integers and the task is to decide whether we can select vertices of the input graph such…