Runtime, Definitions, Theorems

Topics

Graph Algorithms

BFS (Breadth-First Search)

  • Used for finding shortest paths in unweighted graphs.
  • Applications:
    • Testing existence of all-to-all paths.
    • Shortest path in unweighted graphs (all edges same weight).
    • Tree structure/path reconstruction (pred[] array use).
    • Layered traversal.

DFS (Depth-First Search)

  • Used for various graph-based problems including cycle detection.
  • Applications:
    • Testing whether a graph is a DAG.
    • Topological sort.
    • Testing existence of all-to-all paths.
    • Cycle detection.
    • Discovery/finish times.
    • Strongly connected components (SCC).
    • Proof:
      • If ( C_i, C_j ) are SCCs and there is an edge ( C_i \to C_j ) in ( G ), then ( f[C_i] > f[C_j] ).
      • Tree:
        • Case 1: ( d[C_i] < d[C_j] ).
        • Case 2: ( d[C_i] > d[C_j] ).
    • Bridge detection.

Types of Edges

  • Tree edges: Edge that is part of DFS tree.
  • Forward edges: Edge that connects an ancestor to a descendant in DFS.
  • Backward edges: Edge that connects a node to its ancestor (indicating a cycle).
  • Cross edges: Edge that connects two separate DFS trees.

Directed Acyclic Graph (DAG)

  • Checking if a graph is a DAG:
    • Run DFS and check if there is a back edge (i.e., an edge to a gray vertex).
  • Topological Sorting:
    • Run DFS and save each vertex when it finishes on a stack.
    • A DAG always contains a vertex of in-degree 0.
    • Order vertices in reverse finish time.

Strongly Connected Components (SCC)

  • Applications:
    • Finding all cyclic dependencies in code.
    • Data filtering.
    • Identifying maximal SCC containing a source and target.

Minimum Spanning Tree (MST)

  • Kruskal’s Algorithm:
    • Sort edges from light to heavy.
    • Add an edge if it does not create a cycle (use union-find).
  • Union-Find:
    • Used to check whether endpoints are in the same subset.

Shortest Path Algorithms

Dijkstra’s Algorithm

  • Greedy algorithm for single-source shortest paths (requires non-negative weights).
  • Implemented using a priority queue.
  • Runtime: ( O((n+m) \log n) ).

Bellman-Ford Algorithm

  • Similar to Dijkstra’s but allows negative weights.
  • Runs relaxation step ( n-1 ) times.
  • Detects negative-weight cycles.
  • Runtime: ( O(nm) ).

Floyd-Warshall Algorithm

  • All-pairs shortest path (handles negative weights but no negative cycles).
  • Dynamic programming approach.
  • Runtime: ( O(n^3) ).

Maximum Flow & Cut

Max s-t Flow (Max Flow = Min Cut)

  • Residual Graph: Represents remaining capacities.
  • Augmenting Paths: Paths that can increase flow.

Algorithms:

  • Ford-Fulkerson Algorithm:
    • Uses augmenting paths to increase flow.
    • Runtime: ( O(k(n+m)) ).
  • Edmonds-Karp Algorithm:
    • Uses BFS to find augmenting paths.
    • Runtime: ( O(nm^2) ).

Bipartite Graphs

  • Bipartite Matching:
    • Reduce to max-flow problem.
  • Vertex Cover Problem:
    • Bipartite min vertex cover problem.
    • König’s Theorem: ( \text{max matching} = \text{min vertex cover} ).

Facts

  • pred[] induces a tree.
  • Cross edges: Edges in graph but not in pred[].
  • Undirected graphs do not have back edges that “skip” levels in BFS trees.
  • Directed graphs may have such back edges.
  • Bipartiteness:
    • If there were an edge between two red nodes (or two blue nodes), there would be an odd-length cycle.
  • Strong Connectivity:
    • A strongly connected graph allows traversal from any node to any other node.
    • A connected component can consist of a single node with no outgoing edges.
  • SCCs:
    • If DFS is run on nodes in order of largest-to-smallest finish times, we cannot reach other unvisited SCCs.
  • Negative weight cycles:
    • If one exists, there is no shortest path.
    • Negative weight edges in undirected graphs are not allowed.
    • A simple path can always have at most ( n-1 ) edges.
    • If a path has ( n ) edges, a negative cycle must exist.
  • Flow Decomposition:
    • A flow can always be decomposed into capacity-disjoint paths.

Runtime Complexity

Graph Traversals

