ﻻ يوجد ملخص باللغة العربية
The two weighted graph problems Node Multiway Cut (NMC) and Subset Feedback Vertex Set (SFVS) both ask for a vertex set of minimum total weight, that for NMC disconnects a given set of terminals, and for SFVS intersects all cycles containing a vertex of a given set. We design a meta-algorithm that allows to solve both problems in time $2^{O(rw^3)}cdot n^{4}$, $2^{O(q^2log(q))}cdot n^{4}$, and $n^{O(k^2)}$ where $rw$ is the rank-width, $q$ the $mathbb{Q}$-rank-width, and $k$ the mim-width of a given decomposition. This answers in the affirmative an open question raised by Jaffke et al. (Algorithmica, 2019) concerning an XP algorithm for SFVS parameterized by mim-width. By a unified algorithm, this solves both problems in polynomial-time on the following graph classes: Interval, Permutation, and Bi-Interval graphs, Circular Arc and Circular Permutation graphs, Convex graphs, $k$-Polygon, Dilworth-$k$ and Co-$k$-Degenerate graphs for fixed $k$; and also on Leaf Power graphs if a leaf root is given as input, on $H$-Graphs for fixed $H$ if an $H$-representation is given as input, and on arbitrary powers of graphs in all the above classes. Prior to our results, only SFVS was known to be tractable restricted only on Interval and Permutation graphs, whereas all other results are new.
A bipartite graph $G=(A,B,E)$ is ${cal H}$-convex, for some family of graphs ${cal H}$, if there exists a graph $Hin {cal H}$ with $V(H)=A$ such that the set of neighbours in $A$ of each $bin B$ induces a connected subgraph of $H$. Many $mathsf{NP}$-
It has long been known that Feedback Vertex Set can be solved in time $2^{mathcal{O}(wlog w)}n^{mathcal{O}(1)}$ on $n$-vertex graphs of treewidth $w$, but it was only recently that this running time was improved to $2^{mathcal{O}(w)}n^{mathcal{O}(1)}
We prove new complexity results for Feedback Vertex Set and Even Cycle Transversal on $H$-free graphs, that is, graphs that do not contain some fixed graph $H$ as an induced subgraph. In particular, we prove that both problems are polynomial-time sol
We study the recently introduced Connected Feedback Vertex Set (CFVS) problem from the view-point of parameterized algorithms. CFVS is the connected variant of the classical Feedback Vertex Set problem and is defined as follows: given a graph G=(V,E)
By a well known result the treewidth of k-outerplanar graphs is at most 3k-1. This paper gives, besides a rigorous proof of this fact, an algorithmic implementation of the proof, i.e. it is shown that, given a k-outerplanar graph G, a tree decomposit