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

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 of that SPR-tree by an inductively assumed kernel. However, this naïve approach comes with some technical obstacles: how do we replace a subgraph with a kernel in which we are not ensured that the interface to the subgraph remains? On a more fundamental level, this simple idea is doomed to fail because while the face cover number of the kernel may be the same, it might interact differently with the rest of the graph than the subgraph we replace it with (see Figure 1). Consequently, we need to strengthen what we inductively assume of kernels constructed so far and then also demonstrate in each dynamic programming step that these assumptions are satisfied after carrying out the reduction steps. Crucially, our stronger assumptions allow us to preserve the way in which the face cover of the graph induced at any child node interacts with the graph induced at the parent node during kernelization. We call a kernel that satisfies our stronger assumptions a nice kernel, and our target is to dynamically compute such a kernel.

While many parts of our dynamic programming procedure require us to devise reduction rules that are specific to the skeleton and hence the type of node we are considering (S, P or R), some subgraphs that are induced at the children of a node have sufficiently simple face covers. Hence, we can replace them by constant-sized subgraphs and obtain a nice kernel in which we only need to handle subgraphs induced at children that have significantly more complex interactions with the skeleton of the parent.

We refer to the simple subgraphs as terminal-free, unproblematic or semi-problematic components depending on whether they contain terminals, and if so, whether they can be covered optimally using only faces that interact with the rest of the graph. We describe polynomial-time algorithms to recognize each of them. We call the remaining complex subgraphs induced by children problematic. At each node type, the overall strategy is to bound the number of virtual edges that we need to consider by a polynomial in the prospective face cover number $k$. Once we achieve that, we can then reduce the skeleton in a way that we can bound the number of its non-virtual edges in $k$. Both of these are the steps that are the most specific to the node types. Finally, we inductively replace the problematic virtual components by their kernels and any possible remaining non-problematic ones by their constant-size replacements – this last step does not depend on the particular node type.

Concerning the node-type specific arguments, simple reduction rules like edge deletions and contractions can be used at S-nodes and P-nodes. However, such simple reduction rules are difficult to control at R-nodes, which, of all the node types admit the structurally most complex skeletons, namely 3-connected planar graphs. Deleting or contracting edges from a 3-connected planar graph does not, in general, preserve 3-connectivity. This is of great relevance for face cover numbers because, before any reduction, the skeleton has a unique embedding, a property that we cannot easily preserve during reduction. For this reason, during the kernelization for R-nodes, we switch to the embedded setting, and formulate reduction rules that take the initial fixed embedding into account. To transition back to the setting in which we consider a non-embedded graph, we re-establish 3-connectivity by what we call “rigidizing” the embedded nice kernel. While doing so, we take care not to change the sets of terminals of the nice kernel that occur together on a face, and hence obtain a non-embedded nice kernel at R-nodes.

In Section 2, we give necessary definitions and notation. In Section 3, we give formal definitions of terminal-free, unproblematic or semi-problematic and problematic components, and algorithms to distinguish them. Then, in Section 4 we define the notion of a nice kernel and describe the replacements of the components from Section 3, which are not node-type specific. In Section 5, we turn to the actual formulation of the dynamic program. We conclude in Section 6. The omitted proofs are marked with $†$ and can be found in the full version of the paper [17].

We follow standard graph terminology [9]. A graph is a pair $G=(V,E)$, such that $E\subseteq \left(\genfrac{}{}{0pt}{}{V}{2}\right)$. The elements of $V$ are called the vertices of the graph and the elements of $E$ are called edges. The number of vertices of a graph is its order denoted by $n$. A subgraph $G^{\prime }=(V^{\prime },E^{\prime })$ of $G$, written as $G^{\prime }\subseteq G$, is a graph such that $V^{\prime }\subseteq V$ and $E^{\prime }\subseteq E$. $G^{\prime }$ is an induced subgraph of $G$, if for all $x,y\in V^{\prime }$, if $xy\in E$ then $xy\in E^{\prime }$.

A path is a non-empty graph $P=(V^{\prime },E^{\prime })$ of the form $V^{\prime }=\{x_0,x_1,\mathrm{\dots },x_k\}$ and $E^{\prime }=\{x_0{x}_1,\mathrm{\dots },$ $x_{k-1}{x}_k\}$, where all $x_i$ are distinct. The vertices $x_0$ and $x_k$ are called the endpoints of $P$. An induced path is a path in which all the vertices except the endpoints have degree two. The number of edges in a path is its length.

A graph is connected if there is a path between any two vertices in a graph, and disconnected otherwise. A graph is biconnected if there does not exist any vertex whose removal from the graph results in a disconnected graph. Similarly, a graph is called 3-connected if there does not exist a subset of vertices of size two whose removal disconnects the graph.