Algorithm Adjacency List Adjacency Matrix
BFS ( O(n+m) ) ( O(n^2) )
DFS ( O(n+m) ) ( O(n^2) )
Is Strongly Connected? ( O(n+m) ) ( O(n^2) )
Is DAG? ( O(n+m) ) ( O(n^2) )
Topological Sort ( O(n+m) ) ( O(n^2) )
SCC ( O(n+m) ) ( O(n^2) )

MST & Shortest Path

Algorithm Time Complexity
Kruskal’s MST ( O(m \log n) )
Union-Find ( O(m \log n) ) or ( O(\alpha(m + n)) ) (pseudo-linear)
Dijkstra’s Algorithm ( O((n+m) \log n) )
Bellman-Ford ( O(nm) )
Floyd-Warshall ( O(n^3) )

Maximum Flow

Algorithm Time Complexity
Ford-Fulkerson ( O(k(n+m)) )
Edmonds-Karp ( O(nm^2) )

Definitions

  • ( I_u ) denotes ( (d[u], f[u]) ) (discovery & finish times in DFS).
  • ( v ) is white-reachable from ( u ) if there exists a path from ( u ) to ( v ) containing only white nodes.
  • ( G ) is strongly connected iff every node is reachable from every other node.
  • Minimum Spanning Tree (MST):
    • Cut: A partition of vertices into two sets.
    • Cutset: Set of edges crossing the cut.
  • Simple Path: A path in a graph with no repeating vertices.
  • s-t Flow:
    • Assigns a number ( f(e) ) to each edge satisfying:
      • Capacity constraint: ( 0 \leq f(e) \leq c(e) ).
      • Flow conservation: ( \text{flow in} = \text{flow out} ) (except at ( s, t )).
  • Edge-Disjoint Paths:
    • If ( c(e) = 1 ) for all ( e ), cut capacity equals the number of edges crossing the cut.
  • Residual Graphs:
    • Represents remaining capacity after flow assignment.

Complexity Classes

P (Polynomial Time)

  • The set of all decision problems that have polynomial-time algorithms solving them.
  • Formal Definition:
    • A problem ( \Pi ) is in P if there exists a deterministic algorithm that solves it in ( O(n^k) ) time for some constant ( k ).

NP (Non-Deterministic Polynomial Time)

  • The set of all decision problems that can be solved using a polynomial-time verification algorithm.
  • No oracle is needed: We assume a certificate (or witness) is provided by an oracle.
  • To show a problem is in NP:
    1. Define a valid certificate.
    2. Design a polynomial-time verification algorithm that checks if the certificate is valid.

NP-Complete (NPC)

  • The set of all decision problems ( \Pi ) such that:
    • ( \Pi \in \text{NP} ) (i.e., it has a polynomial-time verification algorithm).
    • For all problems ( \Pi’ \in \text{NP} ), we can polynomially reduce ( \Pi’ ) to ( \Pi ) (i.e., ( \Pi’ \leq_P \Pi )).

NP-Hard (NPH)

  • The set of all problems (not necessarily decision problems) that are at least as hard as the hardest NP problems.
  • A problem is NP-Hard if every problem in NP can be reduced to it in polynomial time.
  • Unlike NPC, an NP-Hard problem does not have to be in NP (i.e., it may not be a decision problem).

Theorems

Graph Theory

Bipartite Graph

  • A graph is bipartite if and only if it does not contain an odd-length cycle.

Depth-First Search (DFS)

Let ( u, v ) be any node. The following are equivalent:

  • ( v ) is white-reachable from ( u ) when we call DFSVisit(u).
  • ( v ) turns grey after ( u ) and black before ( u ).
  • Discovery/finish time interval ( I_v ) is nested inside ( I_u ).
  • ( v ) is discovered during DFSVisit(u).
  • ( v ) is a descendant of ( u ) in the DFS forest.
  • For each pair of nodes ( u, v ), the intervals of ( u ) and ( v ) are either disjoint or nested.

Strongly Connected Graph

  • A graph is strongly connected if and only if for any node ( s ), all nodes are reachable from ( s ), and ( s ) is reachable from all nodes.

Directed Acyclic Graph (DAG)

  • A directed graph is a DAG if and only if depth-first search encounters no back edges.
  • A DAG contains a vertex of in-degree 0.
  • If ( D ) is a DAG, and we order vertices in reverse order of finishing time (largest to smallest finishing time), then we get a topological ordering.
  • Suppose ( D ) is a DAG, then ( f[v] < f[u] ) for every arc ( u \to v ).
  • If ( C_i, C_j ) are strongly connected components (SCCs) and there is an edge ( C_i \to C_j ) in ( G ), then ( f[C_i] > f[C_j] ).

