A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs

Thekla Hamm, Sukanya Pandey, Krisztina Szilágyi · 2026

Read A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs by Thekla Hamm, Sukanya Pandey, Krisztina Szilágyi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-04169.txt.

Introduction

Thekla Hamm, Sukanya Pandey, and Krisztina Szilágyi study the Face Cover Number problem for planar graphs given without a fixed drawing. Terminals are marked vertices, and the question is whether some drawing places all terminals on the edges of at most a chosen number of faces. With a fixed drawing, a polynomial kernel was already known.

A kernel shrinks an instance to a small equivalent one, which speeds later solving. The challenge without a drawing is that no face borders are given in advance. Hamm and her two co-authors build the kernel from the bottom up along an SPR-tree, keeping the traits that matter for face cover at each step. Their result is the first polynomial kernel for the unfixed-drawing version of the problem.

Catalog record

CREATORThekla Hamm, Sukanya Pandey, Krisztina Szilágyi
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE96 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-04169

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs Thekla Hamm, Sukanya Pandey, Krisztina Szilágyi Abstract Given a planar graph, a subset of its vertices called terminals, and k ∈ ℕ k\in\mathbb{N} , the Face Cover Number problem asks whether the terminals lie on the boundaries of at most k k faces of some embedding of the input graph. When a plane graph is given in the input, the problem is known to have a polynomial kernel [ 16 ] . In this paper, we present the first polynomial kernel for Face Cover Number when the input is a planar graph (without a fixed embedding). Our approach overcomes the challenge of not having a predefined set of face boundaries by building a kernel bottom-up on an SPR-tree while preserving the essential properties of the face cover along the way. TU [email protected] by the Austrian Science Fund (J4651-N) during part of this work. RWTH [email protected] Czech Technical University in [email protected] under the project Robotics and advanced industrial production (reg. no. CZ.02.01.01/00/22_008/0004590). {CCSXML} ¡ccs2012¿ ¡concept¿ ¡concept_id¿10003752.10003809.10010052¡/concept_id¿ ¡concept_desc¿Theory of computation Parameterized complexity and exact algorithms¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10002950.10003624.10003633.10010917¡/concept_id¿ ¡concept_desc¿Mathematics of computing Graph algorithms¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡/ccs2012¿ ccs Theory of computation Parameterized complexity and exact algorithms ccs Mathematics of computing Graph algorithms keywords Kernelization, Planar Graphs, SPQR-tree † † runningauthor: T. Hamm, S. Pandey, K. Szilágyi † † copyright: Thekla Hamm, Sukanya Pandey, Krisztina Szilágyi 1 Introduction Problems in network design have been extensively studied on the class of planar graphs. Many of these problems take as input a graph and a subset of its vertices distinguished as terminals, and the goal is to find an optimal subgraph connecting or separating the terminals that satisfies certain constraints. Even when the input is restricted to the class of planar graphs, a large number of these problems remain intractable if the number of terminals is superconstant [ 14 , 28 , 27 , 25 , 8 , 15 , 22 ] . This motivates the quest for further restrictions on the input that may make the problems tractable. Besides bounding the actual number of terminals, one can target weaker restrictions, which impose conditions on the placement of the terminals in the input planar graph. One such restriction could be to require that the terminals lie on the boundary of a single face of the planar input graph. Some well-known NP-hard problems like Steiner Tree , Multiway Cut , and Shortest Disjoint Paths can be solved in polynomial time [ 11 , 2 , 6 , 4 ] in this case. It is therefore natural to wonder: What if the terminals lie on the boundaries of k>1 faces? . The terminal face cover number of a planar graph is the minimum number of faces, over all embeddings, that jointly cover all the terminals. Parameterization by the terminal face cover number was first considered by Erickson et al. in their seminal paper [ 11 ] to design an XP algorithm for Steiner Tree . Recently, it has received a lot of attention, be it for flow and cut problems [ 24 , 23 , 6 , 26 ] , shortest path problems [ 7 , 13 ] , minimum non-crossing walks [ 10 ] , and minimum Steiner tree [ 19 ] . In this paper, we focus on the problem of computing the terminal face cover number. Formally, the problem is defined as follows: Face Cover Number Instance: Planar graph G , T\subseteq V(G) , integer k Question: Does there exist a set of faces of size at most k in some embedding of G that covers all the vertices of T ? Bienstock and Monma [ 3 ] initiated the study of Face Cover Number and showed that it can be solved in FPT time parameterized by k . Their algorithm runs in c^{k}\cdot n time, for some constant c>1 . They also studied a related problem where the input consists of a plane graph, that is, a planar graph with a fixed embedding. We call this problem Embedded Face Cover Number . For this problem, they considered parameterization by the number of terminals t , and gave the first subexponential FPT algorithm with a running time of 2^{\mathcal{O}(\sqrt{t})} . A special case of Embedded Face Cover Number with T=V(G) , parameterized by the face cover number, was studied by Kloks et al. [ 20 ] . They showed that the problem can be solved in time \mathcal{O}^{*}(c^{\sqrt{k}}) . Subsequently, their result was improved by Fernau and Juedes [ 12 ] , whose algorithm runs in time \mathcal{O}^{*}(2^{24.551\sqrt{k}}) and further by Koutsonas and Thilikos [ 21 ] who gave an algorithm with a running time of \mathcal{O}^{*}(2^{10.1\sqrt{k}}) . This problem can be easily reduced to Red-Blue Dominating Set , a variant of Dominating Set on 2-colored graphs. All the aforementioned algorithms indirectly find the minimum face cover of the input plane graph by solving Red-Blue Dominating Set . A direct FPT algorithm for the problem was given by Abu-Khzam et al. [ 1 ] . However, with a running time of \mathcal{O}^{*}(4.6056^{k}) , their algorithm is not subexponential in the parameter. Given the fixed-parameter tractability of both the above problems, a natural line of inquiry is whether there exists a polynomial kernel for the problem. For Embedded Face Cover Number , Garnero et al. [ 16 ] showed that a linear kernel exists by reduction to Red-Blue Dominating Set . Before their work, a quadratic kernel was known to exist due to the result of Kloks et al. [ 20 ] . To date, it was not known whether Face Cover Number has a polynomial kernel. We answer this question in the affirmative by presenting a cubic kernel for the problem parameterized by the face cover number. Theorem 1 . Given an instance (G,T,k) of Face Cover Number , we can produce a kernel (G^{\prime},T^{\prime},k^{\prime}) in polynomial time such that |G^{\prime}|+k^{\prime}\in\mathcal{O}(k^{3}) . Overview of the algorithm. Our approach is to perform dynamic programming over an SPR-tree of the given planar graph. SPR-trees are classic data structures that have often been useful for algorithm design on planar graphs. At a high level, an SPR-tree can be viewed as a tree-structured decomposition of a planar graph into its 3-connected subgraphs. Every node of this tree-structure is associated with a graph called the skeleton of that node. The graph induced at any node is obtained by replacing each of the so-called virtual edges (edges of the skeleton that are not actual edges of the planar graph) by the graphs induced at the children of that node. In this sense, endpoints of virtual edges can be viewed as an “interface” between the graph induced at a node and the graphs induced at its children. Each node of the SPR-tree has a type – S, P or R – depending on the structure of its skeleton. With this in mind, we aim to construct a kernel for Face Cover Number in a leaves-to-root fashion along an SPR-tree of the input graph. For this, a natural attempt at the dynamic programming step is to try to replace parts of the graph that correspond to an SPR-tree rooted at a child

Read the complete text