An SPR-tree is a rooted tree in which each node $t$ is associated with a multigraph called the skeleton of the node. The nodes, and their skeletons, have one of three types:

1. 1.

   S node: These are nodes whose skeleton forms a cycle of three or more vertices.

2. 2.

   P node: These are nodes whose skeleton is a graph with exactly two vertices and at least three edges between them. Such a graph is called a dipole.

3. 3.

   R node: These are nodes whose skeleton forms a 3-connected graph that is not a cycle or a dipole.

Each edge between two nodes $t$ and $t^{\prime }$ of the SPR-tree is associated to one edge with an ordering of its endpoints in the skeleton of $t$ and one edge with an ordering of its endpoints in the skeleton of $t^{\prime }$. Overall, the edge of the skeleton of each node is allowed to be associated to at most one edge of the SPR-tree in this way. These skeleton edges that are associated to SPR-tree edges are called virtual edges. The edges of the skeleton of any node that are not virtual are called real. For the subtree rooted at a node $t$ of the SPR-tree the graph induced by it is inductively defined as follows.

• $\mathrm{■}$

  if $t$ is a leaf, the graph induced by the subtree rooted at $t$ is the skeleton of $t$.

• $\mathrm{■}$

  if $t$ has children $t_1,\mathrm{\dots },t_c$, the graph induced by the subtree rooted at $t$ is the graph arising from the skeleton of $t$ by doing the following for each $i\in [c]$: Insert the graph induced by the subtree rooted at $t_i$; identify the first and second endpoint of the virtual edge in the skeleton of $t_i$ that is associated to $t{t}_i$ with the first and second endpoint respectively of the virtual edge in the skeleton of $t$ that is associated to $t{t}_i$; and lastly, delete the virtual edges corresponding to $t{t}_i$. Intuitively speaking, the graph induced by the subtrees rooted at $t_i$ are “glued-in” in place of the respective virtual edges of the skeleton of $t$.

We say that an SPR-tree is an SPR-tree of the graph that it induces.

For a node $t$ of an arbitrary fixed SPR-tree of $G$, we denote the subgraph induced by the subtree rooted at $t$ by $G_t$. We call the subgraph induced by a subtree rooted at a child of $t$ a virtual component of $G_t$. Let $c_1,c_2$ be the endpoints of the virtual edges associated to $t{t}^{\prime }$ where $t^{\prime }$ is a child of $t$. We call $c_1$ and $c_2$ the corners of the virtual component of $G_t$ associated with $t^{\prime }$. We call the edge $c_1{c}_2$ the corner edge of $G_{t^{\prime }}$. We refer to the virtual component of $G_t$ associated with $t^{\prime }$ plus its corner edge as the enhancement of that virtual component. In an embedding of an enhancement, we call the two faces containing the corner edge external faces and the remaining faces internal faces. If $G_t$ itself has no corners, i.e. $t$ is the root of the SPR-tree, then $G_t$ is equal to its enhancement (we pick an arbitrary edge of $G_t$ and regard it as the corner edge and its endpoints as corners).

A kernelization for a parameterized problem $\mathrm{\Pi }\in {\mathrm{\Sigma }}^{\ast }\times \mathbb{N}$ is an algorithm that takes as input an instance $(I,k)$ of $\mathrm{\Pi }$, runs in time $poly(|I|+k)$ and outputs an instance $(I^{\prime },k^{\prime })$ of $\mathrm{\Pi }$ such that: (1) $(I,k)$ is a YES-instance if and only if $(I^{\prime },k^{\prime })$ is a YES-instance (2) $|I^{\prime }|\le f(k)$, for some computable function $f$, and (3) $k^{\prime }\le g(k)$, for some computable function $g$. The output $(I^{\prime },k^{\prime })$ of a kernelization is referred to as a kernel. We say that $(I^{\prime },k^{\prime })$ is a polynomial kernel if $|I^{\prime }|+k^{\prime }\le poly(k)$.

A drawing of a connected planar graph $G=(V,E)$ is defined as a mapping of the vertices in $V$ to points in ${ℝ}^2$ and edges to simple curves between the points corresponding to its endpoints, such that: (1) distinct edges have distinct pair of endpoints, and (2) the interior of an edge does not contain any vertex or any point of another edge. Given a planar drawing, the (clockwise) cyclic order of edges incident on every vertex is fixed. The set of circular orderings of edges around each vertex is called a rotation system. A (combinatorial) embedding is an equivalence class of planar drawings defined by their rotation systems. We frequently identify vertices and edges with their drawings and embeddings with an arbitrary drawing from its represented equivalence class.

