Determining the Outerthickness of Graphs Is NP-Hard

Guy (1974) [16] defined the outerthickness of a graph $G$ as the minimum number of parts in an edge partition of $G$ such that each part induces an outerplanar subgraph; that is, a planar graph admitting an embedding in the plane in which every node lies on the outer face. Outerthickness is an analogue of thickness, except that each part is required to be outerplanar rather than merely planar. Although Mansfield (1983) proved that determining the thickness of a graph is NP-hard [24], the complexity of determining the outerthickness has remained unsettled [2, 3, 18, 23, 27, 28, 29, 30].

The algorithmic study of outerthickness is motivated in part by a conjecture of Chartrand et al. (1971) [9], who proposed, among other things, that every planar graph admits an edge partition into two outerplanar graphs; equivalently, that every planar graph has outerthickness at most 2. Elmallah and Colbourn (1988) [13] cited this conjecture and addressed it for 4-node-connected planar graphs by presenting an algorithm that produces such a partition into two outerplanar subgraphs. Although they did not explicitly analyze the running time, using the state of the art of the required subroutines at the time [20, 15], their algorithm can be implemented in $O(n^3)$ time, where $n$ denotes the number of nodes in the input graph (and we use this convention throughout the paper).

Subsequently, Heath (1991) claimed a proof of Chartrand et al.’s conjecture and gave an $O(n^2\log n)$-time algorithm to partition the edges of any planar graph into at most two outerplanar graphs [17]. Later, Gonçalves (2005) established the same statement with an optimal $O(n)$-time construction [14]. It is worth noting that Gonçalves remarked that some earlier claimed proofs were later found to be incorrect, and subsequent work attribute the resolution of Chartrand et al.’s conjecture to Gonçalves [11, 32, 10, 4].

Unlike the substantial progress on planar graphs, there has been little progress on determining outerthickness for general graphs. Mäkinen and Poranen (2004) conjectured in [27, 29] that deciding the outerthickness of a general graph is NP-hard. Since then, the open status of this problem has been repeatedly highlighted in subsequent work [28, 3, 23, 30], and was reiterated as recently as 2023 by Hlinený and Masarík [18] and 2024 by Balko et al. [2]. We further note that Balko et al. prove NP-hardness for computing the uncrossed number under the assumption that computing outerthickness is NP-hard [2].

In this paper, we settle the computational complexity of determining the outerthickness of general graphs, a question that has remained open since outerthickness was introduced in 1974. Formally, we consider the following decision problem.

We use $k$-OuterThickness$(G)$ to denote Problem 1 with input graph $G$ and parameter $k$ for short. Our main result is the following.

Moreover, our hardness result applies to a more general covering problem $P_{ℱ,k}$, defined as follows. Let $ℱ$ be a proper graph class, where a graph class is called proper if it does not contain all graphs. Let $k\ge 1$ be an integer parameter. Given an undirected simple graph $G=(V,E)$, the task is to cover the edge set $E(G)$ by at most $k$ subsets $E_1,\mathrm{\dots },E_k$ such that each subgraph $(V(G),E_i)$ belongs to $ℱ$. Note that if $ℱ$ is monotone, meaning that whenever $G\in ℱ$ and $H$ is a subgraph of $G$, we have $H\in ℱ$, then any such cover can be converted into an edge partition by deleting overlaps. Hence, for monotone classes $ℱ$, covering and partitioning are equivalent. In particular, the class of all outerplanar graphs is monotone.

We generalize the NP-hardness of $k$-OuterThickness$(G)$ to $P_{ℱ,k}$ for every proper $ℱ$ that satisfies the three conditions stated below:

In our NP-hardness reduction, we need an indicator array $A_{ℱ,q}$ that records, for each graph with at most $q$ nodes, whether it belongs to $ℱ$, where $q$ is a function of $k$. Since there are $2^{O(q^2)}$ such graphs, $A_{ℱ,q}$ is a bit string of length $2^{O(q^2)}$. Thus, the existence of the appropriate array is sufficient to establish, nonconstructively, the existence of a valid NP-hardness reduction, even if there is no uniform procedure for computing this array from $ℱ$ and $q$. However, if one requires the reduction to be constructible within some bounded amount of resources for algorithmic purposes, then one must impose an additional condition on $ℱ$ to ensure that $A_{ℱ,q}$ can be computed within those resource bounds.

Moreover, if membership in $ℱ$ can be decided by an algorithm $M_{ℱ}$ in polynomial time, then $P_{ℱ,k}\in \mathrm{NP}$. A certificate is an edge covering of $E(G)$ by $k$ subsets $E_i$ for $i\in [k]$, and we can verify in polynomial time that $(V(G),E_i)\in ℱ$ for every $i\in [k]$ by running $M_{ℱ}$ on each part. Hence the certificate certifies that the $ℱ$-thickness of $G$ is at most $k$. As a result, Theorem 3 also yields NP-completeness if membership in $ℱ$ can be decided in polynomial time.