Tree Properties

  • A tree on ( n ) vertices has ( n-1 ) edges.
  • There is a unique path between any two vertices.
  • If ( T ) is a tree and an edge ( e’ ) is in cycle ( C ), then ( T \cup {e} \setminus {e’} ) is a tree.

Minimum Spanning Tree (MST)

  • For any cut of a graph ( G ), the minimum weight edge in the cutset is in every MST for ( G ).

Flow-Cut Theorem

  • The max ( s )-( t ) flow has value equal to the capacity of the minimum ( s )-( t ) cut ((\max) flow = (\min) cut).

König’s Theorem

  • ( | \text{max matching} | = | \text{min vertex cover} | ).

Augmenting Flow

  • Augment() improves the flow.
  • If ( f ) is an ( s )-( t ) flow such that there is no ( s )-( t ) path in the residual graph ( R ), then there is an ( s )-( t ) cut ( S ) such that ( \text{value}(f) = \text{capacity}(S) ).

Types of Problems

NPC:

3-SAT, Clique(G, k), Independent Set, Vertex Cover(G, k), Hamiltonian cycle/path (both directed and undirected), Subset Sum, subGisomorphic

Clique
Does G contain clique size >= k

Vertex Cover
Does G contain vertex cover size <= k

Independent Set
Set of vertex where no vertices are adjacent

SAT
Given boolean formula, is there a truth assignment s.t. F evaluates to true

3-SAT
SAT with m clauses but each clause have exactly 3 literals

Hamiltonian cycle
Does G contain a ham cycle given an undirected graph

TSP-decision
Does G contain a ham cycle with w(H)<=T

Subset sum
Given a list of S and target T, all positive ints, does there exist a subset s.t. Sum of s = T

0-1 Knapsack
List of profits is a list of weights W, capacity M, and target profit T. Is there a tuple s.t. wx<=M and px>=T

Divide and Conquer

Ex.: mergesort, quicksort O(nlogn)
Bently’s problem O(nlogn)
Non-dominated points O(nlogn)
Multiprecision multiplication (takeaway: can reduce recursion to lower and d+c isnt always faster) O(nlog3)
Matrix multiplication O(nlog7)
Selection problem O(n)
Median-of-medians quickselect O(n)
Closest pair O(nlogn)
Binary search O(logn)

Greedy

Interval selection O(nlogn)
Knapsack O(n*m)
Interval Coloring O(nlogn)
Improved using heap

Dynamic Programming (“how many ways”)

Fibonacci O(n)
Longest common sequence O(n+m)
Rod Cutting 𝚯(n^2)
0-1 knapsack t:𝚯(n) s:O(m)
Minimal length triangulation O(n3)

Proof Strategy

Divide and Conquer

To write

  • Base case, divide, conquer, merge/compute

**Prove correctness **

  • Induction (base case, combination step)
    • Prove base cases are correct
    • Inductively assume subproblems are solved correctly
    • Show they are correctly assembled into a solution

Greedy

To write

  • Usually require some pre processing of the input data
  • List out strategies
    • Prove incorrectness
  • Prove correctness
    • Feasibility (direct)
    • Optimal (contradiction suppose O is better than X)
      • Greedy stays ahead (induction)
        • show every choice in 𝑋 is “at least as good” as the corresponding choice in O
      • Exchange
        • show 𝑂 can be improved by replacing some choice in 𝑂 with a choice in X
      • Other arguments

Greedy stays ahead
Use: if optimal solution have different sizes (explain why solution must be no bigger/smaller than the optimal solution)

  • Let G be greedy sol, let O be optimal sol
  • Reorder choices in O to line up with choices in G
  • Assume choices 1…i-1 in G >=(good) reordered choices O
  • Hold for i
  • All choices made in G >=(good) O
  • G is optimal

Exchange Arguments
Use: same size and differ in cost (justify how to remove some part of solution and snap another in place)
how that if 𝑂 differs from G, then you can change O to be more like G without losing optimality

  • If inputs are distinct
    • There is a unique optimal solution
    • Let O!=G be an optimal solution that beats greedy
    • Show how to change O to obtain a better solution
  • If not
    • There may be many optimal solutions
    • Let O!=G be an optimal solution that matches greedy on as many choices as possible
    • Show how to change O to obtain an optimal solution O’ that matches greedy for even more choices

DP

