.. _np-complete-graph-problems: NP-Complete Graph Problems =========================== The NP-completeness of the SAT problem family is key to proving the NP-completeness or NP-hardness of other problems. In this chapter, we examine graph problems that are NP-complete or NP-hard. The approach is to polynomially reduce each new problem to one previously proven NP-complete, thereby demonstrating its NP-completeness or NP-hardness. These proofs primarily originate from Karp's 1972 paper. In this work, Karp introduced and proved 21 NP-complete problems. These proofs are not inherently difficult. As a mental exercise, it is beneficial to attempt solving the problems independently before reviewing the solutions. .. _largest-independent-set: Largest Independent Set ------------------------- In this section, we prove that the problem of determining whether a graph contains an induced subgraph with :math:`k` vertices and no edges is an NP-complete decision problem, demonstrating that computing :math:`\alpha` (the independence number) of a graph is NP-hard. We reduce this problem to the 3SAT problem. For each clause in the 3SAT input, create three vertices corresponding to its literals and connect them with edges. Then, connect every pair of vertices where one represents a variable and the other its negation. This constructs a graph with :math:`3k` vertices and several edges. Clearly, the independent set of this graph cannot exceed size :math:`k`. Now, this graph has an independent set of this size **if and only if** the original 3SAT instance is satisfiable. This equivalence holds because exactly one literal from each clause must be selected (assigned a true value), and the chosen literals cannot contain conflicting variables (a variable and its negation), meaning they share no edges in the graph and thus form an independent set. It is worth noting that if :math:`k` is a fixed constant (e.g., the problem asks whether a graph contains a triangle), then this problem is **not NP-complete** and can be solved in polynomial time :math:`O(n^k)`. .. _graph-clique-min-vertex-cover: Graph Clique and Minimum Vertex Cover ------------------------------------- The largest clique is equivalent to the largest independent set in the complement graph. Therefore, calculating :math:`\omega` of a graph is also NP-hard. The minimum vertex cover is conversely the complement of the largest independent set. That is, vertices outside the largest independent set form the smallest vertex cover, and vice versa. Hence, the :math:`\beta` of a graph is also an NP-hard problem. .. figure:: /_static/dot/Gadget.svg :width: 50% :align: center :alt: Image of the gadget graph Chromatic Number ---------------- The decision problem of whether an input graph is 3-colorable is an NP-complete problem. From this, it follows that computing the chromatic number :math:`\chi` of a graph is an NP-hard problem. We also reduce this problem to the 3SAT problem. We construct a graph as follows: - Create three vertices True, False, and Neutral, and connect them pairwise. This ensures these vertices cannot share the same color, and their colors will represent the truth or falsity of variables. - For each variable and its negation, place a vertex and connect them with an edge. Also, connect both to the Neutral vertex so they must choose either the True or False color. - For each clause, add a gadget to the graph. A gadget is a subgraph with three external edges and a final vertex. The gadget has the property that if the vertices connected to its three external edges are colored False, the final vertex cannot be colored True; otherwise, it can. For each clause, we connect the gadget's three external edges to the corresponding variable vertices and link the final vertex to the Neutral and False vertices. This forces the final vertex's color to match the True vertex. Thus, a solution exists if and only if the graph can be 3-colored. The only remaining detail is designing the gadget graph. A possible candidate is the following graph: Here, the three external edges are highlighted in blue, and the final vertex in red. You can verify the correctness of this gadget yourself. You may wonder, where did this gadget come from? The design idea is that each triangle acts like a logical OR gate, and by combining two 2-input gates, we obtain a 3-input gate. From previous chapters, you know the 2-colorability problem—unlike the 3-colorability problem, which is NP-complete—can be solved in linear time using the DFS algorithm. .. _hamiltonian-path: Hamiltonian Path --------------------- We reduce this problem to the sat problem. For each clause, we place a vertex, and for each variable, a diamond-shaped structure. The remainder of the proof is available at https://www.geeksforgeeks.org/proof-hamiltonian-path-np-complete/ Hamiltonian Cycle --------------------- We reduce this problem to the Hamiltonian path problem. Consider an arbitrary simple graph :math:`G`. Then, add a new vertex to it and connect it to all existing vertices. Call the new graph :math:`G^{\prime}`. Every Hamiltonian path in graph :math:`G` can be converted into a Hamiltonian cycle in graph :math:`G^{\prime}` by traversing the new vertex, and every Hamiltonian cycle in graph :math:`G^{\prime}` can be converted into a Hamiltonian path in graph :math:`G` by removing the new vertex. Therefore, if we have an algorithm to detect a Hamiltonian cycle, we can use it to detect a Hamiltonian path by adding a vertex. Since the Hamiltonian path problem is NP-complete and the Hamiltonian cycle problem is clearly in NP, the Hamiltonian cycle problem is also NP-complete. .. _longest-path-cycle: Longest Path and Cycle ---------------------- These problems are not decision problems, but since all class NP problems are reducible to them (because Hamiltonian path and cycle are special cases of these two problems), therefore these problems are NP-hard.