The parity hamiltonian cycle problem in directed graphs

Hiroshi Nishiyama, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)


This paper investigates a variant of the Hamiltonian cycle, the parity Hamiltonian cycle (PHC) problem: a PHC in a directed graph is a closed walk (possibly using an arc more than once) which visits every vertex odd number of times. Nishiyama et al. (2015) investigated the undirected version of the PHC problem, and gave a simple characterization that a connected undirected graph has a PHC if and only if it has even order or it is non-bipartite. This paper gives a complete characterization when a directed graph has a PHC, and shows that the PHC problem in a directed graph is solved in polynomial time. The characterization, unlike with the undirected case, is described by a linear system over GF(2).

Original languageEnglish
Title of host publicationCombinatorial Optimization - 4th International Symposium, ISCO 2016, Revised Selected Papers
EditorsSatoru Fujishige, Ridha A. Mahjoub, Raffaele Cerulli
PublisherSpringer Verlag
Number of pages9
ISBN (Print)9783319455860
Publication statusPublished - 2016
Event4th International Symposium on Combinatorial Optimization, ISCO 2016 - Vietri sul Mare, Italy
Duration: May 16 2016May 18 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9849 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other4th International Symposium on Combinatorial Optimization, ISCO 2016
CityVietri sul Mare

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'The parity hamiltonian cycle problem in directed graphs'. Together they form a unique fingerprint.

Cite this