{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,24]],"date-time":"2026-09-24T23:56:46Z","timestamp":1790294206029,"version":"4.1.0"},"reference-count":22,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2018,9,17]],"date-time":"2018-09-17T00:00:00Z","timestamp":1537142400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The Hamiltonian cycle reconfiguration problem asks, given two Hamiltonian cycles     C 0     and     C t     of a graph G, whether there is a sequence of Hamiltonian cycles      C 0  ,  C 1  , \u2026 ,  C t      such that     C i     can be obtained from     C  i \u2212 1      by a switch for each i with     1 \u2264 i \u2264 t    , where a switch is the replacement of a pair of edges     u v     and     w z     on a Hamiltonian cycle with the edges     u w     and     v z     of G, given that     u w     and     v z     did not appear on the cycle. We show that the Hamiltonian cycle reconfiguration problem is PSPACE-complete, settling an open question posed by Ito et al. (2011) and van den Heuvel (2013). More precisely, we show that the Hamiltonian cycle reconfiguration problem is PSPACE-complete for chordal bipartite graphs, strongly chordal split graphs, and bipartite graphs with maximum degree 6. Bipartite permutation graphs form a proper subclass of chordal bipartite graphs, and unit interval graphs form a proper subclass of strongly chordal graphs. On the positive side, we show that, for any two Hamiltonian cycles of a bipartite permutation graph and a unit interval graph, there is a sequence of switches transforming one cycle to the other, and such a sequence can be obtained in linear time.<\/jats:p>","DOI":"10.3390\/a11090140","type":"journal-article","created":{"date-parts":[[2018,9,17]],"date-time":"2018-09-17T10:42:20Z","timestamp":1537180940000},"page":"140","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Complexity of Hamiltonian Cycle Reconfiguration"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0194-7138","authenticated-orcid":false,"given":"Asahi","family":"Takaoka","sequence":"first","affiliation":[{"name":"Department of Information Systems Creation, Faculty of Engineering, Kanagawa University, Rokkakubashi 3-27-1 Kanagawa-ku, Yokohama-shi, Kanagawa 221-8686, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2018,9,17]]},"reference":[{"key":"ref_1","first-page":"127","article-title":"The complexity of change","volume":"Volume 409","author":"Blackburn","year":"2013","journal-title":"Surveys in Combinatorics 2013"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/j.tcs.2016.08.016","article-title":"The complexity of dominating set reconfiguration","volume":"651","author":"Haddadan","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., and Mouawad, A.E. (2018, January 7\u201310). The complexity of independent set reconfiguration on bipartite graphs. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), New Orleans, LA, USA.","DOI":"10.1137\/1.9781611975031.13"},{"key":"ref_4","first-page":"195","article-title":"Statistical problems involving permutations with restricted positions","volume":"Volume 36","author":"Klaasen","year":"2001","journal-title":"State of the Art in Probability and Statistics"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"12:1","DOI":"10.1145\/2822322","article-title":"On the Switch Markov Chain for Perfect Matchings","volume":"64","author":"Dyer","year":"2017","journal-title":"J. ACM"},{"key":"ref_6","first-page":"627","article-title":"Transforming Graphs with the Same Graphic Sequence","volume":"25","author":"Bereg","year":"2017","journal-title":"J. Inf. Process."},{"key":"ref_7","unstructured":"West, D.B. (2000). Introduction to Graph Theory, Prentice Hall. [2nd ed.]."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1054","DOI":"10.1016\/j.tcs.2010.12.005","article-title":"On the complexity of reconfiguration problems","volume":"412","author":"Ito","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"ref_9","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0012-365X(95)00057-4","article-title":"Hamiltonian circuits in chordal bipartite graphs","volume":"156","year":"1996","journal-title":"Discr. Math."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1016\/j.tcs.2005.05.008","article-title":"PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation","volume":"343","author":"Hearn","year":"2005","journal-title":"Theor. Comput. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1587\/transfun.E101.A.232","article-title":"The Complexity of (List) Edge-Coloring Reconfiguration Problem","volume":"101-A","author":"Osawa","year":"2018","journal-title":"IEICE Trans."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V.B., and Spinrad, J.P. (1999). Graph Classes: A Survey, Society for Industrial and Applied Mathematics.","DOI":"10.1137\/1.9780898719796"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/S0012-365X(96)00307-X","article-title":"Proper interval graphs and the guard problem","volume":"170","author":"Chen","year":"1997","journal-title":"Discr. Math."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1105","DOI":"10.1016\/j.ipl.2009.07.010","article-title":"A simple algorithm to find Hamiltonian cycles in proper interval graphs","volume":"109","author":"Ibarra","year":"2009","journal-title":"Inf. Process. Lett."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/S0020-0190(03)00298-9","article-title":"A linear time recognition algorithm for proper interval graphs","volume":"87","author":"Panda","year":"2003","journal-title":"Inf. Process. Lett."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/S0166-218X(87)80003-3","article-title":"Bipartite permutation graphs","volume":"18","author":"Spinrad","year":"1987","journal-title":"Discrete Appl. Math."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Hearn, R.A., and Demaine, E.D. (2009). Games, Puzzles and Computation, A. K. Peters Ltd.","DOI":"10.1201\/b10581"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0012-365X(83)90154-1","article-title":"Characterizations of strongly chordal graphs","volume":"43","author":"Farber","year":"1983","journal-title":"Discr. Math."},{"key":"ref_20","unstructured":"Dahlhaus, E. (1991). Chordale Graphen im besonderen Hinblick auf parallele Algorithmen. [Habilitation Thesis, University of Bonn]. (In German)."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Spinrad, J.P. (2003). Efficient Graph Representations: Fields Institute Monographs, American Mathematical Society.","DOI":"10.1090\/fim\/019"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0898-1221(93)90308-I","article-title":"Optimal greedy algorithms for indifference graphs","volume":"25","author":"Looges","year":"1993","journal-title":"Comput. Math. Appl."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/9\/140\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:20:54Z","timestamp":1760196054000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/9\/140"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,17]]},"references-count":22,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2018,9]]}},"alternative-id":["a11090140"],"URL":"https:\/\/doi.org\/10.3390\/a11090140","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,17]]}}}