Just mentioning additional information.

Dirac's theorem and Ore's theorem are necessary but not sufficient. So 'determining if a Hamiltonian cycle exists' is also NPH.

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+4 votes

Let SHAM$_3$_{ }be the problem of finding a Hamiltonian cycle in a graph $G=(V,E)$ with $|V|$ divisible by $3$ and DHAM$_3$ be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?

- Both DHAM$_3$ and SHAM$_3$ are NP-hard
- SHAM$_3$ is NP-hard, but DHAM$_3$ is not
- DHAM$_3$ is NP-hard, but SHAM$_3$ is not
- Neither DHAM$_3$ nor SHAM$_3$ is NP-hard

0

Just mentioning additional information.

Dirac's theorem and Ore's theorem are necessary but not sufficient. So 'determining if a Hamiltonian cycle exists' is also NPH.

+11 votes

Best answer

+1

|V| is divisible by 3 in both the problems. The difference between DHAM and SHAM is that one is about finding if the Hamiltonian cycle exist and the other one is about finding that cycle.

0

$SHAM_3$: "finding a Hamil..." does not sound as a decision problem. Isnt it? Yes finding if Hamiltonian circuit exists or not is NP-Complete and hence NP-Hard...Am I write?

0 votes

actually DHAM is well known npc problem. SHAM is optimization problem which is relax version of decison problem and is more harder than decision problem so if decison problem is npc then optimization problem willl also be npc as it is more harder .Now DHAM is poly time reducible to SHAM as with DHAM we can have 3 possible cases :1) no of vertices is exactly divisible by 3 then it iss direectly reducible to SHAM 2) if no of vertex is 1mod 3just add 2 extraa vertices 3) if no of vertex 2mod3 add 1 extraa vertex thus every instance of DHAM can be converted to SHAM morever SHAM is verifiable hence np so SHAM is also np complete

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.3k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,903 questions

47,556 answers

146,275 comments

62,304 users