Is Hamiltoncycle and Euler cycle NP-complete or not?Every $t$-coloring of $K_{2t+1}$ contains a monochromatic...

What is the fastest integer factorization to break RSA?

How can I deal with my CEO asking me to hire someone with a higher salary than me, a co-founder?

How to stretch the corners of this image so that it looks like a perfect rectangle?

Using "tail" to follow a file without displaying the most recent lines

Can a virus destroy the BIOS of a modern computer?

Different meanings of こわい

Why was Sir Cadogan fired?

Can someone clarify Hamming's notion of important problems in relation to modern academia?

Venezuelan girlfriend wants to travel the USA to be with me. What is the process?

Implication of namely

Forgetting the musical notes while performing in concert

What Exploit Are These User Agents Trying to Use?

OP Amp not amplifying audio signal

Unlock My Phone! February 2018

How can a day be of 24 hours?

In the UK, is it possible to get a referendum by a court decision?

Do Iron Man suits sport waste management systems?

How could indestructible materials be used in power generation?

Is it "common practice in Fourier transform spectroscopy to multiply the measured interferogram by an apodizing function"? If so, why?

How badly should I try to prevent a user from XSSing themselves?

What are the G forces leaving Earth orbit?

Why is it a bad idea to hire a hitman to eliminate most corrupt politicians?

What is required to make GPS signals available indoors?

Is it a bad idea to plug the other end of ESD strap to wall ground?



Is Hamiltoncycle and Euler cycle NP-complete or not?


Every $t$-coloring of $K_{2t+1}$ contains a monochromatic cycleComplete graph-coloringColouring $n$ vertices with $(n-1)$ colours in a graph with chromatic number $n$Check existence of walk visiting every node in graph odd-timesUse of pigeonhole principle in ramsey-theorem about monochromatic triangles.Alternating cycle in a graphGraph Coloring : How to Think about Algorithms Exercise 1.6.2Complete graphs in the plane with colored edges where an edge don't cross edges with same colorIs it possible to start with a partially colored graph for a graph $G$ and complete it into a coloring with $chi(G)$ colors?A new graph invariant? The maximum number of non-equivalent colorings with $n$ colors.













1












$begingroup$



Question: Determine which of these computational problems are NP-complete.




  1. Determining whether a number with $n$ digits is a prime number.

  2. Determining whether a graph with $n$ nodes has a hamiltoncycle.

  3. Determining whether a graph with $n$ nodes has an eulercycle.

  4. Determining whether a graph with $n$ nodes can be coloured with $2$ colors.

  5. Determining whether a graph with $n$ nodes can be colored with $3$ colors.






My Attempts:



1) I'm not sure if this is correct because the question specifies the number of digits to be $n$ and not that the actual prime number is $n$. So in the latter case, we only need to check the division of $n$ with primes that are less than $sqrt{n}$. This reasoning doesnt feel correct.



2) So if we first choose one node we can choose among $n$ of them, then we can choose to go to $n-1$ other nodes, and then $n-2$ and so on. So we get $n!$ which is not in polynomial time, thus it is NP-complete.



3) This one is trickier, i can't really use a similar argument as for the hamiltoncycle. I don't know the number of edges. How should I think here?



4) I assume that a coloring here should be such that no neighbouring/connected nodes have the same colour. But I have no idea how these $n$ nodes are connected in order to figure this out?



5) Same question as 4) essentially.










share|cite|improve this question









$endgroup$












  • $begingroup$
    For (3), it is known that a graph has an eulerian cycle if and only if all the nodes have an even degree. That's linear on the number of nodes.
    $endgroup$
    – frabala
    Mar 18 at 13:52












  • $begingroup$
    What do you mean by "Thats linear on the number of nodes"? So the problem is then to check whether or not all of these $n$ nodes have an even degree. How is this a linear problem?
    $endgroup$
    – Parseval
    Mar 18 at 14:21






  • 1




    $begingroup$
    You're right. I falsely assumed constant time for checking the degree of a node.
    $endgroup$
    – frabala
    Mar 18 at 14:29
















1












$begingroup$



Question: Determine which of these computational problems are NP-complete.




  1. Determining whether a number with $n$ digits is a prime number.

  2. Determining whether a graph with $n$ nodes has a hamiltoncycle.

  3. Determining whether a graph with $n$ nodes has an eulercycle.

  4. Determining whether a graph with $n$ nodes can be coloured with $2$ colors.

  5. Determining whether a graph with $n$ nodes can be colored with $3$ colors.






