3 years ago

A unified polynomial-time algorithm for Feedback Vertex Set on graphs of bounded mim-width.

Jan Arne Telle, Lars Jaffke, O-joung Kwon

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^{\mathcal{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, Circular $k$-Trapezoid and Dilworth-$k$ 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$ and powers of graphs of clique-width $w$ have mim-width at most $w$. These results extensively provide new classes of bounded mim-width. The first result 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$ 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^{\mathcal{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.

Publisher URL: http://arxiv.org/abs/1710.07148

DOI: arXiv:1710.07148v1

You might also like
Discover & Discuss Important Research

Keeping up-to-date with research can feel impossible, with papers being published faster than you'll ever be able to read them. That's where Researcher comes in: we're simplifying discovery and making important discussions happen. With over 19,000 sources, including peer-reviewed journals, preprints, blogs, universities, podcasts and Live events across 10 research areas, you'll never miss what's important to you. It's like social media, but better. Oh, and we should mention - it's free.

  • Download from Google Play
  • Download from App Store
  • Download from AppInChina

Researcher displays publicly available abstracts and doesn’t host any full article content. If the content is open access, we will direct clicks from the abstracts to the publisher website and display the PDF copy on our platform. Clicks to view the full text will be directed to the publisher website, where only users with subscriptions or access through their institution are able to view the full article.