A bounded search tree algorithm for parameterized

Abstract

The parameterized complexity of the face cover problem is considered. The input to this problem is a plane graph G with n vertices. The question asked is whether, for a given parameter value k, there exists a set of k or fewer faces whose boundaries collectively cover (contain) every vertex in G . Early attempts achieved run times of O∗(k12) or worse, by reducing the problem into a special form of dominating set, namely red–blue dominating set, restricted to planar graphs.

Here, we consider a direct approach, where some surgical operation is performed on the graph at each branching decision. This paper builds on previous work of the authors and employs a structure theorem of Aksionov et al., with a detailed case analysis, to produce a face cover algorithm that runs in O(k4.6056+n2) time.

We also point to the tight connections with red–blue dominating set on planar graphs via the annotated version of face cover that we consider in our search tree algorithm. Hence, we get both a O(k4.6056+n2) time algorithm for solving red–blue dominating set on planar graphs and a polynomial time algorithm for producing a linear kernel for annotated face cover.