My Attempts:



1) I'm not sure if this is correct because the question specifies the number of digits to be $n$ and not that the actual prime number is $n$. So in the latter case, we only need to check the division of $n$ with primes that are less than $sqrt{n}$. This reasoning doesnt feel correct.



2) So if we first choose one node we can choose among $n$ of them, then we can choose to go to $n-1$ other nodes, and then $n-2$ and so on. So we get $n!$ which is not in polynomial time, thus it is NP-complete.



3) This one is trickier, i can't really use a similar argument as for the hamiltoncycle. I don't know the number of edges. How should I think here?



4) I assume that a coloring here should be such that no neighbouring/connected nodes have the same colour. But I have no idea how these $n$ nodes are connected in order to figure this out?



5) Same question as 4) essentially.










share|cite|improve this question









$endgroup$












  • $begingroup$
    For (3), it is known that a graph has an eulerian cycle if and only if all the nodes have an even degree. That's linear on the number of nodes.
    $endgroup$
    – frabala
    Mar 18 at 13:52












  • $begingroup$
    What do you mean by "Thats linear on the number of nodes"? So the problem is then to check whether or not all of these $n$ nodes have an even degree. How is this a linear problem?
    $endgroup$
    – Parseval
    Mar 18 at 14:21






  • 1




    $begingroup$
    You're right. I falsely assumed constant time for checking the degree of a node.
    $endgroup$
    – frabala
    Mar 18 at 14:29














1












1








1





$begingroup$



Question: Determine which of these computational problems are NP-complete.




  1. Determining whether a number with $n$ digits is a prime number.

  2. Determining whether a graph with $n$ nodes has a hamiltoncycle.

  3. Determining whether a graph with $n$ nodes has an eulercycle.

  4. Determining whether a graph with $n$ nodes can be coloured with $2$ colors.

  5. Determining whether a graph with $n$ nodes can be colored with $3$ colors.






My Attempts:



1) I'm not sure if this is correct because the question specifies the number of digits to be $n$ and not that the actual prime number is $n$. So in the latter case, we only need to check the division of $n$ with primes that are less than $sqrt{n}$. This reasoning doesnt feel correct.



2) So if we first choose one node we can choose among $n$ of them, then we can choose to go to $n-1$ other nodes, and then $n-2$ and so on. So we get $n!$ which is not in polynomial time, thus it is NP-complete.



3) This one is trickier, i can't really use a similar argument as for the hamiltoncycle. I don't know the number of edges. How should I think here?



4) I assume that a coloring here should be such that no neighbouring/connected nodes have the same colour. But I have no idea how these $n$ nodes are connected in order to figure this out?



5) Same question as 4) essentially.










share|cite|improve this question









$endgroup$





Question: Determine which of these computational problems are NP-complete.




  1. Determining whether a number with $n$ digits is a prime number.

  2. Determining whether a graph with $n$ nodes has a hamiltoncycle.

  3. Determining whether a graph with $n$ nodes has an eulercycle.

  4. Determining whether a graph with $n$ nodes can be coloured with $2$ colors.

  5. Determining whether a graph with $n$ nodes can be colored with $3$ colors.






My Attempts:



1) I'm not sure if this is correct because the question specifies the number of digits to be $n$ and not that the actual prime number is $n$. So in the latter case, we only need to check the division of $n$ with primes that are less than $sqrt{n}$. This reasoning doesnt feel correct.



2) So if we first choose one node we can choose among $n$ of them, then we can choose to go to $n-1$ other nodes, and then $n-2$ and so on. So we get $n!$ which is not in polynomial time, thus it is NP-complete.



3) This one is trickier, i can't really use a similar argument as for the hamiltoncycle. I don't know the number of edges. How should I think here?



4) I assume that a coloring here should be such that no neighbouring/connected nodes have the same colour. But I have no idea how these $n$ nodes are connected in order to figure this out?



5) Same question as 4) essentially.







discrete-mathematics graph-theory






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked Mar 18 at 13:38









ParsevalParseval

3,0721719




