Jaffke, Lars ;
Kwon, Ojoung ;
Telle, Jan Arne
A Unified PolynomialTime Algorithm for Feedback Vertex Set on Graphs of Bounded MimWidth
Abstract
We give a first polynomialtime algorithm for (Weighted) Feedback Vertex Set on graphs of bounded maximum induced matching width (mimwidth). Explicitly, given a branch decomposition of mimwidth w, we give an n^{O(w)}time algorithm that solves Feedback Vertex Set. This provides a unified algorithm for many wellknown classes, such as Interval graphs and Permutation graphs, and furthermore, it gives the first polynomialtime algorithms for other classes of bounded mimwidth, such as Circular Permutation and Circular kTrapezoid graphs for fixed k. In all these classes the decomposition is computable in polynomial time, as shown by Belmonte and Vatshelle [Theor. Comput. Sci. 2013].
We show that powers of graphs of treewidth w1 or pathwidth w and powers of graphs of cliquewidth w have mimwidth at most w. These results extensively provide new classes of bounded mimwidth. We prove a slight strengthening of the first statement which implies that, surprisingly, Leaf Power graphs which are of importance in the field of phylogenetic studies have mimwidth at most 1. Given a tree decomposition of width w1, a path decomposition of width w, or a cliquewidth wexpression of a graph G, one can for any value of k find a mimwidth decomposition of its kpower in polynomial time, and apply our algorithm to solve Feedback Vertex Set on the kpower in time n^{O(w)}.
In contrast to Feedback Vertex Set, we show that Hamiltonian Cycle is NPcomplete even on graphs of linear mimwidth 1, which further hints at the expressive power of the mimwidth parameter.
BibTeX  Entry
@InProceedings{jaffke_et_al:LIPIcs:2018:8534,
author = {Lars Jaffke and Ojoung Kwon and Jan Arne Telle},
title = {{A Unified PolynomialTime Algorithm for Feedback Vertex Set on Graphs of Bounded MimWidth}},
booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
pages = {42:142:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770620},
ISSN = {18688969},
year = {2018},
volume = {96},
editor = {Rolf Niedermeier and Brigitte Vall{\'e}e},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8534},
URN = {urn:nbn:de:0030drops85348},
doi = {10.4230/LIPIcs.STACS.2018.42},
annote = {Keywords: graph width parameters, graph classes, feedback vertex set, leaf powers}
}
27.02.2018
Keywords: 

graph width parameters, graph classes, feedback vertex set, leaf powers 
Seminar: 

35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Issue date: 

2018 
Date of publication: 

27.02.2018 