A direct algorithm for the parameterized face cover problem

Abstract

With respect to a given plane graph, G, a face cover is defined as a set of faces whose boundaries collectively contain every vertex in G. It is known that, when k is fixed, finding a cover of size k (if indeed any exist) can be accomplished in polynomial time. Recent improvements to face cover algorithms are based on the theory of fixed-parameter tractability and reductions to planar dominating set. A major goal has been to reduce the time required for branching, which is the most computationally-intensive aspect of fixed-parameter tractable methods. The fastest previously-known method for solving planar dominating set requires branching time O(8kn). The main contribution of this paper is a direct and relatively simple O(5kn) face cover branching algorithm. A direct O(n2) face cover kernelization algorithm is also presented.