{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreierqehrcbnjmh4aeo7z6apbliuvlfoyt2bvngdfbu3uyyvenb4nie",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mekggddeu6g2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.07607v1",
  "publishedAt": "2026-02-10T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Pin-Hsian Lee",
    "Te-Cheng Liu",
    "Meng-Tsung Tsai"
  ],
  "textContent": "**Authors:** Pin-Hsian Lee, Te-Cheng Liu, Meng-Tsung Tsai\n\nWe 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_F$, defined as follows. Fix a proper graph class $F$ whose membership is decidable. Given an undirected simple graph $G$ and an integer $k$, the task is to cover the edge set $E(G)$ by at most $k$ subsets $E_1,\\ldots,E_k$ such that each subgraph $(V(G),E_i)$ belongs to $F$. Note that if $F$ is monotone (in particular, when $F$ 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 $F$ whose membership is decidable and that satisfies all of the following conditions: (a) $F$ is closed under topological minors, (b) $F$ is closed under $1$-sums, and (c) $F$ contains a cycle of length $3$, the problem $P_F$ is NP-hard for every fixed integer $k\\ge 3$. In particular: For $F$ equal to the class of all outerplanar graphs, our result settles the long-standing open problem on the complexity of determining outerthickness. For $F$ equal to the class of all planar graphs, our result complements Mansfield's NP-hardness result 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 $F$ is the class of all eulerian graphs, then cond. (a) fails. If $F$ is the class of all pseudoforests, then cond. (b) fails. If $F$ is the class of all forests, then cond. (c) fails. For each of these three classes $F$, the problem $P_F$ is solvable in polynomial time for every fixed integer $k\\ge 3$, showing that none of the three conditions can be dropped.",
  "title": "Determining the Outerthickness of Graphs Is NP-Hard"
}