Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs

DOI10.1137/1.9781611977554.CH140MaRDI QIDQ6538673zbMATH OpenFDO

Authors Jacob Focke, Dániel Marx, Fionn Mc Inerney, Daniel Neuen, Govind S. Sankar, Philipp Schepper, Philip Wellnitz

Publication date 14 May 2024

Full work available at URL https://doi.org/10.1137/1.9781611977554.CH140

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cited in

(11)

• Towards tight bounds for the graph homomorphism problem parameterized by cutwidth via asymptotic matrix parameters
• Fundamental problems on bounded-treewidth graphs: the real source of hardness
• A tight Monte-Carlo algorithm for Steiner tree parameterized by clique-width
• Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs. I: Algorithmic results
• Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs. II: Hardness results
• Structural parameterizations for two bounded degree problems revisited
• List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
• Hitting meets packing: how hard can it be?
• Residue domination in bounded-treewidth graphs
• On the complexity of minimum membership dominating set
• Tight bounds for some classical problems parameterized by cutwidth

This page was built for publication: Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6538673)