A SAT Approach to Clique-Width

DOI10.1145/2736696zbMath1354.68240arXiv1304.5498OpenAlexW1906408003MaRDI QIDQ2946763

Marijn J. H. Heule, Stefan Szeider

Publication date: 17 September 2015

Published in: ACM Transactions on Computational Logic, Theory and Applications of Satisfiability Testing – SAT 2013 (Search for Journal in Brave)

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

zbMATH Keywords

satisfiabilityclique-widthSAT encodingSAT solvercardinality constraintlinear clique-width\(k\)-expression

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (8)

Induced betweenness in order-theoretic trees ⋮ On quasi-planar graphs: clique-width and logical description ⋮ Computing optimal hypertree decompositions with SAT ⋮ Bounding clique-width via perfect graphs ⋮ The behavior of clique-width under graph operations and graph transformations ⋮ A SAT Approach to Branchwidth ⋮ Computing properties of stable configurations of thermodynamic binding networks ⋮ A characterisation of clique-width through nested partitions

Uses Software

• MiniSat
• clasp
• Sugar
• Lingeling

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial-time recognition of clique-width \(\leq 3\) graphs
• Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs
• A combinatorial optimization algorithm for solving the branchwidth problem
• A survey of the algorithmic aspects of modular decomposition
• New plain-exponential time classes for graph homomorphism
• Boolean-width of graphs
• Graphs of linear clique-width at most 3
• Compiling finite linear CSP into SAT
• \(k\)-NLC graphs and polynomial algorithms
• Constrained-path labellings on graphs of bounded clique-width
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• Approximating clique-width and branch-width
• On the relationship between NLC-width and linear NLC-width
• The relative clique-width of a graph
• Linear Rank-Width and Linear Clique-Width of Trees
• Finding Good Decompositions for Dynamic Programming on Dense Graphs
• Conflict Anticipation in the Search for Graph Automorphisms
• Rank-width of random graphs
• Computing the Clique-Width of Large Path Powers in Linear Time via a New Characterisation of Clique-Width
• Empirical Study of the Anatomy of Modern Sat Solvers
• Towards an Optimal CNF Encoding of Boolean Cardinality Constraints
• Clique-Width is NP-Complete
• Encoding Treewidth into SAT
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• On the Relationship Between Clique-Width and Treewidth
• Theory and Applications of Satisfiability Testing
• Graph-Theoretic Concepts in Computer Science
• Principles and Practice of Constraint Programming – CP 2004
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic

This page was built for publication: A SAT Approach to Clique-Width