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

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

Recognizing a totally odd K4- subdivision, parity 2-disjoint rooted paths and a parity cycle through specified elements (extended abstract)  
BibTex | RIS | RefWorks Download
A totally odd K4-subdivision is a subdivision of K4 where each subdivided edge has odd length. The recognition of a totally odd K4-subdivision plays an important role in both graph theory and combinatorial optimization. Sewell and Trotter (53), Zang (63) and Thomassen (60) 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 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. Using a similar technique, we give an O(|E(G)||V (G)|�(|E(G)|,|V (G)|)) algorithm for the parity two disjoint rooted paths problem on an input graph G, where �(|E(G)|,|V (G)|) is the inverse of the Ackermann function. We note that this clearly gives an algorithm for the well-known non-parity version of the two disjoint rooted paths problem (19, 50, 52, 55, 58). We then extend our approach to give a polynomial time algorithm which determines, for any fixed k, whether there exists a cycle of a given parity through k independent input edges. This generalizes the non-parity version of the algorithm in (22). Thomassen (61) gave a polynomial algorithm for the case k = 2 and hoped to use this algorithm to recog- nize a totally odd K4-subdivision. Our algorithm runs in O(|E(G)||V (G)|�(|E(G)|,|V (G)|)) for any fixed k. Finally, we give an O(|V (G)|2 + |E(G)|�(|E(G)|,|V (G)|log|V (G)|)) algorithm to de- cide whether a graph contains k disjoint paths from A to B (with |A| = |B| = k) that are not all of the same parity. This answers a conjecture of Thomassen (60). This problem arises from the study of totally odd-K4-subdivisions ∗T his work was done as a part of an INRIA-NII collaboration under MOU grant, and partially supported by MEXT Grant-in- Aid for Scientific Research on Priority Areas "New Horizons in Computing" † National Institute of Informatics, 2-1-2, Hitotsubashi, Chiyoda-ku, Tokyo, Japan. ‡Research partly supported by Japan Society for the Promo-
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.