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.

+12 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?

+1 vote

actually DHAM is well known npc problem. SHAM is optimization problem which 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.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 559
- Exam Queries 553
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,913 questions

52,293 answers

182,250 comments

67,739 users