Monday, May 01, 2017 (Lecture 1): Administrivia. Intro to planar graphs
Main question of the course: given a graph class C, what problems
can be solved easy/easier than on arbitrary graphs?
Some graph classes. Planar graphs. Interval graphs. Partial k-trees.
Administrivia. How grades are determined.
Planar graph definition. Examples. K5 is not planar.
That makes the Clique problem polynomial in planar graphs.
K5 is not planar, so clique-size at most 4. Brute-force
algorithm is polynomial.
Graph assumptions: simple, connected, undirected and big enough.
Graph are stored with incidence lists. Many graph operations are O(1),
but testing existence of an edge is not (at least not with this data
structure.)
Four tools to solve problems in planar graphs:
(a) use some property of planar graphs,
(b) use the planar embedding,
(c) try the problem in the dual graph,
(d) use the planar separator theorem for a divide-and-conquer approach.
We've seen (a). To use (b), need some definitions.
Rotational system. Faces. Facial circuits. Planar embedding.
Given a rotational system, any face could be the outer-face.
Whitney's theorem: If there are no cutting pairs, then the rotational
system is unique (up to reversal). No proof.
Example for (b): Menger problem. Right-hand search
is steered by the planar embedding. Sketch of why this finds the maximum
set of paths.
Wednesday, May 03, 2017 (Lecture 2): Solving problems in planar graphs
Euler's formula. Proof. Lots of consequences.
Every simple connected
planar graph with at least 3 vertices has at most 3n-6 edges.
K5 is not planar.
Every simple connected
planar bipartite graph with at least 3 vertices has at most 2n-4
edges. K3,3 is not planar.
These are in some sense the only non-planar graphs. Kuratowski's
theorem (no proof).
Different types of subgraph: spanning subgraph, induced subgraph, subdivision,
minor.
Algorithmic consequences of Euler's formula:
Use m≤3n to simplify/speed up algorithms.
Example: Shortest path.
Find min-degree order, then every vertex has indegree at most 5.
Coloring. Every planar graph can be colored with 6 colours.
Proof via min-degree-ordering and greedy-algorithm. Brief mention of
4-color theorem, no proof.
Can store planar graphs to answer adjacency queries in constant time.
Finding maximum cliques in planar graphs in linear time, using the
min-degree ordering.
Some problems that remain NP-hard in planar graphs, and how to prove this.
Method 1: crossing gadget to remove a crossing without affecting solutions
of the problem. Example: 3-coloring. The crossing gadget and its colorings.
How to insert the crossing gadget into a suitable drawing. In consequence,
3-coloring is NP-hard even in planar graphs
Similar approach for 3SAT. The graph of a 3SAT instance. Planar3SAT =
instances of 3SAT where this graph is planar. Theorem: This is NP-hard.
Proof via crossing gadget (no details).
Week 2
Monday, May 08, 2017 (Lecture 3): Maximum Flow
Method 2 for proving NP-hardness in planar graphs: create
reductions that preserve planarity. Example: Independent
Set. Reduction from 3-SAT to Independent Set. Observe: if 3SAT
graph is planar, then so is constructed graph.
In consequence, Independent Set is NP-hard even in planar graphs of
max-degree 3.
Maximum-flow problem. Definition. Brief mention of algorithms (no detail).
(s,t)-cuts and their values. The MaxFlowMinCut theorem. Sketch of proof of
easy direction. Now: Maximum flow in planar graphs.
Really solve minimum cut instead.
Intuition: (s,t) cuts become circles that separate s and t.
To make this rigolous, detour into dual graphs. Definition. Some
properties. Dual graphs are not well-defined if graph is not connected.
Back to flows. Minimum (s,t) cuts become shortest
cycles in dual graph that that separate s and t. Special case here only:
both s and t on outer-face.
Rather than finding cycles, split outer-face and find shortest
path. Proof of correctness via recovering
a flow from distances in dual. This flow-value
matches the cut-value, so both are optimal.
Towards planarity testing. Bush forms. Lemma: If
V-V' forms a connected graph, then bush form has a planar embedding
with all leaves on outer-face.
Wednesday, May 10, 2017 (Lecture 4): Planarity testing. Triangulated graphs
Planarity testing idea: Expand bush forms while maintaining all
possible embeddings with all leaves on outer-face.
Details. Explore graph in reverse DFS-order. Store bush forms of subtrees
that were explored. To add one vertex, must get its leaves in each bush
form of child consecutive. If this fails, then graph was not planar.
Some details of how to store bush forms.
PQ-trees. P-nodes, Q-nodes, permitted changes, permissible leaf orders.
Main operation: test whether set of leaves can be made consecutive. Some
ideas that this can be checked with finite set of rules, applied at each
node of PQ-tree. No details about fast implementation.
Maximal planar graphs. Triangulated graphs. Equivalence.
Triangulated graphs have 3n-6 edges, 2n-4 faces, and are
3-connected. Corollary:
Can make a graph triangulated by adding edges. This can be
done in linear time (no details).
The canonical order. Definition and examples. Every triangulated
graph has a canonical order. Proof.
Week 3
Monday, May 15, 2017 (Lecture 5): Canonical ordering. 4-connected triangulations
Properties of canonical ordering. The predecessors of vk+1
form an interval on the outerface of graph Gk.
Canonical orderings can be used to find forests. How to label the
edges. We obtain three rooted trees (also known as Schnyder wood.)
Canonical orderings are good for obtaining graph drawings.
Every planar graph has a visibility representation.
Invariants to maintain while adding vertices. How to add a vertex.
Corollary: every planar graph is a grid-minor.
Every planar graph has a planar straight-line drawing.
Invariants to maintain while adding vertices. How to add a vertex.
4-connected graphs. Cutting triplets. A planar triangulation is
4-connected if and only if it has no separating triangle. Proof.
(2,2)-ordering for 4-connected triangulations. Proof of existence.
No details of applications.
Hamiltonian Cycle problem. NP-hard, even in planar graphs (no details).
Every 4-connected planar graph has a Hamiltonian Cycle. Proof only
for triangulations. The chord condition cc(A,B,C). Every graph that
satisfies this has Hamiltonian Path from A to B. Proof by ``peeling away''
path from A to C and combining resulting Hamiltonian Paths.
Wednesday, May 17, 2017 (Lecture 6): Friends of planar graphs
Superclasses of planar graphs. Graphs embedded in 3D without crossings.
That's all graphs. Sketch of how to prove this. Knotless graphs.
Linkless graphs. (No details on either.)
Graphs embedded in surface of
higher genus. K6 is toroidal. Rotational system, faces, dual graph all
transfer. Many algorithmic results can be transferred, but not always.
(No details.)
Near-planar graphs. Graphs with small crossing number. Graphs with small
skewness. k-planar graphs. How 1-planar graphs are obtained by combining
planar graph and its dual. Many results known about them (no detail.)
Subclasses of planar graphs.
Outer-planar graphs. Characterization: outer-planar if and only if still
planar when adding a universal vertex. In consequence, can test outer-planarity
in linear time. Maximal outer-planar graphs. These have 2n-3 edges and
the dual is a tree after deleting the outer-face. Vertex ordering where
everyone has exactly two predecessors.
k-outer planar graphs. Onion peels. Outerplanarity is at most n/3, and for
some graphs at least n/6. A planar graph with a drawing of
small width or height has small outerplanarity. Proof.
2-terminal series-parallel graphs. The SP-tree.
Properties of 2-terminal SP-graphs: planar, at most 2n-3 edges, 3-colorable.
Proofsketch: use induction on height of SP-tree.
Not all outerplanar graphs are 2-terminal series-parallel graphs, e.g. K1,3.
Problem: not closed under taking subgraphs. SP-graphs.
Apollonian networks. Vertex ordering where
everyone has exactly three predecessors. Properties: 4-colorable, 3n-8
triangles. Hierarchy among all these graph classes. End of Part I of the
course.
Week 4
Monday, May 22, 2017: No lecture (Victoria day)
Wednesday, May 24, 2017 (Lecture 7): Interval graphs and chordal graphs Interval graphs. Definition.
Induced cycles of length >=4 are not interval graphs.
Interval graphs are closed under taking induced subgraphs.
Chordal graphs. Not all
chordal graphs are interval graphs. Example of a tree.
Interval graphs have naturally a vertex order (sorted by left endpoint).
Perfect elimination orders. Not all graphs that have a peo are
interval graphs (same example.) Every graph with a peo is chordal.
Algorithms. Greedy-coloring gives optimum. Proof. chi(G)=omega(G).
Greedy-algorithm for independent set. Doesn't give optimum, even with peo,
but gives optimum if we use reverse peo. Proof.
Friends of interval graphs. Other interesting classes of intersection
graphs: touching rectangles, intersecting disks, touching circles.
Other classes of H-free graphs, in particular perfect graphs.
Finding a PEO. Simple approach: repeatedly remove simplicial vertex.
Faster approach: lexBFS. Labels and how to update them. The algorithm.
Theorem: If G is chordal then this gives a PEO. Sketch of proof.
Week 5
Monday, May 29, 2017 (Lecture 8): Recognizing interval graphs. Tree decompositions
How to test whether a vertex order is a PEO. Main insight: Pred(vi) is
subset of vh cup Pred(vh) for last predecessor vh of vi. Second idea: batch
adjacency-testing together and do it via subset-testing in linear time.
In consequence, can recognize chordal graphs in linear time.
Interval graph recognition. G is an interval graph if and only if we
can arrange maximal cliques such that cliques containing a vertex are
consecutive. Proof. Can find maximal cliques in chordal graphs. Finding
suitable maximal-clique ordering can be done with PQ-trees. With that,
can recognize interval graphs in linear time.
This order of maximal cliques is useful in other ways. Definition of
strong path
decompositions. G is an interval graph if and only if it has a strong
path decomposition.
Now generalize to chordal graphs. Strong tree decomposition. Every graph
with a PEO has a strong tree decomposition. From PEO to decomposition:
add one bag at a time containing vn cup Pred(vn). From decomposition to
PEO: Enumerate vertices according to pre-order of the bags.
Study a subclass of chordal graphs. Recall, trees are chordal. Three
equivalent statement about trees. Now generalize. k-tree definition.
Three equivalent characterizations.
Wednesday, May 31, 2017 (Lecture 9): Partial k-trees and treewidth
Examples of k-trees. Trees are 1-trees. Apollonian networks are 3-trees,
but not vice versa. Maximal outerplanar graphs
are 2-trees, but not vice versa. Every 2-tree is a 2-terminal SP-graph,
but not vice versa. Partial k-trees.
k-trees and strong tree decompositions. Can have all bag-sizes k+1 and adjacent
bags differ by one vertex.
Weak tree decompositiion.
Every graph has one, but how small can the
bag-size be? Treewidth of a graph.
Every 2-terminal SP-graph has treewidth at most 2. Proof via SP-tree.
Lots of equivalent characterization, culminating in that partial k-trees
are the same as graphs of treewidth at most k. Proof, mostly via
existing results already.
Week 6
Monday, June 05, 2017 (Lecture 10): More on treewidth. Pathwidth
Why we care about partial k-trees. Main motivation for algorithm:
Many problems become polynomial (see later).
A few more properties of partial k-trees. If G has treewidth k
then it has a cutting k-set. For connected subgraphs, the bags
containing vertices must be connected. Proof.
Complexity of recognizing partial k-trees. NP-hard. Chain of reductions,
but no details. Some open problems around this.
Properties of partial k-trees. All cliques have size at most k+1.
Closed under taking subgraphs. Also closed under taking minors.
The axb-grid has treewidth min{a,b}. Upper bound by easy construction,
or use fill-in procedure.
Lower bound: show only simpler claim
that the kxk-grid has treewidth at least k-1. Idea: If we had
a tree decomposition of smaller width, then any arc of the tree can
be directed according to column that isn't covered. At a sink of this
orientation we can then find a contradiction.
Series-parallel graphs revisited. With previous results:
SP-graphs are exactly the partial 2-trees.
Other characterizations of SP-graphs (not all equivalences proved).
From one of them
one can deduce that SP-graphs can be recognized easily. Algorithm.
Main idea for correctness: we maintain a minor of input graph throughout.
This takes quadratic time. Can be made to run in linear time (no details).
Path decompositions and pathwidth. Equivalent:
subgraphs of interval graphs
with small chromatic number.
axb-grid has pathwidth min{a,b}.
pw(G) ≥ tw(G).
Any caterpillar has pathwidth 1.
Some trees have pathwidth >1, e.g. subdivided K1,3.
Wednesday, June 07, 2017 (Lecture 11): More on pathwidth. Branchwidth
Other characterization of pathwidth: searchwidth. Order vertices such
that for every cut few vertices on left have neighbours on right.
This is equivalent to the pathwidth. Proof via interval representation
of supergraph.
Pathwidth of trees. We had: caterpillar have pw 1. Generalize proof:
Create path decomposition of width k+1 for tree T with path P such that
all subtrees of T-P have pathwidth k. Other direction hold: Given path
decomposition of width k+1, can extract path (from leftmost to rightmost
bag) such that all subtrees have pathwidth at most k. In consequence,
graphs of pathwidth 1 are subgraphs of caterpillars.
Pathwidth is a lower bound to the height of planar graph drawings. Proof
with detour into visibility representations.
Pursuit evasion games. If graph has pathwith k, then node search number
is at most k. Proof. Other direction holds, but not shown here.
Branchwidth.
Recursive edge partitioning. Branch decomposition and separators on
arcs. Every SP-tree can be viewed as branch decomposition of width 2.
Branchwidth and treewidth are asymptotically the same.
treewidth + 1 <= 3/2 branchwidth. Proof, by
turning any branch decomposition into a tree decomposition simply
by filling bags until the connectivity condition is satisfied.
branchwidth(G) ≤ treewidth(G)+1. Proof by
modifying a tree decomposition until it is a branch decomposition.
Branchwidth in triangulated planar graphs. Goal: If triangulated G
has spanning tree of small height, then it has small branchwidth.
Step 1: Any spanning tree in planar G gives a spanning tree in dual
by taking the non-tree edges. (No proof, was on assignment.)
Step 2: Use spanning tree in
dual graph as host tree for branch decomposition, after some modifications.
If the height of the spanning tree is small, then separators are small.
Week 7
Monday, June 12, 2017: No lecture (keep free for assignment meetings)
Wednesday, June 14, 2017 (Lecture 12): Trees and dynamic programming
Independent set in trees. Easy to solve with bottom-up greedy.
But doesn't work for maximum-weight independent set.
Top-down recursive approach.
Need to consider whether root is included or not. Recursive
procedure if the root is in / is not in. This evaluates subtrees repeatedly;
to save run-time turn it into dynamic program.
The definition of alpha(v,Z). Recursive
formulas for alpha. The resulting bottom-up dynamic program.
Doing it again for matching, and then for dominating set. Key-ingredients:
If you don't know some parameter (such as which child used for matching),
try all possible ones and take the minimum/maximum as appropriate. If
the formula can't obviously be evaluation in O(deg(v)) time, try rewriting
it so that it can.
Independent set it series-parallel graphs via dynamic programming.
Go bottom-up in the SP-tree.
Formulas for the base-case, the parallel combination, and the
series combination.
Week 8
Monday, June 19, 2017 (Lecture 13): Dynamic programming in partial k-trees
Formal proof for one formula of parallel-combination.
Putting it all into one piece of code,
by going bottom-up in the SP-tree.
Now: dynamic programming in graphs of pathwidth 3. Step 1:
Find a nice path decomposition. Forget-nodes and introduce-nodes.
Step 2: Define subgraphs in which we'll search for solutions.
Step 3: Define function to be optimized. (Here again independent
set.) Step 4: Develop recursive formulas. The formula for a
leaf-node. The formula for a forget-node. The formula for
an introduce-node.
Pseudo-code. Note that this works for any constant pathwidth,
not just pathwidth 3, with very little change. Run-time.
Quick detour: How to test in O(k) time whether a vertex-pair
is adjacent. Run-time is O(f(k) n) for some function f(.).
In particular, linear for constant pathwidth.
Dynamic programming in partial k-trees.
Step 1: Find a nice tree decomposition. Definition of this.
How to modify the tree-decomposition to obtain a nice one.
Wednesday, June 21, 2017 (Lecture 14): Problems in partial k-trees
Recursive functions to be computed for a leaf, join node,
forget node and introduce node.
Pseudo-code sketch.
This gives an algorithm that's exponential in k, but polynomial in n.
The concept of fixed-parameter tractability (FPT). Hints at other results
about FPT; no details.
What other problems can be solved on partial k-trees. Intuitive idea:
whenever subproblems can be split/put together easily. A systematic
approach via a detour.
Monadic second-order logic (MSOL): express a graph property as a logic
formula. What is allowed/not allowed. Lots of examples. G has a triangle.
G is bipartite. G is not connected. G has min-degree 2. G has max-degree 2.
An extension: MSOL2, also allow subsets of edges and restricting
adjacency-queries to such. G has perfect matching can be expressed in
MSOL2 (but not in MSOL). G has a Hamiltonian cycle can be
expressed in MSOL2.
Courcelle's theorem: If a graph property can be expressed in MSOL2,
then testing it is FPT in the treewidth. (No proof.)
This covers only decision problems,
but it can be extended to cover optimization problems, even with weights (as
long as weights are polynomial). So from now on, avoid DP if possible and
express problem in MSOL2 instead, to solve it in partial k-trees.
Some problems are NP-hard, even on partial k-trees. Bandwidth is NP-hard
even on trees (no proof). Edge-disjoint paths
Planar grid-drawing
is NP-hard on graphs of pathwidth 4. Proof.
Week 9
Monday, June 26, 2017 (Lecture 15): k-outer-planar graphs
Recall k-outer planar graph. Onion peels.
Every planar graph can be made
k-outerplanar by deleting at most n/(k+1) vertices. Proof.
Any k-outerplanar graph is a partial 3k-tree. Proof, via a detour:
we can add edges to a k-outerplanar graph so that the result is planar
and has a spanning tree of height at most k. Then use previous results.
Using k-outer-planar graphs for approximation algorithms.
Removing every 2nd layer leaves outerplanar graph; can find maximum
independent set. Doing this for both ways of removing layers and
returning better independent set gives 1/2-approximation. Proof.
Do it again, removing every 3rd layer, gives 2/3-approximation.
Do it again, removing every kth layer, gives (k-1)/k-approximation.
Polynomial-time approximation schemes (PTAS). Baker's theorem: Have
a PTAS for independent set in planar graphs. This works, with modifications,
for many packing and covering problems, and even some other graph classes.
Wednesday, June 28, 2017 (Lecture 16): Separators
Had: Can split a partial k-tree with k+1 vertices. There are many
such set that split, which one to use? Theorem: Every tree can
be split at one vertex such that all parts have at most half the size.
Proof via algorithm to find the vertex.
Separators. Definition of alpha-separators. Weighted separators.
Separations of balance alpha.
Theorem: Every partial k-trees has a weighted 1/2-separator of size k+1.
Proof by applying the tree-separator-theorem to a (suitably weighted) tree
decomposition.
The planar separator theorem: Every planar graph has a weighted
1/2-separator of size O(sqrt{n}). Proof via making graph O(sqrt{n})-outerplanar
by removing O(sqrt{n}) many vertices.
Application I: Divide and conquer algorithms. Useful for
approximation algorithms, and sometimes even exact algorithms. No details.
Application II: Planar graphs have pathwidth O(sqrt{n}). Proof.
Application III: Can split graph into arbitrarily small pieces.
Week 10
Monday, July 03, 2017: No lecture (Canada Day observed)
Wednesday, July 05, 2017 (Lecture 17): Approximating Treewidth. Bidimensionality
Proof of ``can split planar graph into arbitrarily small pieces.''.
Main ingredient: The contributions of smaller components ``disappear''
in a geometric series.
Bidimensionality idea: Either graph has small treewidth, or can solve
the problem directly. Example: Longest path. Either DFS-tree has large
height (then have a path) or pathwidth is small (then solve via DP).
To do this for more problems, need a more powerful tool than DFS-tree.
Theorem: Small separators imply small treewidth. Proof. One can
derive a 4-approximation for treewidth from this (no details).
Grid minors in planar graphs. Theorem: For any k, every planar graph
either has a kxk-grid as a minor, or treewidth at most 5k-5. Proof
(with some cases for the induction step left out.) Quadratic run-time
and 5-approximation algorithm for treewidth.
Solving longest path in planar graphs. Either have a large grid-minor
(then the vertex cover is large), or have small treewidth (then we can
find the minimum vertex cover with dynamic programming.) Run-time
is exponential, but `only' in sqrt{ell}. Similar approach: How to
test whether a graph H is a minor of a planar graph G.
Week 11
Monday, July 10, 2017 (Lecture 18): WQO and Graph Minor Theorem
For any infinite sequence of paths, can find two such that the
first is a minor of the second. Definition of WQO. Paths are
WQO. Stars are WQO. Stronger version:
For any WQO graph class, we can find an infinite minor-chain
for any sequence of graphs.
Brooms are WQO, by splitting them
into star + path, extracting an infinite minor chain among
their paths, and then minors among the corresponding stars.
Message: If two graph classes are WQO, the graphs
obtained by combining them are also WQO (as long as we're careful
about what `combine' is allowed to mean.)
Building more WQO graph classes. (Only sketches of proofs.)
Caterpillars. Trees. Partial k-trees.
Theorem: Planar graphs are WQO. Proof much like bidimensionality:
either treewidths are small, or there is a large grid-minor.
More WQO graph classes (only proof ideas): Toroidal graphs. Graphs embedded
on surface of genus g. Graphs on Möbius strip. Graphs of non-orientable
genus. All graphs are WQO. This is known
as Graph Minor Theorem.
Implications. Define minor-minimal obstruction set for a minor-closed
graph class. G is in C if and only if it contains none of these
obstructions as minor. Proof. Graph Minor Theorem implies:
This obstruction-list is finite. Some examples. For most graph classes,
we sadly don't know the obstruction list or even how many there are.
Algorithmic implication. Recall: Can test `is H a minor of G' in time
polynomial in G. (We only proved this for planar graphs.)
In consequence, there exists an algorithm to recognize graphs in any
minor-closed graph class (but we don't know what it is).
What to remember after the final.
We saw planar graphs and partial k-trees. Partial k-trees:
nearly all problems can be solved, via DP or MSOL2 or
divide and conquer. Planar graphs: nearly all problems can be
approximated or have an FPT-algorithm, via Baker's approach or
the separator theorem or bidimensionality.
