dc.contributor.author | Duarte, Gabriel | |
dc.contributor.author | Oliveira, Mateus De Oliveira | |
dc.contributor.author | Souza, Uéverton S. | |
dc.date.accessioned | 2022-02-17T13:09:37Z | |
dc.date.available | 2022-02-17T13:09:37Z | |
dc.date.created | 2021-09-29T16:39:26Z | |
dc.date.issued | 2021 | |
dc.identifier.issn | 1868-8969 | |
dc.identifier.uri | https://hdl.handle.net/11250/2979722 | |
dc.description.abstract | Clique-width and treewidth are two of the most important and useful graph parameters, and several problems can be solved efficiently when restricted to graphs of bounded clique-width or treewidth. Bounded treewidth implies bounded clique-width, but not vice versa. Problems like Longest Cycle, Longest Path, MaxCut, Edge Dominating Set, and Graph Coloring are fixed-parameter tractable when parameterized by the treewidth, but they cannot be solved in FPT time when parameterized by the clique-width unless FPT = W[1], as shown by Fomin, Golovach, Lokshtanov, and Saurabh [SIAM J. Comput. 2010, SIAM J. Comput. 2014]. For a given problem that is fixed-parameter tractable when parameterized by treewidth, but intractable when parameterized by clique-width, there may exist infinite families of instances of bounded clique-width and unbounded treewidth where the problem can be solved efficiently. In this work, we initiate a systematic study of the parameters co-treewidth (the treewidth of the complement of the input graph) and co-degeneracy (the degeneracy of the complement of the input graph). We show that Longest Cycle, Longest Path, and Edge Dominating Set are FPT when parameterized by co-degeneracy. On the other hand, Graph Coloring is para-NP-complete when parameterized by co-degeneracy but FPT when parameterized by the co-treewidth. Concerning MaxCut, we give an FPT algorithm parameterized by co-treewidth, while we leave open the complexity of the problem parameterized by co-degeneracy. Additionally, we show that Precoloring Extension is fixed-parameter tractable when parameterized by co-treewidth, while this problem is known to be W[1]-hard when parameterized by treewidth. These results give evidence that co-treewidth is a useful width parameter for handling dense instances of problems for which an FPT algorithm for clique-width is unlikely to exist. Finally, we develop an algorithmic framework for co-degeneracy based on the notion of Bondy-Chvátal closure. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | Schloss Dagstuhl, Leibniz-Zentrum für Informatik | en_US |
dc.rights | Navngivelse 4.0 Internasjonal | * |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/deed.no | * |
dc.title | Co-Degeneracy and Co-Treewidth: Using the Complement to Solve Dense Instances | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright Gabriel L. Duarte, Mateus de Oliveira Oliveira, and Uéverton S. Souza | en_US |
dc.source.articlenumber | 42 | en_US |
cristin.ispublished | true | |
cristin.fulltext | original | |
cristin.qualitycode | 1 | |
dc.identifier.doi | 10.4230/LIPIcs.MFCS.2021.42 | |
dc.identifier.cristin | 1940808 | |
dc.source.journal | Leibniz International Proceedings in Informatics | en_US |
dc.source.pagenumber | 42:1-42:17 | en_US |
dc.relation.project | Norges forskningsråd: 288761 | en_US |
dc.identifier.citation | Leibniz International Proceedings in Informatics. 2021, 202, 42:1-42:17, 42. | en_US |
dc.source.volume | 202 | en_US |