The restrictions of embeddings and drawings to a subgraph of a graph are called subembeddings and subdrawings respectively. Let $G$ be a plane graph and $t$ a node in its SPR-decomposition. Flipping $G_t$ is defined by reversing the the rotation system restricted to $G_t$ (i.e. for the corner vertices, we only reverse edges in $G_t$).

For every drawing $G$ of a planar graph, the inclusion-maximal regions of ${ℝ}^2\setminus G$ are called faces. The unique unbounded face is the outer face, all other faces are inner faces. Let $f$ be a face. We say that a face $f$ covers a vertex $v$ if the drawing of $v$ lies on the boundary of $f$. For the two external faces of the enhancement $G_t$, we define their corresponding faces in $G$ as the faces whose boundaries restricted to $G_t$ are equal. Given a face cover $F$ of $G$, we define the induced face cover $F_t$ of the enhancement of $G_t$ as the set of internal faces of $G_t$ that are in $F$ together with the external faces corresponding to a face in $F$. The embedded face cover number of an embedded graph $G$ with terminals $T\subseteq V(G)$ is the minimum number of faces needed to cover $T$. The face cover number of a graph $G$ with terminals $T\subseteq V(G)$ ($\mathrm{fcn}(G)=\mathrm{fcn}(G,T)$) is the minimum number of faces over all embeddings of $G$ that cover the terminals of $G$.

By the fact that for $r$, $G_r$ has no corners and $G=G_r$ coincides with its enhancement, (K1)–(K3) are obsolete or equivalent to expressing instance equivalence of $G$ and $K$ as instances of Face Cover Number.

Moreover, by (K4) there is a constant $c$ such that $|V(K)|\le \frac{1}{c}{(k-2)}^3$ where $k$ is the face cover number of $G$ (and hence also of $K$). This shows that $K$ is a cubic kernel for $G$ as an instance of Face Cover Number. $◀$

The next reduction rules replace “simple” virtual components by constant-sized graphs.

We call the above graph a terminal-subdivided edge.

As defined above, let $t$ be a node of the SPR-tree of $G$ and let $G_t$ be its enhancement.

Next, we show that inductively replacing nice kernels for problematic virtual components yields a nice kernel.

Firstly, note that the replacement does not affect the skeleton of $t$, so the corner vertices and corner edge of $G_t$ are preserved, i.e. (K1) is satisfied. Let $c_1,c_2$ be the corner vertices of $C$ and let $C^{\prime }$ be the enhancement of $C$.

Let us now show (K2). Let $i\in \{0,1,2\}$. Fix an embedding $ℱ$ of $G_t$ witnessing ${\mathrm{fcn}}_i(G_t,T)$ and let $F$ be the corresponding face cover. We aim to construct a face cover $\tilde{F}$ of $\widetilde{G_t}$ from $F$. Informally, we partition $F$ into two sets, $F_C$ and $F_U$, where $F_U$ is the set of faces unaffected by the replacement of $C$ by $\tilde{C}$, and $F_C$ contains the remaining faces of $F$. Using the fact that $\tilde{C}$ is a nice kernel for $C$, we construct a face cover ${\tilde{F}}_{C^{\prime }}$ of $\tilde{C}$. The face cover $\tilde{F}$ will contain the faces in $F_U$ and the faces corresponding to ${\tilde{F}}_{C^{\prime }}$.

Formally, we define $F_U=\{f\in F:f\cap V(C)\subseteq \{c_1,c_2\}\}$. In other words, $F_U$ contains faces in $F$ that are disjoint from $C$ except possibly for its corner vertices. Let $F_C=F\setminus F_U$. The faces in $F_C$ correspond to faces of $C^{\prime }$: those that are completely contained in $C$ correspond to internal faces of $C$ (with the same set of vertices) and those that contain vertices outside of $C$ correspond to the external faces of $C^{\prime }$. Let $F_{C^{\prime }}$ be the set of faces of $C^{\prime }$ corresponding to $F_C$. Note that $F_{C^{\prime }}$ is a face cover of $C^{\prime }$ covering all terminals in $T\cap V(C)$ except possibly for $c_1,c_2$ (as these vertices may be covered by faces in $F_U$). Let $j\in \{0,1,2\}$ be the number of faces in $F_{C^{\prime }}$ corresponding to external faces of $C^{\prime }$. We distinguish two cases depending on the value of $j$:

