Authors: Sigve Hortemo Sæther Jan Arne Telle
Publish Date: 2015/07/21
Volume: 75, Issue: 1, Pages: 218-253
Abstract
Many hard graph problems can be solved efficiently when restricted to graphs of bounded treewidth and more generally to graphs of bounded cliquewidth But there is a price to be paid for this generality exemplified by the four problems MaxCut Graph Coloring Hamiltonian Cycle and Edge Dominating Set that are all FPT parameterized by treewidth but none of which can be FPT parameterized by cliquewidth unless FPT = W1 as shown by Fomin et al Proceedings of the twentyfirst annual ACMSIAM symposium on discrete algorithms pp 493–502 2010a SIAM J Comput 3951941–1956 2010b We therefore seek a structural graph parameter that shares some of the generality of cliquewidth without paying this price Based on splits branch decompositions and the work of Vatshelle New width parameters of graphs The University of Bergen 2012 on maximum matchingwidth we consider the graph parameter smwidth which lies between treewidth and cliquewidth Some graph classes of unbounded treewidth like distancehereditary graphs have bounded smwidth We show that MaxCut Graph Coloring Hamiltonian Cycle and Edge Dominating Set are all FPT parameterized by smwidth
Keywords: