Computing hypergraph width measures exactly

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

Authors: Lukas Moll, Siamak Tazari, Marc Thurley 

Publication date: 18 July 2012

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

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).

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

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

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)

Cites Work

• Treewidth Computation and Extremal Combinatorics
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Constraint solving via fractional edge covers
• When is the evaluation of conjunctive queries tractable?
• Hypertree decompositions and tractable queries
• Set partitioning via inclusion-exclusion
• Treewidth and minimum fill-in: Grouping the minimal separators
• Finding induced subgraphs via minimal triangulations
• Exact Algorithms for Treewidth and Minimum Fill-In
• Tractable hypergraph properties for constraint satisfaction and conjunctive queries
• On treewidth and minimum fill-in of asteroidal triple-free graphs

Cited In (8)

• Solving Graph Problems via Potential Maximal Cliques
• Title not available (Why is that?)
• Hyperconsistency width for constraint satisfaction: Algorithms and complexity results
• HyperBench
• Finding optimal triangulations parameterized by edge clique cover
• Computing partial hypergraphs of bounded width
• A revisit of the scheme for computing treewidth and minimum fill-in
• 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)