Hardness results on parity subdivisions in digraphs

• Ana Karolinna Maia UFC
• Cibele Matos Freire Bowdoin College
• Philipe M. Serra UFC

DOI: https://doi.org/10.5753/etc.2026.23617

Resumo

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.

Referências

Bang-Jensen, J., Havet, F., and Maia, A. K. (2015). Finding a subdivision of a digraph. Theoretical Computer Science, 562:283–303.

Havet, F., Maia, A. K., and Mohar, B. (2018). Finding a subdivision of a prescribed digraph of order 4. Journal of Graph Theory, 87(4):536–560.

Kawarabayashi, K.-i., Reed, B., and Wollan, P. (2011). The graph minor algorithm with parity conditions. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 27–36. IEEE.

LaPaugh, A. S. and Papadimitriou, C. H. (1984). The even-path problem for graphs and digraphs. Networks, 14:507–513.

Maia, A. K. and Melo, M. V. M. (2022). Subdivisions with parity in digraphs. In 10th Latin American Workshop on Cliques in Graphs (LAWCG’ 22).

Robertson, N. and Seymour, P. (1995). Graph minors .xiii. the disjoint paths problem. Journal of Combinatorial Theory, Series B, 63(1):65–110.