2 papers
cs.DS2026
Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
BarıŠCan Esmer, Ariel Kulik, Dániel Marx +2
We generalize the monotone local search approach of Fomin, Gaspers, Lokshtanov and Saurabh [J. ACM 2019], by establishing a connection between parameterized approximation and expon…
cs.CC2025
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
Jacob Focke, Dániel Marx, Fionn Mc Inerney +4
We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets of non-negative integers, a -s…