You can find lecture notes here.

The following gathers most of the important notions taught during the lecture on ``Graph Algorithms and Optimization" of the Ubinet course.
Some of 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
    • classical algorithms
    • Linear Programming
  • decide if a problem is ``easy" or ``difficult"
  • know what to do when facing a ``difficult" problem
    • exact exponential algorithms
    • parameterized algorithms
    • approximation algorithms
    • heuristics
• 1) Introduction to Graphs
  Many definitions to be remembered
  • graph, vertex/vertices, edge
  • neighbor, degree
  • path, cycle
  • connected graph
  • tree
  • 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)
  Exercises
• 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)
  Exercises
• 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.
  Exercises
• 6) Introduction to Duality in LP
  • How to compute a Dual Programme.
  • Weak/Strong duality Theorem.
  • Optimality certificate (Complementary Slackness).
  Exercises
• 6.5) Model Graph Problems with LP
  • Revisit graph problems (flow, shortest path, cuts, matching...) with LP
  Exercises
• 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) n^O(1)
  • Kernelization: Data reduction
  • Kernelization <=> FPT
  • Linear Kernel for Vertex Cover