3,0721719












  • $begingroup$
    For (3), it is known that a graph has an eulerian cycle if and only if all the nodes have an even degree. That's linear on the number of nodes.
    $endgroup$
    – frabala
    Mar 18 at 13:52












  • $begingroup$
    What do you mean by "Thats linear on the number of nodes"? So the problem is then to check whether or not all of these $n$ nodes have an even degree. How is this a linear problem?
    $endgroup$
    – Parseval
    Mar 18 at 14:21






  • 1




    $begingroup$
    You're right. I falsely assumed constant time for checking the degree of a node.
    $endgroup$
    – frabala
    Mar 18 at 14:29


















  • $begingroup$
    For (3), it is known that a graph has an eulerian cycle if and only if all the nodes have an even degree. That's linear on the number of nodes.
    $endgroup$
    – frabala
    Mar 18 at 13:52












  • $begingroup$
    What do you mean by "Thats linear on the number of nodes"? So the problem is then to check whether or not all of these $n$ nodes have an even degree. How is this a linear problem?
    $endgroup$
    – Parseval
    Mar 18 at 14:21






  • 1




    $begingroup$
    You're right. I falsely assumed constant time for checking the degree of a node.
    $endgroup$
    – frabala
    Mar 18 at 14:29
















$begingroup$
For (3), it is known that a graph has an eulerian cycle if and only if all the nodes have an even degree. That's linear on the number of nodes.
$endgroup$
– frabala
Mar 18 at 13:52






$begingroup$
For (3), it is known that a graph has an eulerian cycle if and only if all the nodes have an even degree. That's linear on the number of nodes.
$endgroup$
– frabala
Mar 18 at 13:52














$begingroup$
What do you mean by "Thats linear on the number of nodes"? So the problem is then to check whether or not all of these $n$ nodes have an even degree. How is this a linear problem?
$endgroup$
– Parseval
Mar 18 at 14:21




$begingroup$
What do you mean by "Thats linear on the number of nodes"? So the problem is then to check whether or not all of these $n$ nodes have an even degree. How is this a linear problem?
$endgroup$
– Parseval
Mar 18 at 14:21




1




1




$begingroup$
You're right. I falsely assumed constant time for checking the degree of a node.
$endgroup$
– frabala
Mar 18 at 14:29




$begingroup$
You're right. I falsely assumed constant time for checking the degree of a node.
$endgroup$
– frabala
Mar 18 at 14:29










1 Answer
1






active

oldest

votes


















0












$begingroup$

1):



It is known that primality testing is in P. But this is not at all straightforward. You can read about the algorithm here or consult the paper itself: https://en.wikipedia.org/wiki/AKS_primality_test



The problem with your argumentation is that when we refer to polynomial time we mean that with respect to the input length. Now to represent n we need $O(log(n))$ bits. So the input length is order $O(log(n))$. Your proposed algorithm of checking all the values up to $sqrt{n}$ would satisfy (for asymptotic complexity): $$Omega(sqrt{n}) = Omega(sqrt{exp(log(n))}) = Omega(exp(1/2log(n)))$$



Thus that is at least exponential in the input length.



2):



This is in fact NP-complete. In order to prove this you have to prove that it is in NP and that it is NP-hard. It is not too hard to prove that it is in NP: You could guess a circle consisting of all nodes and check in polynomial time that it is actually hamiltonian.
It is more difficult to prove that this is NP-hard. You might want to have a look at reductions for this.



Note that your argumentation is not valid. You cannot conclude that something is NP-complete just because the only algorithm you found is outside of P.



3):



It is even possible to find an Eulerian path in linear time (in the number of edges). Note that there are at most $n^2$ edges in any simple undirected graph (where n is the number of nodes). You can try to find a polynomial algorithm yourself or just look it up on wikipedia. Hint to find the algorithm: Be Greedy.



4):



Your assumption is correct. Note that a graph can be colored with 2 colors if and only if it is bipartite. This can be done in polynomial time. My hint is to look at BFS (breadth first search).



5):



This is NP-complete. In order to show that you have to show that it is in NP (just give a nondeterministic polynomial algorithm that solves it) and that it is NP-hard. Again this is not very straightforward and you'll need to know about reductions to do this.



Link to wikipedia's page about reduction: https://en.wikipedia.org/wiki/Reduction_(complexity)



Feel free to ask if anything I wrote is unclear or if you'd like more information on reductions.






share|cite|improve this answer









