{"id":"arxiv/2602.07607","url":"https://arxiv.org/abs/2602.07607","tags":["cs.CC","cs.DM","math.CO"],"score":0,"title":"Determining the Outerthickness of Graphs Is NP-Hard","domain":"cs.CC","source":"arxiv","authors":["Pin-Hsian Lee","Te-Cheng Liu","Meng-Tsung Tsai"],"reviews":0,"subject":"cs.CC","summary":"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_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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-02-07","reactions":{}}