2026-07-20T14:23:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26526 2026-07-01T07:16:14Z ddc:004 open_access

Determining the Outerthickness of Graphs Is NP-Hard Lee, Pin-Hsian Liu, Te-Cheng Tsai, Meng-Tsung outerthickness outerplanar graphs edge partition We give a short, self-contained, and easily verifiable proof that determining the outerthickness of a general graph is NP-hard. This resolves a long-standing open problem on the computational complexity of outerthickness. Moreover, our hardness result applies to a more general covering problem P_{ℱ, k}, defined as follows. Let ℱ be a proper graph class. Let k ≥ 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₁,…,E_k such that each subgraph (V(G),E_i) for i ∈ [k] belongs to ℱ. Note that if ℱ is monotone (in particular, when ℱ is the class of all outerplanar graphs), any such cover can be converted into an edge partition by deleting overlaps; hence, in this case, covering and partitioning are equivalent. Our result shows that for every proper graph class ℱ that satisfies all of the following conditions: (a) ℱ is closed under topological minors, (b) ℱ is closed under 1-sums, and (c) ℱ contains a cycle of length 3, the problem P_{ℱ, k} is NP-hard for every integer k ≥ 3. In particular: - For ℱ equal to the class of all outerplanar graphs, our result settles the long-standing open problem on the complexity of determining outerthickness. - For ℱ equal to the class of all planar graphs, our result complements Mansfield’s NP-hardness result (1983) for the thickness, which applies only to the case k = 2. It is also worth noting that each of the three conditions above is necessary. If ℱ is the class of all eulerian graphs, then condition (a) fails. If ℱ is the class of all pseudoforests, 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 ≥ 3, showing that none of the three conditions can be dropped unless P = NP. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pin-Hsian Lee and Te-Cheng Liu and Meng-Tsung Tsai 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.137 urn:nbn:de:0030-drops-265265 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.137 eng https://creativecommons.org/licenses/by/4.0/legalcode