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

0

|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.3k
- Engineering Mathematics 5.2k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.2k
- Theory of Computation 4k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1k
- Others 1.3k
- Admissions 486
- Exam Queries 434
- Tier 1 Placement Questions 17
- Job Queries 56
- Projects 9

36,132 questions

43,578 answers

123,851 comments

42,816 users