NP-Completeness Theory for Graph Algorithms in CSCE-411

CSCE-411 Design and Analysis of Algorithms Spring 2025 Instructor: Jianer Chen Office: PETR 428 Phone: 845-4259 Email: chen@cse.tamu.edu Notes 33: NP-completeness Theory

NP-Completeness Theory Try to tell you how to avoid solving a problem (because it is too hard).

NP-Completeness Theory Try to tell you how to avoid solving a problem (because it is too hard). Project A. Write a useable program (algorithm) that, given a weighted graph G and two vertices s and t, finds a shortest path from s to t. Project B. Write a useable program (algorithm) that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t.

NP-Completeness Theory Try to tell you how to avoid solving a problem (because it is too hard). Project A. Write a useable program (algorithm) that, given a weighted graph G and two vertices s and t, finds a shortest path from s to t. Assigned to your colleague Project B. Write a useable program (algorithm) that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Assigned to you

NP-Completeness Theory Try to tell you how to avoid solving a problem (because it is too hard). Project A. Write a useable program (algorithm) that, given a weighted graph G and two vertices s and t, finds a shortest path from s to t. Assigned to your colleague: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson, . Project B. Write a useable program (algorithm) that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Assigned to you

NP-Completeness Theory Try to tell you how to avoid solving a problem (because it is too hard). Project A. Write a useable program (algorithm) that, given a weighted graph G and two vertices s and t, finds a shortest path from s to t. Assigned to your colleague: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson, . Project B. Write a useable program (algorithm) that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Assigned to you: Dijkstra?

NP-Completeness Theory Try to tell you how to avoid solving a problem (because it is too hard). Project A. Write a useable program (algorithm) that, given a weighted graph G and two vertices s and t, finds a shortest path from s to t. Assigned to your colleague: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson, . Project B. Write a useable program (algorithm) that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Assigned to you: Dijkstra,

NP-Completeness Theory Try to tell you how to avoid solving a problem (because it is too hard). Project A. Write a useable program (algorithm) that, given a weighted graph G and two vertices s and t, finds a shortest path from s to t. Assigned to your colleague: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson, . Project B. Write a useable program (algorithm) that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Assigned to you: Dijkstra, Bellman-Ford?

NP-Completeness Theory Try to tell you how to avoid solving a problem (because it is too hard). Project A. Write a useable program (algorithm) that, given a weighted graph G and two vertices s and t, finds a shortest path from s to t. Assigned to your colleague: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson, . Project B. Write a useable program (algorithm) that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Assigned to you: Dijkstra, Bellman-Ford,

NP-Completeness Theory Try to tell you how to avoid solving a problem (because it is too hard). Project A. Write a useable program (algorithm) that, given a weighted graph G and two vertices s and t, finds a shortest path from s to t. Assigned to your colleague: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson, . Project B. Write a useable program (algorithm) that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Assigned to you: Dijkstra, Bellman-Ford, Floyd-Warshall?

NP-Completeness Theory Try to tell you how to avoid solving a problem (because it is too hard). Project A. Write a useable program (algorithm) that, given a weighted graph G and two vertices s and t, finds a shortest path from s to t. Assigned to your colleague: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson, . Project B. Write a useable program (algorithm) that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Assigned to you: Dijkstra, Bellman-Ford, Floyd-Warshall,

NP-Completeness Theory Try to tell you how to avoid solving a problem (because it is too hard). Project A. Write a useable program (algorithm) that, given a weighted graph G and two vertices s and t, finds a shortest path from s to t. Assigned to your colleague: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson, . Project B. Write a useable program (algorithm) that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Assigned to you: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson?

NP-Completeness Theory Try to tell you how to avoid solving a problem (because it is too hard). Project A. Write a useable program (algorithm) that, given a weighted graph G and two vertices s and t, finds a shortest path from s to t. Assigned to your colleague: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson, . Project B. Write a useable program (algorithm) that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Assigned to you: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson, .

NP-Completeness Theory Try to tell you how to avoid solving a problem (because it is too hard). Project A. Write a useable program (algorithm) that, given a weighted graph G and two vertices s and t, finds a shortest path from s to t. Assigned to your colleague: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson, . Project B. Write a useable program (algorithm) that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Assigned to you: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson, . XXXXXXXXXXXXXX

