Hikarii's blog

Find any Hamiltonian cycle in O(n^2) or similar?
By Hikarii, history, 4 years ago, In English

I've encountered a problem that wants to find any Hamiltonian cycle (it ends where it starts). The graph given has undirected edges (which is different than this problem from CSES), and the number of vertices are $$$4 * 10^3$$$. I've been doing some search online for a while now, but eventually none of the solution seems to be better than $$$O(2^n * n)$$$. Do you have any ideas? I'm glad if some (pseudo) codes are provided, if possible. Thank you.

  • Vote: I like it
  • -18
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 2   Vote: I like it +37 Vote: I do not like it

https://en.wikipedia.org/wiki/Hamiltonian_path

Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem, which is NP-complete.

Chances are there's some special property of the graph in the problem that you mentioned that makes it solvable in polynomial time.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -24 Vote: I do not like it

    I hate to tell you this, but it seems that there is no special property mentioned in the problem statement, and I'm pretty certain about that.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      do you have a link to this problem

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        I do, but it's entirely in Vietnamese, and you have to join the Graph Marathon (which is in fact just a problemset and not a "real" contest, perhaps DMOJ doesn't have such feature?), which I'm afraid will make it difficult.

        This is the problem anyway. To view it, create an account, then go back to the home page and click on the Graph Marathon (which shows as currently running), join it, and click the link to the problem.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Disclaimer: It's possible that I've misunderstood something in the statement because I don't speak Vietnamese, I just copy pasted it into Google translate.

          I have a feeling this task requires heuristics for the following reasons:

          1. Extremely low AC rate and from looking at submission list, most AC submissions are from problem author (author name is on the right on problem statement).
          2. Users that got AC also had several TLE submissions hovering around the AC range (in the 30s), which would be unlikely if there was a provable polynomial time solution.
          3. In the comment section, there's a comment from author that seems to roughly translate to "greedy", which is just flat out wrong.

          Doing some Googling, there are a number of heuristics for Hamiltonian cycles that exist. For example, this link claims that if the graph is dense enough, with all degrees at least $$$n / 2$$$, a cycle always exists and you can find one in $$$O(n^2)$$$ (the link talks about paths since that was the original question, but the proof mentions cycles). Also, since the problem doesn't provide instructions on what to do if there's no solution, you can deduce the test cases always guarantee at least one cycle exists, so the graphs are probably somewhat dense because author had to write a generator that generates valid test cases somehow, and that's much easier with dense graphs.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            I think my hunch was right, I implemented the simple $$$O(n^2)$$$ heuristic I mentioned above (described in more detail on Wikipedia), which gets around 34/40 (results are not always consistent since I use seed based on clock time). With a bit more tweaking you can probably get it to 40/40.

            https://ideone.com/rIeQ5B

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I think this problem is a Hail Mary at this point. I have been tweaking the Warnsdorff's heuristic for a while but couldn't get more than 28 cases correct.

              → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          If you don't mind, you can send me the problem statement, because I'm Vietnamese too, anh I can read it

          → Reply