Hamiltonian Path

Learned in MATH239 - Introduction to Combinatorics used in CS341.

For clarification, is a Hamiltonian path a path that visits every vertex of graph $G$ only once?

Yes, where each vertex in the path is visited only once.

Checking the existence of a Hamiltonian path is NP-Hard problem, and no efficient algorithm is known for solving the problem.

Hamiltonian Cycle

A Hamiltonian cycle, is a special case of a Hamiltonian path, where the starting and ending vertices are the same, forming a cycle.

The hamiltonian cycle problem is NP-Complete.

Hamiltonian Cycle

A cycle that is a spanning subgraph (i.e., visits all vertices) is called a Hamiltonian cycle.

Determining if a graph has a Hamiltonian cycle or not is in general very difficult - NP-Complete.

Hamiltonian Path in a DAG: Given a directed acyclic graph G, give an algorithm that checks if G has a Hamiltonian path.

Solution: Perform a topological sort on G, and check if $(v_i,v_j)$ is an edge for every $i,j$. This is the only possible hamiltonian path, since there can be no edges going backwards in this order.

Another question:

Apparently $G^{\prime }$ is always a DAG. $\to$ Start with a graph $G$, next compute the SCCs of $G$. We construct a graph $G^{\prime }$, whose vertex set is the SCCs of $G$, and we add a directed edge from an SCC $V_i$ to an SCC $V_j$ if and only if there exist vertices $v_i\in V_{i,}$ $v_{j\in }{V}_j$ such that $(v_{i,}{v}_j)$ is an edge in $G$. The claim is that $G^{\prime }$ is a DAG.