Building a table of results bottom-up

  • Is the problem broken down into overlapping problems? Yes then dp
  • State: What does dp[i] stand fo
  • Transition: how to get to current dp[i]
  • Base case
  • Recurrence
  • Pseudocode
  • Correctness
  • Time complexity

Graphs

Proof by contradiction that our solution is optimal

  • E.g. if this can be done by positive weights can it be transformed to apply negative weights.
  • How to transform hamiltonian cycle into a MSt

Graph proof tips

  • COMMON!!! To show da(v) = db(v) (or arr[u] = smth) show <= and >=
  • Induction
  • Need to first prove there exist shortest shortest path (i.e. all weights are +’ve edges)

Polytime Turing Reduction

  • Relates two problems to each other.
  • Does not require problems to be decision problems.

Correctness
The return value must be correct for every possible input.

Polynomial Time Complexity
The runtime is polynomial in the input size.

  • Must show polynomial complexity in terms of some lower bound on the input size.

Showing a Problem is in NP

  1. Define a Yes-Certificate: A piece of evidence that certifies an instance is a “yes” instance.
  2. Design a Polynomial-Time Verification Algorithm:
    • verify(I, C): Algorithm that verifies the correctness of the certificate in polynomial time.
    • The oracle can return anything if false, so ensure:
      • Certificate data type is correct.
      • Certificate size is bounded.

Correctness Proof

  • For Yes-Instances: Let ( I ) be any yes-instance. Find a certificate ( C ) such that verify(I, C) = true.
  • For No-Instances: Let ( I ) be any no-instance and ( C ) be any certificate. Prove that verify(I, C) = false.
  • If verify(I, C) = true, then ( I ) is a yes-instance.

Polynomial Transformations (Karp Reduction)

  • Use for:
    • Proving NP-Completeness
    • Proving impossibility results

Steps:

  1. Specify function ( f(I) ): Transform instance ( I ) of problem ( \Pi_1 ) into instance ( f(I) ) of problem ( \Pi_2 ).
  2. Prove ( f(I) ) runs in polynomial time.
  3. Show correctness:
    • ( I ) is a yes-instance of ( \Pi_1 ) iff ( f(I) ) is a yes-instance of ( \Pi_2 ).

Proving Our Problem is NP-Complete (NPC)

  1. Show an NP-Complete Problem Reduces to Our Problem:
    • ( \text{NPC problem} \leq_P ) our problem (via polynomial transformation).
    • Only transform the input.
  2. Prove Our Problem is in NP:
    • Define a yes-certificate.
    • Provide a polynomial-time verification algorithm.

Proving a Problem is Undecidable

  • Show one instance that either:
    • Returns a wrong answer.
    • Runs forever (i.e., does not halt).

Proving a Problem is NP-Hard

  1. Use Turing Reductions from the Halting Problem:
    • If a problem can solve the halting problem, it is NP-hard.
  2. Prove the Problem is NPC:
    • Since all problems in NPC are NP-Hard.

NP-Hardness Definition:

  • A problem is NP-Hard if every problem in NP can be reduced to it in polynomial time.

Karp Reduction vs. Turing Reduction

  • Karp Reduction is a special case of Turing Reduction:
    • Existence of a Karp Reduction proves NP-Completeness.
    • Existence of a Turing Reduction proves NP-Hardness.

logic problem -> 3SAT
vertex cover type problem -> Vertex Cover
path problem -> Hamiltonian path/cycle (directed or undirected)

Exam Tips

Midterm

Runtime
- Recursion tree
- Substitution / guess+check+induction
- Master theorem
Divide and conquer
Greedy
- Feasible
- Disprove greedy strategy
- Greedy stays ahead
- Exchange argument
DP

Final Topics

Short Answer Reasons

  • EXPTime
  • Runtime analysis
  • Designing an algorithm
    • How it works, and how to use it, or modify it if necessary, to solve a problem (e.g., shortest path problem).

Proving Polynomial Time Equivalence (Turing Reduction)

  • Show problem is in NPC.
  • Karp reduction:
    • Give ( F(I) ) in polytime.
    • Show ( I ) is a yes-instance of ( \Pi_1 ) iff ( F(I) ) is a yes-instance of ( \Pi_2 ).

Showing a Problem is in NP

  • Define a Yes-Certificate.
  • Design verify(I, C) in polynomial time.
  • Ensure verify(I, C) = true iff ( G ) is a yes-instance.

Proving a Problem is Undecidable

  • Turing reduction to the Halting Problem.
  • Proof by non-existence of an algorithm:
    • Show that there cannot exist an algorithm ( A ) such that, for every instance ( I ), ( A(I) ) returns the correct answer in finite time.