In this paper we investigate the existence of parameterized algorithms running in subexponential time for two fundamental cyclehitting problems: Feedback Vertex Set and Triangle Hitting. We focus on the class of pseud...
详细信息
ISBN:
(纸本)9783031754081;9783031754098
In this paper we investigate the existence of parameterized algorithms running in subexponential time for two fundamental cyclehitting problems: Feedback Vertex Set and Triangle Hitting. We focus on the class of pseudo-disk graphs, which forms a common generalization of several graph classes where such results exist, like disk graphs and square graphs. In these graphs we show that given a geometric representation FVS can be solved in time 2(O(k9/10 log k))n(O(1)) and TH in time 2(O(k3/4 log k)) n(O(1)).
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 ...
详细信息
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) and an integer k, decide whether there exists FaS dagger V, |F|a parts per thousand currency signk, such that G[Va-F] is a forest and G[F] is connected. We show that Connected Feedback Vertex Set can be solved in time O(2 (O(k)) n (O(1))) on general graphs and in time on graphs excluding a fixed graph H as a minor. Our result on general undirected graphs uses, as a subroutine, a parameterized algorithm for Group Steiner Tree, a well studied variant of Steiner Tree. We find the algorithm for Group Steiner Tree of independent interest and believe that it could be useful for obtaining parameterized algorithms for other connectivity problems.
暂无评论