{"id":"arxiv/2607.13999","url":"https://arxiv.org/abs/2607.13999","tags":["cs.CC","cs.DM","math.CO"],"score":0,"title":"Edge-decomposition into Two Triangular Forests is NP-complete","domain":"cs.CC","source":"arxiv","authors":["Beniamin Bibrowski","Tomáš Masařík"],"reviews":0,"subject":"cs.CC","summary":"Let $\\mathcal F$ be a graph class that is closed under topological minors and 1-sums, has decidable membership, contains a triangle, and is not the class of all graphs. Recently, Lee, Liu, and Tsai [ICALP 2026] showed that the edge-decomposition problem into $k \\geq 3$ elements of $\\mathcal F$ is NP-hard. In particular, their general hardness reduction covers a long-standing problem on outerthickness (when $\\mathcal F$ is the class of outerplanar graphs). On the other hand, it is well known that decomposing a graph into forests is polynomial-time solvable, as implied by work of Edmonds [J.…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-15","reactions":{}}