NP-Completeness Theory Try to tell you how to avoid solving a problem (because it is too hard). Project A. Write a useable program (algorithm) that, given a weighted graph G and two vertices s and t, finds a shortest path from s to t. Assigned to your colleague: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson, . Project B. Write a useable program (algorithm) that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Assigned to you: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson, . XXXXXXXXXXXXXX

NP-Completeness Theory What you will do next? Project B. Write a useable algorithm that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Assigned to you: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson, . XXXXXXXXXXXXXX

NP-Completeness Theory What you will do next? Project B. Write a useable algorithm that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Assigned to you: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson, . XXXXXXXXXXXXXX Work harder

NP-Completeness Theory What you will do next? Project B. Write a useable algorithm that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Assigned to you: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson, . XXXXXXXXXXXXXX Work harder Does not help I guarantee that you would not solve it.

NP-Completeness Theory What you will do next? Project B. Write a useable algorithm that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Assigned to you: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson, . XXXXXXXXXXXXXX Work harder Does not help I guarantee that you would not solve it. Tell your boss the problem is difficult

NP-Completeness Theory What you will do next? Project B. Write a useable algorithm that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Assigned to you: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson, . XXXXXXXXXXXXXX Work harder Does not help I guarantee that you would not solve it. Tell your boss the problem is difficult Your boss is not going to be convinced

NP-Completeness Theory What you will do next? Project B. Write a useable algorithm that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Assigned to you: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson, . XXXXXXXXXXXXXX Work harder Does not help I guarantee that you would not solve it. Tell your boss the problem is difficult Your boss is not going to be convinced Tell your boss you are not as good as your colleague

NP-Completeness Theory What you will do next? Project B. Write a useable algorithm that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Assigned to you: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson, . XXXXXXXXXXXXXX Work harder Does not help I guarantee that you would not solve it. Tell your boss the problem is difficult Your boss is not going to be convinced Tell your boss you are not as good as your colleague In fact, you are innocent:

NP-Completeness Theory What you will do next? Project B. Write a useable algorithm that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Assigned to you: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson, . XXXXXXXXXXXXXX Work harder Does not help I guarantee that you would not solve it. Tell your boss the problem is difficult Your boss is not going to be convinced Tell your boss you are not as good as your colleague In fact, you are innocent: Nobody (in the world) can give a useable algorithm for this problem

NP-Completeness Theory What you will do next? Project B. Write a useable algorithm that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Assigned to you: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson, . XXXXXXXXXXXXXX Work harder Does not help I guarantee that you would not solve it. Tell your boss the problem is difficult Your boss is not going to be convinced Tell your boss you are not as good as your colleague In fact, you are innocent: Nobody (in the world) can give a useable algorithm for this problem Nobody (in the world) can prove that the problem is difficult.

NP-Completeness Theory Project B. Write a useable algorithm that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Nobody (in the world) can give a useable algorithm for the problem Nobody (in the world) can prove that the problem is difficult.

NP-Completeness Theory Project B. Write a useable algorithm that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Nobody (in the world) can give a useable algorithm for the problem Nobody (in the world) can prove that the problem is difficult.

NP-Completeness Theory Project B. Write a useable algorithm that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Nobody (in the world) can give a useable algorithm for the problem Nobody (in the world) can prove that the problem is difficult. What is a useable algorithm? an algorithm that is fast enough.

NP-Completeness Theory Project B. Write a useable algorithm that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Nobody (in the world) can give a useable algorithm for the problem Nobody (in the world) can prove that the problem is difficult. What is a useable algorithm? an algorithm that is fast enough. A problem is feasible if it can be solved by a useable algorithm.

NP-Completeness Theory Project B. Write a useable algorithm that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Nobody (in the world) can give a useable algorithm for the problem Nobody (in the world) can prove that the problem is difficult. What is a useable algorithm? an algorithm that is fast enough. A problem is feasible if it can be solved by a useable algorithm.