As a corollary of Theorem 3, by setting $ℱ$ to be the class of all planar graphs, we obtain Corollary 4, which complements Mansfield’s NP-hardness result (1983) for the thickness [24], established only for the case $k=2$.

It may be worth noting that Mansfield’s NP-hardness proof for the thickness proceeds via a reduction from Planar-3SAT [22] due to Lichtenstein (1982), which is technical. In contrast, our hardness proof uses other source problems: for $k=3$, we reduce from the chromatic index problem for $3$-regular graphs due to Holyer (1981) [19], and for every integer $k\ge 3$, we reduce from the chromatic index problem for $k$-regular graphs due to Leven and Galil (1983) [21].

As illustrated in Table 1, each of the three conditions mentioned in Theorem 3 is necessary. If $ℱ$ is the class of all eulerian³³3We follow Catlin’s convention [8] and use lowercase intentionally and consistently. graphs (including disconnected ones), then condition (a) fails. If $ℱ$ is the class of all pseudoforests, that is, the class of all undirected graphs in which each connected component contains at most one cycle, then condition (b) fails. If $ℱ$ is the class of all forests, then condition (c) fails. For each of these three classes $ℱ$, the problem $P_{ℱ,k}$ is solvable in polynomial time for every integer $k\ge 3$ (the case $P_{\mathrm{eulerian},k}$ is due to Alon and Tarsi [1], and the cases $P_{\mathrm{forests},k}$ and $P_{\mathrm{pseudoforests},k}$ follow from Edmonds [12]), showing that none of the three conditions can be dropped unless $\mathrm{P}=\mathrm{NP}$. In addition to the three example problems above, we found that the class $ℱ$ of all graphs whose edge sets can be partitioned into at most a constant number of forests, that is, graphs with arboricity bounded by a constant, also serves as a useful counterexample when attempting to replace the three conditions with weaker ones; see Section 5 for details.

All graphs and subgraphs considered in this paper are finite, undirected, and simple. For a graph $G$, we write $V(G)$ and $E(G)$ for its node set and edge set, respectively. For convenience, we sometimes use an edge subset $E^{\prime }\subseteq E(G)$ to denote the subgraph of $G$ induced by $E^{\prime }$, namely $(V(G),E^{\prime })$.

Let $𝒫$ be a graph property. A graph $G$ is said to be edge-maximal with respect to $𝒫$ if $G$ satisfies $𝒫$, but for every pair of non-adjacent nodes $u,v\in V(G)$, the graph obtained by adding the edge $\{u,v\}$ to $G$ does not satisfy property $𝒫$.

For every integer $m\ge 1$, we use the notation $[m]$ to denote the set of integers $\{1,\mathrm{\dots },m\}$. The reduction source of our problem is defined below.

Given an input instance $G$ of Edge-Coloring on $3$-regular graphs, defined in Theorem 5, we compute a label function $\phi$ defined below and an auxiliary graph $H$ in polynomial time. Then, we obtain a supergraph $G^{\prime }$ from joining $G$ and $H$ using the label function $\phi$ such that $G$ admits a 3-edge-coloring if and only if $G^{\prime }$ has an edge-partition into 3 outerplanar subgraphs (Lemma 7). This proves the NP-hardness stated in Theorem 2 for $k=3$. Moreover, $3$-OuterThickness$(G)\in \mathrm{NP}$: a certificate is an edge partition of $E(G)$ into $3$ subsets $E_i$ for $i\in [3]$, and we can verify in polynomial time that $(V(G),E_i)$ is outerplanar for every $i\in [3]$ by running the linear-time outerplanarity test of Mitchell [25] on each part. Hence the certificate certifies that the outerthickness of $G$ is at most $3$.

• $\mathrm{■}$

  Let $\phi :E(G)\to ℒ$ be a labeling function, where $ℒ=\{1,2,\mathrm{\dots },|ℒ|\}$ is a constant-size (not necessarily minimum-size) label set, such that for every path of length at most $3$ in $G$, the edges on the path receive pairwise distinct labels under $\phi$. The existence of $\phi$, as well as a construction running in time polynomial in the input size of $G$, is guaranteed by Proposition 11.

• $\mathrm{■}$

  We pick a sufficiently large constant $C$ such that every $C$-node graph⁴⁴4By a $C$-node graph, we mean a graph with $C$ nodes. with outerthickness $3$ contains an (not necessarily maximum) independent set of $\alpha \ge |ℒ|$ nodes. Then we construct a $C$-node graph $H$ that is edge-maximal with outerthickness $3$; that is, adding any edge not in $E(H)$ increases the outerthickness of $H$. Given the promise of $C$, let $w_1,w_2,\mathrm{\dots },w_{\alpha }$ be the $\alpha$ nodes in an independent set in $H$. The existence of $H$, as well as a construction running in time constant in the input size of $G$, is guaranteed by Proposition 12.

