Talks and Poster Presentations (with Proceedings-Entry):
M. Heule, St. Szeider:
"A SAT Approach to Clique-Width";
Talk: International Conference on Theory and Applications of Satisfiability Testing (SAT),
Helsinki, Finland;
2013-07-08
- 2013-07-12; in: "Theory and Applications of Satisfiability Testing - SAT 2013",
M. Järvisalo, A. Van Gelder (ed.);
Springer / LNCS,
7962
(2013),
ISBN: 978-3-642-39070-8;
318
- 334.
English abstract:
Clique-width is a graph invariant that has been widely studied in combinatorics and computer science. However, computing the clique-width of a graph is an intricate problem, the exact clique-width is not known even for very small graphs. We present a new method for computing the clique-width of graphs based on an encoding to propositional satisfiability (SAT) which is then evaluated by a SAT solver. Our encoding is based on a reformulation of clique-width in terms of partitions that utilizes an efficient encoding of cardinality constraints. Our SAT-based method is the first to discover the exact clique-width of various small graphs, including famous graphs from the literature as well as random graphs of various density. With our method we determined the smallest graphs that require a small pre-described clique-width.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-642-39071-5
Related Projects:
Project Head Stefan Szeider:
The Parameterized Complexity of Reasoning Problems
Created from the Publication Database of the Vienna University of Technology.