We prove that for any epsilon > 0 there exists an integer n(epsilon) such that the pathwidth of every cubic (or 3-regular) graph on n > n(epsilon) vertices is at most (1/6 + epsilon)n. Based on this bound we imp...
详细信息
We prove that for any epsilon > 0 there exists an integer n(epsilon) such that the pathwidth of every cubic (or 3-regular) graph on n > n(epsilon) vertices is at most (1/6 + epsilon)n. Based on this bound we improve the worst case time analysis for a number of exact exponential algorithms on graphs of maximum vertex degree three. (c) 2005 Elsevier B.V. All rights reserved.
The problem of finding a minimum feedback vertex set has many applications and its history can be traced back to the early '60s (see the survey of Festa at al. [2]). It is also one of the classical NP-complete pro...
详细信息
ISBN:
(纸本)3540390987
The problem of finding a minimum feedback vertex set has many applications and its history can be traced back to the early '60s (see the survey of Festa at al. [2]). It is also one of the classical NP-complete problems from Karp's list [5]. There is quite a dramatic story of obtaining faster and faster parameterized algorithms with a chain of improvements (see e.g. [7]) concluding with 2(O(k))n(O(1))-time algorithms obtained independently by different research groups [1,4]. A feedback vertex set of a graph on n vertices can be trivially found in time 0(2 n n) by trying all possible vertex subsets. For a long time, despite attacks of many researchers, no faster exponential time algorithm was known. Very recently Razgon [8] broke the 2(n) barrier with an O(1.8899(n)) time algorithm. The algorithm of Razgon is based on the Branch & Reduce paradigm and its analysis is nice and clever. In this paper we show how to find a minimum feedback vertex set in time O(1.7548(n)). Our improvement is based on Razgon's idea of measuring the progress of the branching algorithm. The most significant improvement in the running time of our algorithm is due to a new branching rule which is based on Proposition 2. This rule works nicely except one case, which, luckily, can be reduced to finding an independent set of maximum size.
暂无评论