2026-07-20T05:41:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8534 2024-03-06T10:42:21Z ddc:004 open_access

A Unified Polynomial-Time Algorithm for Feedback Vertex Set on Graphs of Bounded Mim-Width Jaffke, Lars Kwon, O-joung Telle, Jan Arne graph width parameters graph classes feedback vertex set leaf powers We give a first polynomial-time algorithm for (Weighted) Feedback Vertex Set on graphs of bounded maximum induced matching width (mim-width). Explicitly, given a branch decomposition of mim-width w, we give an n^{O(w)}-time algorithm that solves Feedback Vertex Set. This provides a unified algorithm for many well-known classes, such as Interval graphs and Permutation graphs, and furthermore, it gives the first polynomial-time algorithms for other classes of bounded mim-width, such as Circular Permutation and Circular k-Trapezoid 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 tree-width w-1 or path-width w and powers of graphs of clique-width w have mim-width at most w. These results extensively provide new classes of bounded mim-width. 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 mim-width at most 1. Given a tree decomposition of width w-1, a path decomposition of width w, or a clique-width w-expression of a graph G, one can for any value of k find a mim-width decomposition of its k-power in polynomial time, and apply our algorithm to solve Feedback Vertex Set on the k-power in time n^{O(w)}. In contrast to Feedback Vertex Set, we show that Hamiltonian Cycle is NP-complete even on graphs of linear mim-width 1, which further hints at the expressive power of the mim-width parameter. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lars Jaffke and O-joung Kwon and Jan Arne Telle 2018 Is Part Of LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2018.42 urn:nbn:de:0030-drops-85348 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.42 eng https://creativecommons.org/licenses/by/3.0/legalcode