Fundamental problems on bounded-treewidth graphs: the real source of hardness

DOI10.4230/LIPICS.ICALP.2024.34MaRDI QIDQ6875174zbMATH OpenFDO

Authors Barış Can Esmer, Jacob Focke, Dániel Marx, Paweł Rzążewski

Publication date 14 January 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2024.34

zbMATH Keywords

dominating setedge deletionhubparameterized complexityset cover hypothesisstrong exponential time hypothesistight boundstreewidthtriangle packingtriangle partitionvertex coloringvertex deletion

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A framework for parameterized subexponential algorithms for generalized cycle hitting problems on planar graphs
• A survey of parameterized algorithms and the complexity of edge modification
• A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank
• Anti-factor is FPT parameterized by treewidth and list size (but counting is hard)
• Component order connectivity and vertex degrees
• Component order connectivity in directed graphs
• Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Exact covers via determinants
• Fast Algorithms for Join Operations on Tree Decompositions
• Faster parameterized algorithms for two vertex deletion problems
• Finding large set covers faster via the representation method
• Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs
• Fine-grained parameterized complexity analysis of graph coloring problems
• Finer tight bounds for coloring on clique-width
• scientific article; zbMATH DE number 7228418 (Why is no real title available?)
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• scientific article; zbMATH DE number 1472195 (Why is no real title available?)
• scientific article; zbMATH DE number 6857816 (Why is no real title available?)
• scientific article; zbMATH DE number 7651213 (Why is no real title available?)
• scientific article; zbMATH DE number 7720021 (Why is no real title available?)
• scientific article; zbMATH DE number 7788352 (Why is no real title available?)
• Known algorithms on graphs of bounded treewidth are probably optimal
• On component order edge connectivity of a complete bipartite graph.
• On problems as hard as CNF-SAT
• On the complexity of k-SAT
• Optimal dynamic program for r-domination problems over tree decompositions
• Parameterized algorithms
• Partitioning into sets of bounded cardinality
• Structural parameters, tight bounds, and approximation for \((k, r)\)-center
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs
• Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus
• Towards exact structural thresholds for parameterized complexity
• Which problems have strongly exponential complexity?

Cited in

(2)

• Generalized graph packing problems parameterized by treewidth
• Tight bounds for some classical problems parameterized by cutwidth

This page was built for publication: Fundamental problems on bounded-treewidth graphs: the real source of hardness

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