$endgroup$














    Your Answer





    StackExchange.ifUsing("editor", function () {
    return StackExchange.using("mathjaxEditing", function () {
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    });
    });
    }, "mathjax-editing");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "69"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3152801%2fis-hamiltoncycle-and-euler-cycle-np-complete-or-not%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    0












    $begingroup$

    1):



    It is known that primality testing is in P. But this is not at all straightforward. You can read about the algorithm here or consult the paper itself: https://en.wikipedia.org/wiki/AKS_primality_test



    The problem with your argumentation is that when we refer to polynomial time we mean that with respect to the input length. Now to represent n we need $O(log(n))$ bits. So the input length is order $O(log(n))$. Your proposed algorithm of checking all the values up to $sqrt{n}$ would satisfy (for asymptotic complexity): $$Omega(sqrt{n}) = Omega(sqrt{exp(log(n))}) = Omega(exp(1/2log(n)))$$



    Thus that is at least exponential in the input length.



    2):



    This is in fact NP-complete. In order to prove this you have to prove that it is in NP and that it is NP-hard. It is not too hard to prove that it is in NP: You could guess a circle consisting of all nodes and check in polynomial time that it is actually hamiltonian.
    It is more difficult to prove that this is NP-hard. You might want to have a look at reductions for this.



    Note that your argumentation is not valid. You cannot conclude that something is NP-complete just because the only algorithm you found is outside of P.



    3):



    It is even possible to find an Eulerian path in linear time (in the number of edges). Note that there are at most $n^2$ edges in any simple undirected graph (where n is the number of nodes). You can try to find a polynomial algorithm yourself or just look it up on wikipedia. Hint to find the algorithm: Be Greedy.



    4):



    Your assumption is correct. Note that a graph can be colored with 2 colors if and only if it is bipartite. This can be done in polynomial time. My hint is to look at BFS (breadth first search).



    5):



    This is NP-complete. In order to show that you have to show that it is in NP (just give a nondeterministic polynomial algorithm that solves it) and that it is NP-hard. Again this is not very straightforward and you'll need to know about reductions to do this.



    Link to wikipedia's page about reduction: https://en.wikipedia.org/wiki/Reduction_(complexity)



    Feel free to ask if anything I wrote is unclear or if you'd like more information on reductions.






    share|cite|improve this answer









    $endgroup$


















      0












      $begingroup$

      1):



      It is known that primality testing is in P. But this is not at all straightforward. You can read about the algorithm here or consult the paper itself: https://en.wikipedia.org/wiki/AKS_primality_test



      The problem with your argumentation is that when we refer to polynomial time we mean that with respect to the input length. Now to represent n we need $O(log(n))$ bits. So the input length is order $O(log(n))$. Your proposed algorithm of checking all the values up to $sqrt{n}$ would satisfy (for asymptotic complexity): $$Omega(sqrt{n}) = Omega(sqrt{exp(log(n))}) = Omega(exp(1/2log(n)))$$



      Thus that is at least exponential in the input length.



      2):



      This is in fact NP-complete. In order to prove this you have to prove that it is in NP and that it is NP-hard. It is not too hard to prove that it is in NP: You could guess a circle consisting of all nodes and check in polynomial time that it is actually hamiltonian.
      It is more difficult to prove that this is NP-hard. You might want to have a look at reductions for this.



      Note that your argumentation is not valid. You cannot conclude that something is NP-complete just because the only algorithm you found is outside of P.



      3):



      It is even possible to find an Eulerian path in linear time (in the number of edges). Note that there are at most $n^2$ edges in any simple undirected graph (where n is the number of nodes). You can try to find a polynomial algorithm yourself or just look it up on wikipedia. Hint to find the algorithm: Be Greedy.



      4):



      Your assumption is correct. Note that a graph can be colored with 2 colors if and only if it is bipartite. This can be done in polynomial time. My hint is to look at BFS (breadth first search).



      5):



      This is NP-complete. In order to show that you have to show that it is in NP (just give a nondeterministic polynomial algorithm that solves it) and that it is NP-hard. Again this is not very straightforward and you'll need to know about reductions to do this.



      Link to wikipedia's page about reduction: https://en.wikipedia.org/wiki/Reduction_(complexity)



      Feel free to ask if anything I wrote is unclear or if you'd like more information on reductions.






      share|cite|improve this answer









      $endgroup$
















        0












        0








        0





        $begingroup$

        1):



        It is known that primality testing is in P. But this is not at all straightforward. You can read about the algorithm here or consult the paper itself: https://en.wikipedia.org/wiki/AKS_primality_test



        The problem with your argumentation is that when we refer to polynomial time we mean that with respect to the input length. Now to represent n we need $O(log(n))$ bits. So the input length is order $O(log(n))$. Your proposed algorithm of checking all the values up to $sqrt{n}$ would satisfy (for asymptotic complexity): $$Omega(sqrt{n}) = Omega(sqrt{exp(log(n))}) = Omega(exp(1/2log(n)))$$



        Thus that is at least exponential in the input length.



        2):



        This is in fact NP-complete. In order to prove this you have to prove that it is in NP and that it is NP-hard. It is not too hard to prove that it is in NP: You could guess a circle consisting of all nodes and check in polynomial time that it is actually hamiltonian.
        It is more difficult to prove that this is NP-hard. You might want to have a look at reductions for this.



        Note that your argumentation is not valid. You cannot conclude that something is NP-complete just because the only algorithm you found is outside of P.



        3):



        It is even possible to find an Eulerian path in linear time (in the number of edges). Note that there are at most $n^2$ edges in any simple undirected graph (where n is the number of nodes). You can try to find a polynomial algorithm yourself or just look it up on wikipedia. Hint to find the algorithm: Be Greedy.



        4):



        Your assumption is correct. Note that a graph can be colored with 2 colors if and only if it is bipartite. This can be done in polynomial time. My hint is to look at BFS (breadth first search).



        5):



        This is NP-complete. In order to show that you have to show that it is in NP (just give a nondeterministic polynomial algorithm that solves it) and that it is NP-hard. Again this is not very straightforward and you'll need to know about reductions to do this.



        Link to wikipedia's page about reduction: https://en.wikipedia.org/wiki/Reduction_(complexity)



        Feel free to ask if anything I wrote is unclear or if you'd like more information on reductions.






        share|cite|improve this answer









        $endgroup$



        1):



        It is known that primality testing is in P. But this is not at all straightforward. You can read about the algorithm here or consult the paper itself: https://en.wikipedia.org/wiki/AKS_primality_test



        The problem with your argumentation is that when we refer to polynomial time we mean that with respect to the input length. Now to represent n we need $O(log(n))$ bits. So the input length is order $O(log(n))$. Your proposed algorithm of checking all the values up to $sqrt{n}$ would satisfy (for asymptotic complexity): $$Omega(sqrt{n}) = Omega(sqrt{exp(log(n))}) = Omega(exp(1/2log(n)))$$



        Thus that is at least exponential in the input length.



        2):



        This is in fact NP-complete. In order to prove this you have to prove that it is in NP and that it is NP-hard. It is not too hard to prove that it is in NP: You could guess a circle consisting of all nodes and check in polynomial time that it is actually hamiltonian.
        It is more difficult to prove that this is NP-hard. You might want to have a look at reductions for this.



        Note that your argumentation is not valid. You cannot conclude that something is NP-complete just because the only algorithm you found is outside of P.



        3):



        It is even possible to find an Eulerian path in linear time (in the number of edges). Note that there are at most $n^2$ edges in any simple undirected graph (where n is the number of nodes). You can try to find a polynomial algorithm yourself or just look it up on wikipedia. Hint to find the algorithm: Be Greedy.



        4):



        Your assumption is correct. Note that a graph can be colored with 2 colors if and only if it is bipartite. This can be done in polynomial time. My hint is to look at BFS (breadth first search).



        5):



        This is NP-complete. In order to show that you have to show that it is in NP (just give a nondeterministic polynomial algorithm that solves it) and that it is NP-hard. Again this is not very straightforward and you'll need to know about reductions to do this.



        Link to wikipedia's page about reduction: https://en.wikipedia.org/wiki/Reduction_(complexity)



        Feel free to ask if anything I wrote is unclear or if you'd like more information on reductions.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Mar 18 at 20:23









        araomisaraomis

        4039




        4039






























            draft saved

            draft discarded




















































            Thanks for contributing an answer to Mathematics Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3152801%2fis-hamiltoncycle-and-euler-cycle-np-complete-or-not%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            Nidaros erkebispedøme

            Birsay

            Where did Arya get these scars? Unicorn Meta Zoo #1: Why another podcast? Announcing the arrival of Valued Associate #679: Cesar Manara Favourite questions and answers from the 1st quarter of 2019Why did Arya refuse to end it?Has the pronunciation of Arya Stark's name changed?Has Arya forgiven people?Why did Arya Stark lose her vision?Why can Arya still use the faces?Has the Narrow Sea become narrower?Does Arya Stark know how to make poisons outside of the House of Black and White?Why did Nymeria leave Arya?Why did Arya not kill the Lannister soldiers she encountered in the Riverlands?What is the current canonical age of Sansa, Bran and Arya Stark?