Final Flashcards
Packing Problems
Choose k objects among a set given certain constraints
Independent Set Problem
Given G and k, does G contain an independent set of at least size K
Independent Set
Set of vertices in a graph where no two nodes are adjacent
Set Packing
Given a set U, a collection of S subsets, and k, is there a collection of at least k subsets where no two subsets intersect
Covering Problems
Given a set, choose a subset of only k objects
Vertex Cover Problem
Given G and k, does G contain a vertex cover of at most size k?
Vertex Cover
Set of vertices that includes at least one endpoint of every edge of the graph
Set Cover
Given a set U, a collection of S subsets, and k, is there a collection of at most k subsets whose union is equal to all of U?
Partitioning Problems
Search over all ways to divide a collection of objects into subsets so that each object appears in exactly one of the subsets
3-D Matching Problem
Given disjoint sets X, Y, and Z, each of size n, and given set T as a subset of X x Y x Z of ordered triples, does there exist a set of n triples in T so that each element of X union Y union Z is contained in exactly one of these triples?
Graph Coloring
Given G and k, does G have a k-coloring?
Sequencing Problems
Search over all permutations of a collection of objects
Hamiltonian Cycle
Visits each vertex in G exactly once, starting and ending at the same node
Hamiltonian Cycle Problem
Does a directed graph G contain a Hamiltonian Cycle?
Hamiltonian Path Problem
Does directed graph G contain a Hamiltonian Path
Hamiltonian Path
Visits each vertex in G exactly once
Traveling Salesman
Given a set of distances on n cities, and a bound D, is there a tour length of at most D?
TF: Numerical Problems are always NP-complete
False. For small instances, Dynamic Programming can solve in polynomial time
Subset Sum Problem
Given a set of numbers and a target, is there a subset of numbers that add up to exactly the target?
3-SAT Problem
Given a set of clauses each of length 3 over a set of variables from 1 to n, does there exist a satisfying truth assignment?
NP
Nondeterministic Polynomial Time
Min cut
Cut with minimum outward flow separating s and t
s-t path
P goes from s to t without visiting any node more than once
Ford-Fulkerson Runtime
O(mC) - at most C iterations of max flow on m edges