NP-Completeness Theory Project B. Write a useable algorithm that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Nobody (in the world) can give a useable algorithm for the problem Nobody (in the world) can prove that the problem is difficult. What is a useable algorithm? an algorithm that is fast enough. A problem is feasible if it can be solved by a useable algorithm. What problem is difficult? A problem that is infeasible. i.e., a problem that has no useable algorithms.

NP-Completeness Theory Project B. Write a useable algorithm that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Nobody (in the world) can give a useable algorithm for the problem Nobody (in the world) can prove that the problem is difficult. What is a useable algorithm? an algorithm that is fast enough. A problem is feasible if it can be solved by a useable algorithm. What problem is difficult? A problem that is infeasible. i.e., a problem that has no useable algorithms. But how can you know (prove) that a problem has no useable algorithms?

NP-Completeness Theory Project B. Write a useable algorithm that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Nobody (in the world) can give a useable algorithm for the problem Nobody (in the world) can prove that the problem is difficult. What is a useable algorithm? an algorithm that is fast enough. A problem is feasible if it can be solved by a useable algorithm. What problem is difficult? A problem that is infeasible. i.e., a problem that has no useable algorithms. But how can you know (prove) that a problem has no useable algorithms? Nobody can.

NP-Completeness Theory Project B. Write a useable algorithm that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Nobody (in the world) can give a useable algorithm for the problem Nobody (in the world) can prove that the problem is difficult. What is a useable algorithm? an algorithm that is fast enough. A problem is feasible if it can be solved by a useable algorithm. What problem is difficult? A problem that is infeasible. i.e., a problem that has no useable algorithms. But how can you know (prove) that a problem has no useable algorithms? Nobody can. But we have NP-completeness theory.

NP-Completeness Theory Project B. Write a useable algorithm that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Nobody (in the world) can give a useable algorithm for the problem Nobody (in the world) can prove that the problem is difficult. What is a useable algorithm? an algorithm that is fast enough. A problem is feasible if it can be solved by a useable algorithm. What problem is difficult? A problem that is infeasible. i.e., a problem that has no useable algorithms. But how can you know (prove) that a problem has no useable algorithms? Nobody can. But we have NP-completeness theory. The theory developed a framework that enables to prove that the given problem belongs to a class of (over thousands) problems that are all equivalent, in the sense that if you find a useable algorithm for any single of these problems, then you have useable algorithms for all (> 2,000) problems in the class.

NP-Completeness Theory Project B. Write a useable algorithm that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Nobody (in the world) can give a useable algorithm for the problem Nobody (in the world) can prove that the problem is difficult. What is a useable algorithm? an algorithm that is fast enough. A problem is feasible if it can be solved by a useable algorithm. What problem is difficult? A problem that is infeasible. i.e., a problem that has no useable algorithms. But how can you know (prove) that a problem has no useable algorithms? Nobody can. But we have NP-completeness theory. The theory developed a framework that enables to prove that the given problem belongs to a class of (over thousands) problems that are all equivalent, in the sense that if you find a useable algorithm for any single of these problems, then you have useable algorithms for all (> 2,000) problems in the class. Current Status: No one in the world (including the smartest ones) has been able to find a useable algorithm for any single of the problems in the class.

NP-Completeness Theory Project B. Write a useable algorithm that, given a weighted graph G and two vertices s and t, finds a longest simple path from s to t. Nobody (in the world) can give a useable algorithm for the problem Nobody (in the world) can prove that the problem is difficult. What is a useable algorithm? an algorithm that is fast enough. A problem is feasible if it can be solved by a useable algorithm. What problem is difficult? A problem that is infeasible. i.e., a problem that has no useable algorithms. But how can you know (prove) that a problem has no useable algorithms? Nobody can. But we have NP-completeness theory. The theory developed a framework that enables to prove that the given problem belongs to a class of (over thousands) problems that are all equivalent, in the sense that if you find a useable algorithm for any single of these problems, then you have useable algorithms for all (> 2,000) problems in the class. Current Status: No one in the world (including the smartest ones) has been able to find a useable algorithm for any single of the problems in the class. Thus, if your problem belongs to this class, you probably want to consider quitting (hopeless, unless you are smarter than all smartest computer scientists in the world).

