Results 1 to 3 of 3

Math Help - complexity theory {Hamiltonian, DHC, IND}

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    5

    Exclamation complexity theory {Hamiltonian, DHC, IND}

    Hello,
    I need help with a couple of questions.
    (The answers haven't come up properly (), are too cryptic and I'm having some difficulty).
    I'm trying really hard to learn this, so could you explain it as fully and clearly as possible - that would be of great help.
    (I find there are some intuitive leaps, or pieces of insight in complexity theory that I don't always see).


    a) How do you show that the Hamiltonian Circuit problem is NP-Complete

    (do you use gadgets? tsp? I think there is a 'clean' way to do it)

    b) If Directed Hamiltonian Circuit is HC but for directed graphs, then how do you show that DHC is NP-Complete
    (some how reduce DHC to HC).


    2) An independent set I is a subset of the nodes of a graph G where: no 2 nodes in I are adjacent in G. For natural number k, the problem k-IND asks if there is an independent set of size k. The problem: How do you show k-IND is in Logspace.




    Thank you very much
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778
    a) How do you show that the Hamiltonian Circuit problem is NP-Complete
    I don't remember right now how to do this, but this is definitely a standard topic. It is most likely proved rigorously in Lewis and Papadimitriou and Sipser. There are also probably places on the Internet that explain this. Are you referring to such places saying that "the answers haven't come up properly"? If you have more specific questions about the proof, we can discuss them.

    Reducing DHC to HC may be somewhat nontrivial (I think I remember seeing a proof), but again I would search the Internet.

    2) An independent set I is a subset of the nodes of a graph G where: no 2 nodes in I are adjacent in G. For natural number k, the problem k-IND asks if there is an independent set of size k. The problem: How do you show k-IND is in Logspace.
    Could you remind how graphs are represented as inputs? I believe the input size is linear w.r.t. the number of vertices and edges; is this so?

    Basically, to decide k-IND it is enough to store k identifiers of vertices. One also needs an algorithm that searches through all k-subsets of vertices (i.e., writes each subset, one after another, into the space reserved for k vertices). Another subroutine that is needed is to check, for given k identifiers of vertices, if they are independent. If vertices are numbered in binary, then the space needed to store k identifiers is logarithmic w.r.t. input -- this is the most important part to check.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2010
    Posts
    5
    Quote Originally Posted by emakarov View Post

    Basically, to decide k-IND it is enough to store k identifiers of vertices. One also needs an algorithm that searches through all k-subsets of vertices (i.e., writes each subset, one after another, into the space reserved for k vertices). Another subroutine that is needed is to check, for given k identifiers of vertices, if they are independent. If vertices are numbered in binary, then the space needed to store k identifiers is logarithmic w.r.t. input -- this is the most important part to check.
    Thank you very much. That's what I got too.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] complexity theorie, deterministic turing-machines, time complexity
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 19th 2011, 06:44 AM
  2. Replies: 0
    Last Post: April 9th 2011, 08:57 AM
  3. O(sin n), Ω(sin n), Θ(sin n) complexity
    Posted in the Advanced Math Topics Forum
    Replies: 4
    Last Post: August 18th 2010, 06:55 AM
  4. Graph Theory Hamiltonian Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 15th 2009, 08:41 PM
  5. Complexity theory
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 14th 2006, 06:47 AM

Search Tags


/mathhelpforum @mathhelpforum