A Polynomial Time Algorithm for the Hamilton Circuit Problem

2013/05/26 by Xinwen Jiang, Jiang, Xinwen · 1 voice
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Formal Methods in Verification #cs.DS

paper · pdf · doi:10.48550/arxiv.1305.5976

openalex publication_date 2013/05/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we introduce a so-called Multistage graph Simple Path (MSP) problem and show that the Hamilton Circuit (HC) problem can be polynomially reducible to the MSP problem. To solve the MSP problem, we propose a polynomial algorithm and prove its NP-completeness. Our result implies NP=P.

Discussions

• P might be NP: A Polynomial Time Algorithm for the Hamilton Circuit Problem [hn, 44 points, 47 comments]

Related

• A Algorithm for the Hamilton Circuit Problem
• Hamiltonian Cycle Problem is in P
• A Simple Algorithm for Hamiltonicity
• Hamilton Circuits in Graphs and Directed Graphs
• A fast algorithm on average for solving the Hamilton Cycle problem