3 papers
cs.DS2026
Parameterized Complexity of Power Network Design: Coordinating Cable Placement is Hard
Thekla Hamm, Bart M. P. Jansen, Faezeh Motiei
We study generalizations of the Steiner Tree problem motivated by the design of power networks. While Steiner Tree asks for a single minimum-cost tree connecting given terminal ver…
cs.CC2026
Search-space Reduction for Boolean MinCSPs via Essential Constraints
Bart M. P. Jansen, Ruben F. A. Verhaegh
For a fixed set of Boolean constraint types, a MinCSP-instance consists of a formula that applies constraints from to a set of $n…
cs.DS2024
Kernelization Dichotomies for Hitting Subgraphs under Structural Parameterizations
Marin Bougeret, Bart M. P. Jansen, Ignasi Sau
For a fixed graph , the -SUBGRAPH HITTING problem consists in deleting the minimum number of vertices from an input graph to obtain a graph without any occurrence of as a…