Abstract: Hypergraph width measures are a class of hypergraph invariants important in studying the complexity of constraint satisfaction problems (CSPs). We present a general exact exponential algorithm for a large variety of these measures. A connection between these and tree decompositions is established. This enables us to almost seamlessly adapt the combinatorial and algorithmic results known for tree decompositions of graphs to the case of hypergraphs and obtain fast exact algorithms. As a consequence, we provide algorithms which, given a hypergraph H on n vertices and m hyperedges, compute the generalized hypertree-width of H in time O*(2^n) and compute the fractional hypertree-width of H in time O(m*1.734601^n).
Recommendations
- Computing partial hypergraphs of bounded width
- Digraph width measures in parameterized algorithmics
- On digraph width measures in parameterized algorithmics
- Hypertree width and related hypergraph invariants
- Hypertree-width and related hypergraph invariants
- Computing the \(k\)-metric dimension of graphs
- Hypergraph computation
- How to compute digraph width measures on directed co-graphs
- Approximating width parameters of hypergraphs with excluded minors
- Tree-Related Widths of Graphs and Hypergraphs
Cites work
- Exact Algorithms for Treewidth and Minimum Fill-In
- Finding induced subgraphs via minimal triangulations
- Hypertree decompositions and tractable queries
- On treewidth and minimum fill-in of asteroidal triple-free graphs
- Set partitioning via inclusion-exclusion
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Tractable hypergraph properties for constraint satisfaction and conjunctive queries
- Treewidth Computation and Extremal Combinatorics
- Treewidth and minimum fill-in: Grouping the minimal separators
- When is the evaluation of conjunctive queries tractable?
Cited in
(12)- Computing optimal hypertree decompositions with SAT
- Solving graph problems via potential maximal cliques: an experimental evaluation of the Bouchitté-Todinca algorithm
- Hyper-T-width and hyper-D-width: Stable connectivity measures for hypergraphs
- Computing partial hypergraphs of bounded width
- Finding optimal triangulations parameterized by edge clique cover
- A revisit of the scheme for computing treewidth and minimum fill-in
- Tree-Related Widths of Graphs and Hypergraphs
- Approximating fractional hypertree width
- HyperBench. A benchmark and tool for hypergraphs and empirical findings
- scientific article; zbMATH DE number 7764113 (Why is no real title available?)
- Approximating fractional hypertree width
- Hyperconsistency width for constraint satisfaction: Algorithms and complexity results
This page was built for publication: Computing hypergraph width measures exactly
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q437685)