in this case, all terminals of $C^{\prime }$ are covered by a face in $F_{C^{\prime }}$. By an exchange argument, it is easy to see that $F_{C^{\prime }}$ is optimal, i.e. it witnesses ${\mathrm{fcn}}_j(C,T\cap V(C))$, so we have ${\mathrm{fcn}}_j(C,T\cap V(C))=|F_{C^{\prime }}|=|F_C|$. Fix an embedding of $\tilde{C}$ witnessing ${\mathrm{fcn}}_j(\tilde{C},T^{\prime }\cap V(\tilde{C}))$ and let ${\tilde{F}}_{C^{\prime }}$ be the corresponding face cover. We set $T_1=T$, $T_1^{\prime }=T^{\prime }$.

in this case, $c_1$ and $c_2$ might not be covered by a face in $F_{C^{\prime }}$. Let $T_1,T_1^{\prime }$ be sets of terminals obtained by removing the corner vertices not covered by a face in $F_C$ from $T$ and $T^{\prime }$ respectively. Similarly, we have that ${\mathrm{fcn}}_0(C,T_1^{\prime }\cap V(C))=|F_C|$. Fix an embedding of $\tilde{C}$ witnessing ${\mathrm{fcn}}_0(\tilde{C},T_1^{\prime }\cap V(\tilde{C}))$ and let ${\tilde{F}}_{C^{\prime }}$ be the corresponding face cover.

We embed $\widetilde{G_t}$ by using the above embedding of $\tilde{C}$ and leaving the remaining part of $\widetilde{G_t}$ the same as in $ℱ$. If $j=1$, we embed $\tilde{C}$ inside $\widetilde{G_t}$ such that the external face of $\tilde{C}$ that belongs to $F_{C^{\prime }}$ corresponds to the face in $F_C$ containing $c_1,c_2$. If $j\in \{0,2\}$ we can embed $\tilde{C}$ with an arbitrary choice of external faces (i.e. the way it is “flipped” inside $\widetilde{G_t}$ is irrelevant). Now we have obtained an embedding of $\widetilde{G_t}$.

We define ${\tilde{F}}_C$ as the set of faces of $\widetilde{G_t}$ corresponding to ${\tilde{F}}_{C^{\prime }}$. Note that the faces in $F_U$ are faces of $\widetilde{G_t}$ (since they do not contain vertices from $V(C)\setminus \{c_1,c_2\}$) and that $F_U\cap {\tilde{F}}_C=\mathrm{\varnothing }$.

We claim that $\tilde{F}=F_U\cup {\tilde{F}}_C$ is a face cover of $\widetilde{G_t}$. Clearly, all terminals except $c_1,c_2$ are covered: those in $V(\tilde{C})$ are covered by a face in ${\tilde{F}}_C$, and the others are covered by a face in $F_U$. The vertices $c_1$ and $c_2$ (if they are terminals) are covered by a face in ${\tilde{F}}_C$ if they were covered by a face in $F_C$, and otherwise they are covered by a face in $F_U$. Thus $\tilde{F}$ is a face cover of $\widetilde{G_t}$. It remains to show the size bounds.

If $|F|\le k$, then we have ${\mathrm{fcn}}_j(C,T_1\cap V(C))=|F_C|\le k$, so $|{\tilde{F}}_C|={\mathrm{fcn}}_j(\tilde{C},T_1^{\prime }\cap V(\tilde{C}))={\mathrm{fcn}}_j(C,T_1\cap V(C))$ by (K2) and (K3). Thus $|{\tilde{F}}_C|=|F_C|$, so $|\tilde{F}|=|F|$. If $|F|>k$, we distinguish two cases. If $|F_C|>k$, then $|{\tilde{F}}_C|>k$, so $|\tilde{F}|>k$. If $|F_C|\le k$, then $|{\tilde{F}}_C|=|F_C|$, so $|\tilde{F}|=|F|>k$.

To show (K3), we remove one or both corner vertices from $T$ and $T^{\prime }$ and proceed the same as the case $j=0$. $◀$

Does there exist a linear kernel for Face Cover Number?

Addressing this question likely necessitates a deeper understanding of the structural properties of 3-connected planar graphs.

Following the fixed-parameter tractable (FPT) algorithm developed by Bienstock and Monma [3], there have been no subsequent improvements for the non-embedded case. In particular, no subexponential-time algorithm is currently known for Face Cover, prompting the following question:

Is there an algorithm that solves Face Cover in $2^{𝒪(\sqrt{k})}$ time, where $k$ is the face cover number?

It is important to note that while bidimensionality theory applies to the variant with $T=V(G)$, the general form of the problem does not fall within this framework. Addressing Open Question 2 will therefore require the development of novel algorithmic ideas beyond existing techniques.