Exponential Algorithms for Finding Hamiltonian Cycles and Paths =============================================================== In this section, we will examine 4 algorithms along with their implementations. These 4 algorithms are very similar to each other but have subtle differences that require careful attention to these distinctions and the fundamental idea behind each one. Hamiltonian Path --------------- Hamiltonian Path Algorithms ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. code-block:: python def hamiltonian_path(graph, start, path=[]): # Hamiltonian algorithm implementation goes here path = path + [start] if len(path) == len(graph.nodes): return path for node in graph.neighbors(start): if node not in path: new_path = hamiltonian_path(graph, node, path) if new_path: return new_path return None Algorithms for finding Hamiltonian paths attempt to discover a path that visits every vertex in a graph exactly once. One common approach is using **backtracking with pruning** which systematically explores potential paths while eliminating impossible branches early. .. note:: The Hamiltonian path problem is **NP-Complete**, meaning for large graphs, finding an exact solution can be computationally prohibitive. In such cases, heuristic approaches or approximations are often used. Algorithm 1 ~~~~~~~~~~~~~ From previous sections, we understood that there is no necessary and sufficient condition for finding Hamiltonian cycles and paths. In other words, this is an NP problem, and no polynomial-time algorithm exists for it. Now we attempt to present an exponential algorithm. Using dynamic programming, we define :math:`dp_{mask, a, b}` as a boolean array indicating whether there exists a Hamiltonian path using vertices in the set :math:`mask`, starting from vertex :math:`a` and ending at vertex :math:`b`. To update this function, it suffices to enumerate over the vertex preceding :math:`b`. Let this vertex be :math:`c`. It is necessary for :math:`c` to be a member of the set :math:`mask`, and there must be an edge between :math:`b` and :math:`c`. Finally, to determine the existence of a Hamiltonian path, we can check all :math:`dp_{2^n-1,i,j}` values for all possible :math:`i` and :math:`j`. Thus, the algorithm implementation will be as follows: .. code-block:: cpp #define bit(n,k) (((n)>>(k))&1) const int maxn = 16; bool dp[1<> n; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) cin >> adj[i][j]; // mohasebe dp for(int mask = 1; mask < (1<>(k))&1) const int maxn = 16; int dp[1<> n; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) cin >> adj[i][j]; // mohasebe dp for(int mask = 1; mask < (1<> j) & 1] # بررسی کامل بودن زیرگراف is_complete = True for v in subset: for u in subset: if v != u and u not in graph[v]: is_complete = False break if not is_complete: break if is_complete: print(f"Complete subgraph found: {subset}") Therefore, we succeeded in reducing the algorithm's time complexity to :math:`O(2^n \times n^2)`. Hamiltonian Cycle ----------------- A **Hamiltonian cycle** is a cycle in a graph that visits every vertex exactly once and returns to the starting vertex. This concept is named after the mathematician William Rowan Hamilton. Determining whether a Hamiltonian cycle exists in a graph is a classic NP-complete problem. .. code-block:: python graph = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E'] } # Define the graph using a dictionary def hamiltonian_cycle(graph, start, current, visited, path): if len(visited) == len(graph): if start in graph[current]: return path + [start] else: return None for neighbor in graph[current]: if neighbor not in visited: result = hamiltonian_cycle(graph, start, neighbor, visited | {neighbor}, path + [current]) if result: return result return None The code above demonstrates a recursive approach to find a Hamiltonian cycle in a graph represented as a dictionary. The algorithm uses backtracking to explore all possible paths and checks if a valid cycle exists. .. image:: images/hamiltonian_cycle.png :alt: Example of a Hamiltonian cycle in a graph ### Key Notes: - If a graph contains a Hamiltonian cycle, it is called a **Hamiltonian graph**. - Unlike Eulerian cycles, there is no simple necessary and sufficient condition for the existence of a Hamiltonian cycle. - Practical applications include optimization problems in logistics, circuit design, and DNA sequencing. Algorithm 1 ~~~~~~~~~~~~~ To check whether a graph contains a Hamiltonian cycle, it suffices to choose an arbitrary vertex like :math:`a`. Then for all neighbors of vertex :math:`a`, such as :math:`b`, we determine whether there exists a Hamiltonian path from :math:`a` to :math:`b`. (If such a path exists, first traverse the Hamiltonian path then traverse the edge :math:`ab`). This can be implemented using the recursive function we described in Algorithm 1 of the previous section. Now we try to improve the algorithm. Since vertex :math:`a` was chosen arbitrarily, we conjecture that by redefining the recursive function, we can achieve an algorithm with better time complexity. We define :math:`dp_{mask,u}` as a boolean array indicating whether starting from vertex :math:`u`, we can visit all vertices in set :math:`mask` and finally reach the smallest member of set :math:`mask`. The difference from the previous definition is that now the endpoint of the Hamiltonian path is determined by :math:`mask`, eliminating the need to add an extra dimension to the state. For updates, you can perform case analysis on the vertex following :math:`u`. .. code-block:: cpp #include #define bit(n,k) (((n)>>(k))&1) using namespace std; const int maxn = 16; bool dp[1<> n; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) cin >> adj[i][j]; // mohasebe dp for(int mask = 1; mask < (1<>(k))&1) const int maxn = 16; int dp[1<> n; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ bool x; cin >> x; if(x){ adj_mask[i] |= 1<