Hardness results on parity subdivisions in digraphs - Maia, Ana Karolinna; Freire, Cibele Matos; Serra, Philipe M. (Anais do Encontro de Teoria da Computação (ETC), 2026)
The paper presents computational complexity results on the problem of parity subdivision in digraphs. We say that a vertex is small if its total degree (the sum of its in-degree and its out-degree) is at most 3 and it does not have in-degree or out-degree equal to 3; otherwise it is called big. We prove that the Parity (s, t)-Path problem is NP-complete when restricted to digraphs with only small vertices. With this result, we demonstrate that Parity Subdivision is also NP-complete. We conjecture that Parity F -Subdivision is NP-complete for any digraph F with at least two connected big vertices.Finally, we discuss cases in which the problem is solvable in polynomial time, such as parity path subdivision, 3-odd-cycle, and spiders.