You can find lecture notes here.
The following slides have been done for a one-week school on Graph Theory and Optimization at University of Oulu, Finland, September 15-18th, 2015
- 0) Why is it useful?
Objectives of this school
learn how to model problems (from various domains) using graphs
know the available tools to handle these problem
decide if a problem is ``easy" or ``difficult"
know what to do when facing a ``difficult" problem
- exact exponential algorithms
- parameterized algorithms
- approximation algorithms
1) Introduction to Graphs
Many definitions to be remembered
- graph, vertex/vertices, edge
- neighbor, degree
- path, cycle
- connected graph
- subgraph, spanning subgraph
2) Weighted Graphs: Shortest Paths and Spanning Trees
- weighted graph, distances
- Deciding connectivity
- Shortest path tree in undirected graph O(|E|), (BFS)
- Computing Shortest path tree, (|E| + |V| log |V|) (Dijkstra)
- Computing Min. spanning tree O(|E| log |E|), (Kruskal)
3) Flow: Ford-Fulkerson Algorithm
- flow, cut
- Ford-Fulkerson algorithm, O(|E| flowMax) for rational capacities
- Min Cut = Max Flow
- Menger Theorem (max number disjoint paths = min size of separator)
- Matching (Hungarian method, Edmonds algorithm, Hall Theorem)
4) Computational Complexity (in brief)
- P, NP, NP-hard, NP-complete
- 3-SAT, Hamiltonian path, Coloring, Vertex Cover, ...
- Approximation algorithm
5) Introduction to Linear Programming
- linear programme.
- graphical method of resolution.
- Linear programs can be solved efficiently (polynomial-time).
- Integer programs are a lot harder (in general no known polynomial algorithms)
In this case, we look for approximate solutions.
6) Introduction to Duality in LP
- How to compute a Dual Programme.
- Weak/Strong duality Theorem.
- Optimality certificate (Complementary Slackness).
6.5) Model Graph Problems with LP
- Revisit graph problems (flow, shortest path, cuts, matching...) with LP
- 7) Integer Linear Programming
- ILP allow to model many problems
- there may be a huge integrality gap
(between OPT(LP) and OPT(ILP)).
if no integrality gap (e.g., totally unimodular matrices),
then Fractional Relaxation gives Optimal Integral Solution
concrete example: RWA in WDM networks
8) Approximation Algorithms
- Minimum Vertex Cover vs. Maximum Matching
- Fractional relaxation is a method to obtain for some problems (Vertex Cover, Set Cover):
- Lower bounds on the optimal solution of an integer linear program (minimization).
- Polynomial approximation algorithms (with rounding).
9) Parameterized Algorithms
- Parameterized Problem: input (size n) + parameter k
- FPT algorithm: in time f(k) nO(1)
- Kernelization: Data reduction
- Kernelization <=> FPT
- Linear Kernel for Vertex Cover