We initialize $G^{\prime }$ by taking a copy of $G$ and a copy of $H$ with disjoint node sets, and then identifying $G^{\prime }$ with their union. Then, for each edge $e≔\{u,v\}\in E(G)$, we add the edges $\{u,w_{\phi (e)}\}$ and $\{v,w_{\phi (e)}\}$ to $G^{\prime }$, as illustrated in Figure 1. Note that $G^{\prime }$ remains a simple graph: since any two edges incident to the same node in $G$ receive distinct labels under $\phi$, no parallel edges are created.

We need the following observation for our main lemma.

We generalize the NP-hardness proof for outerthickness in Section 3 to every proper graph class $ℱ$ that satisfies all of the following conditions:

1. (a)

   $ℱ$ is closed under topological minors,

2. (b)

   $ℱ$ is closed under $1$-sums, and

3. (c)

   $ℱ$ contains a cycle of length $3$.

By Condition (a), $ℱ$ is monotone. Thus, any covering of the edge set of an input graph for the problem $P_{ℱ,k}$ can be converted into an edge partition by deleting overlaps; hence, in this setting, covering and partitioning are equivalent. Thus, in this section, we treat $P_{ℱ\mathbf{,}k}$ as a partition problem: Let $ℱ$ be a proper graph class. We define the $ℱ$-thickness of an undirected simple graph $G$, denoted by ${\theta }_{ℱ}(G)$, to be the minimum integer $k$ such that $E(G)$ admits a partition into at most $k$ subsets $E_1,E_2,\mathrm{\dots },E_k$ with $(V(G),E_i)\in ℱ$ for all $i\in [k]$. Thus, the problem $P_{ℱ,k}$ asks, given an undirected simple graph $G$, whether ${\theta }_{ℱ}(G)\le k$.

Our NP-hardness reduction proceeds as follows. Let $k\ge 3$ be an integer. Given an input instance $G$ of Edge-Coloring on $k$-regular graphs, defined in Theorem 5, we compute a label function $\phi$ defined below and an auxiliary graph $H$ in polynomial time. Then, we obtain a supergraph $G^{\prime }$ from joining $G$ and $H$ using the label function $\phi$ such that $G$ admits a $k$-edge-coloring if and only if $G^{\prime }$ has ${\theta }_{ℱ}(G^{\prime })\le k$ (Lemma 16). This proves the NP-hardness claimed in Theorem 3 for every integer $k\ge 3$.

• $\mathrm{■}$

  Let $\phi :E(G)\to ℒ$ be a labeling function, where $ℒ=\{1,2,\mathrm{\dots },|ℒ|\}$ is a constant-size (not necessarily minimum-size) label set, such that for every path in $G$ of length at most $3$, the edges on the path receive pairwise distinct labels under $\phi$. The existence of such a function $\phi$, together with a construction running in time polynomial in the input size of $G$, is guaranteed by Proposition 11. The resulting label set $ℒ$ satisfies $|ℒ|=2k(k-1)+1=O(1)$, as desired.

• $\mathrm{■}$

  We pick a sufficiently large constant $C$ such that every $C$-node graph with $ℱ$-thickness $k$ contains an (not necessarily maximum) independent set of $\alpha \ge |ℒ|$ nodes. Then we construct a $C$-node graph $H$ that is edge-maximal with $ℱ$-thickness $k$. Given the promise of $C$, let $w_1,w_2,\mathrm{\dots },w_{\alpha }$ be the $\alpha$ nodes in an independent set in $H$. The existence of $H$, as well as a construction running in time constant in the input size of $G$, is shown in Lemma 13.

Finally, we remark on the case $k=2$. It is known that every planar graph has outerthickness at most $2$ due to Gonçalves (2005) [14], and hence $2$-OuterThickness$(G)$ for planar graphs contains only Yes-instances. For general graphs, however, the complexity of $2$-OuterThickness$(G)$ was, to the best of our knowledge, open at the time this paper was submitted for review. We later found that $2$-OuterThickness$(G)$ is NP-hard as well; the proof is included in the arXiv version of this paper. More broadly, in the context of our hardness framework in Theorem 3, any proper graph class $ℱ$ satisfying Conditions (a)–(c) for which the corresponding problem $P_{ℱ,k}$ with $k=2$ is NP-hard.

It is also worth noting that Conditions (a)–(c) in Theorem 3 are necessary even for $k=2$, in the following sense: relaxing any one of them allows graph classes $ℱ$ for which $P_{ℱ,2}$ is solvable in polynomial time.

For instance, if $ℱ$ is the class of forests, then Condition (c) fails, and $P_{ℱ,k}$ for $k=2$ is in P by the same algorithm as in the case $k\ge 3$. Similarly, if $ℱ$ is the class of pseudoforests, then Condition (b) fails, and $P_{ℱ,k}$ for $k=2$ also is in P by the same algorithm as for $k\ge 3$. Finally, if $ℱ$ is the class of graphs of bounded arboricity, then Condition (a) is not satisfied⁵⁵5For example, the $1$-subdivision of $K_5$ has arboricity at most $2$, whereas its topological minor $K_5$ has arboricity $3$., and the corresponding partitioning problem $P_{ℱ,2}$ is in P by Edmonds’ matroid-partitioning algorithm [12].