Computing hypergraph width measures exactly

DOI10.1016/J.IPL.2011.12.002zbMATH Open1242.05058OpenAlexW1979091081MaRDI QIDQ437685FDOQ437685

Authors Lukas Moll, Siamak Tazari, Marc Thurley 

Publication date 18 July 2012

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1106.4719

zbMATH Keywords

graph algorithmsexact exponential algorithmsdesign of algorithmsfractional hypertree-widthgeneralized hypertree-width

Mathematics Subject Classification ID

Applications of graph theory (05C90) Trees (05C05) Hypergraphs (05C65)

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)

• Title not available (Why is no real title available?)
• Hyperconsistency width for constraint satisfaction: Algorithms and complexity results
• 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
• Finding optimal triangulations parameterized by edge clique cover
• Approximating fractional hypertree width
• Approximating fractional hypertree width
• Computing partial hypergraphs of bounded width
• A revisit of the scheme for computing treewidth and minimum fill-in
• HyperBench. A benchmark and tool for hypergraphs and empirical findings
• Computing optimal hypertree decompositions with SAT
• Tree-Related Widths of Graphs and Hypergraphs

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)