2026-07-23T05:17:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8177 2024-03-06T10:39:17Z ddc:004 open_access

Multi-Clique-Width Fürer, Martin clique-width parameterized complexity tree-width independent set polynomial graph coloring Multi-clique-width is obtained by a simple modification in the definition of clique-width. It has the advantage of providing a natural extension of tree-width. Unlike clique-width, it does not explode exponentially compared to tree-width. Efficient algorithms based on multi-clique-width are still possible for interesting tasks like computing the independent set polynomial or testing c-colorability. In particular, c-colorability can be tested in time linear in n and singly exponential in c and the width k of a given multi-k-expression. For these tasks, the running time as a function of the multi-clique-width is the same as the running time of the fastest known algorithm as a function of the clique-width. This results in an exponential speed-up for some graphs, if the corresponding graph generating expressions are given. The reason is that the multi-clique-width is never bigger, but is exponentially smaller than the clique-width for many graphs. This gap shows up when the tree-width is basically equal to the multi-clique width as well as when the tree-width is not bounded by any function of the clique-width. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Martin Fürer 2017 Is Part Of LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2017.14 urn:nbn:de:0030-drops-81775 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.14 eng https://creativecommons.org/licenses/by/3.0/legalcode