Clique-width minimization is NP-hard
(2006)
Presentation / Conference Contribution
Fellows, M. R., Rosamond, F. A., Rotics, U., & Szeider, S. (2006, May). Clique-width minimization is NP-hard. Presented at 38th Annual ACM Symposium on Theory of Computing, Seattle, Washington, USA
Clique-width is a graph parameter that measures in a certain sense the complexity of a graph. Hard graph problems (e.g., problems expressible in Monadic Second Order Logic with second-order quantification on vertex sets, that includes NP-hard problem... Read More about Clique-width minimization is NP-hard.