Complexity theory {Hamiltonian, DHC, IND}

[needlittlehlp]

Hello,

I need help with a couple of questions.
(The answers haven't come up properly and 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).

Homework Statement

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.

Homework Equations

Notion of '<' reduction; intuition?

The Attempt at a Solution

I've stated by thoughts in brackets.

Like I've said, I am have difficulty in grip into this topic. If I have some solid foundation that I understand (ie: these questions) then I think I will improve my chances for the looming exam. :(


Please help. Thank you very much

 

[Valkarie]

.a) To show that the Hamiltonian Circuit problem (HC) is NP-Complete, you need to use a technique called 'reduction'. In this context, reduction means showing that an instance of HC can be reduced (transformed) into an instance of another problem that is already known to be NP-Complete. This other problem is called the 'target' problem and must already be known to be NP-Complete. One way to do this is to reduce from the Travelling Salesperson Problem (TSP) which is NP-Complete. You can do this by showing that any instance of TSP can be transformed into an equivalent instance of HC. This means that if you have an algorithm for solving HC, then you can also use it for solving TSP. b) To show that Directed Hamiltonian Circuit (DHC) is NP-Complete, you need to show that it can be reduced to HC. This means showing that an instance of DHC can be transformed into an equivalent instance of HC. Once you have done that, you can use the same reduction technique as before to show that HC is NP-Complete.2) To show that k-IND is in Logspace, you need to show that there is an algorithm which can solve the problem using a logarithmic amount of resources. This means that the algorithm needs to use only a logarithmic (O(log n)) amount of memory and time to solve the problem. You can do this by designing a clever algorithm which checks all possible combinations of nodes in the graph in a systematic way and determine whether they form an independent set of size k.