NP-Completeness Theory If a problem Q can be solved in polynomial time, i.e., in time O(nc) for a constant c, then we consider Q feasible.

NP-Completeness Theory If a problem Q can be solved in polynomial time, i.e., in time O(nc) for a constant c, then we consider Q feasible. Let P to be the class of all problems solvable in polynomial time.

NP-Completeness Theory If a problem Q can be solved in polynomial time, i.e., in time O(nc) for a constant c, then we consider Q feasible. Let P to be the class of all problems solvable in polynomial time. Examples. All problems we have studied in this class are in P. Sorting: O(n log n) = O(n2) Longest Common Subsequence: O(n2) Many graph problems solvable based on DFS and BFS: O(m+n) = O(L) Single Source Shortest Path: Dijktra: O(n2) or O(m log n) = O(n3), Bellman-Ford: O(nm) = O(n3) All-Pairs Shortest Path: Floyd-Warshall: O(n3), Johnson: O(nm log n) = O(n4) Minimum Spanning Tree: O(n2) or O(m log n) = O(n3), Bipartite Graph Matching: O(nm) = O(n3),

NP-Completeness Theory If a problem Q can be solved in polynomial time, i.e., in time O(nc) for a constant c, then we consider Q feasible. Let P to be the class of all problems solvable in polynomial time. Consider the following problems: Vertex Cover (VC). Given a graph G and an integer k, can we find a set C of k vertices in G such that every edge of G has at least one end in C?

NP-Completeness Theory If a problem Q can be solved in polynomial time, i.e., in time O(nc) for a constant c, then we consider Q feasible. Let P to be the class of all problems solvable in polynomial time. Consider the following problems: Vertex Cover (VC). Given a graph G and an integer k, can we find a set C of k vertices in G such that every edge of G has at least one end in C? Independent Set (IS). Given a graph G and an integer k, can we find a set I of k vertices in G such that no two vertices in I are adjacent?

NP-Completeness Theory If a problem Q can be solved in polynomial time, i.e., in time O(nc) for a constant c, then we consider Q feasible. Let P to be the class of all problems solvable in polynomial time. Consider the following problems: Vertex Cover (VC). Given a graph G and an integer k, can we find a set C of k vertices in G such that every edge of G has at least one end in C? Independent Set (IS). Given a graph G and an integer k, can we find a set I of k vertices in G such that no two vertices in I are adjacent? Satisfiability (SAT). Given a CNF formula F = F(x1, x2, , xn), is there an assignment to x1, x2, , xn such that F = true?

NP-Completeness Theory If a problem Q can be solved in polynomial time, i.e., in time O(nc) for a constant c, then we consider Q feasible. Let P to be the class of all problems solvable in polynomial time. Consider the following problems: Vertex Cover (VC). Given a graph G and an integer k, can we find a set C of k vertices in G such that every edge of G has at least one end in C? Independent Set (IS). Given a graph G and an integer k, can we find a set I of k vertices in G such that no two vertices in I are adjacent? Satisfiability (SAT). Given a CNF formula F = F(x1, x2, , xn), is there an assignment to x1, x2, , xn such that F = true? Partition. Given a set S = {a1, a2, , an} of n integers, is there a way to partition S into S1 and S2 such that S1 and S2 have the same sum?

NP-Completeness Theory If a problem Q can be solved in polynomial time, i.e., in time O(nc) for a constant c, then we consider Q feasible. Let P to be the class of all problems solvable in polynomial time. Consider the following problems: Vertex Cover (VC). Given a graph G and an integer k, can we find a set C of k vertices in G such that every edge of G has at least one end in C? Independent Set (IS). Given a graph G and an integer k, can we find a set I of k vertices in G such that no two vertices in I are adjacent? Satisfiability (SAT). Given a CNF formula F = F(x1, x2, , xn), is there an assignment to x1, x2, , xn such that F = true? Partition. Given a set S = {a1, a2, , an} of n integers, is there a way to partition S into S1 and S2 such that S1 and S2 have the same sum? These problems have wide applications in practice, but no one knows how to solve any of them efficiently (i.e., are they in P ?)