Recognizing a totally odd K_4-subdivision, parity 2-disjoint rooted paths and a parity cycle through specified elements (extended abstract)

摘要

A totally odd K_4-subdivision is a subdivision of K_4 where each subdivided edge has odd length. The recognition of a totally odd K_4-subdivision plays an important role in both graph theory and combinatorial optimization. Sewell and Trotter, Zang and Thomassen independently conjectured the existence of a polynomial time recognition algorithm. In this paper, we give the first polynomial time algorithm for solving this problem. We also study the parity two disjoint rooted paths problem where we determine if there exists two vertex disjoint paths of a specified parity between two pairs of terminals.