[Back]


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.