The Binary BrothersTwo Mentors, One Mission – Your Selection
All mock tests are FREE till 31 December — register to save your progress
Unit 7 · Data Structures and Algorithms Paper 2 CS · December 2022 Shift 1

In the context of Hamiltonian problems, which of the following are correct?
A. The Hamiltonian cycle problem is NP-complete.
B. If G is an undirected bipartite graph with an odd number of vertices, then G is Hamiltonian.
C. The Hamiltonian path problem cannot be solved in polynomial time on a directed acyclic graph.
D. If G is a connected undirected graph with at least three vertices, then G³ (the graph obtained by connecting all pairs of vertices joined by a path of length at most 3 in G) is Hamiltonian.
E. If any NP-complete problem is polynomial-time solvable, then P = NP.
Choose the most appropriate answer from the options given below:

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: C. A, D, E only

Explanation

A and E are standard results, and D is a known theorem (the cube of a connected graph is Hamiltonian). A bipartite graph with an odd number of vertices can never be Hamiltonian (B false). On a DAG a Hamiltonian path can be found in linear time via topological sort (C false).

More Data Structures and Algorithms questions