TA SESSION PLAN
The listings below provide a synopsis of the material covered by the TAs in their weekly sessions throughout the course. These listings are not binding and can be changed by the staff at its discretion and without any special notice to the student body. Until a session is actually given, its plan is tentative. There is no binding obligation on the part of the staff that the session would fit its pre-published plan. We also specify the source of the topics covered throughout these sessions If your TA did not cover some of the material in the listing published for a given session, then it is your obligation to study all parts which your TA did not cover on your own according to the source associated with the topic. ​All material produced by the course TAs did not undergo the scrutiny reserved for formal publications. Whenever a source is listed for a topic it is the version seen in that source that dominates in case of conflicts.
Session 1:
-
Self-reduction for 3COL | NPC exe. notes
-
2-CNF-SAT is in P | Course Booklet
​
Session 2:
-
NAE-3CNF-SAT is NPC
-
3-CNF-SAT ≤_p NAE-4-CNF-SAT
-
NAE-4-CNF-SAT ≤_p NAE-4-CNF-SAT
-
Both reductions are in the NPC exe. notes
-
-
3-CNF-SAT ≤_p CLIQUE | CLRS, Thm 34.11
-
Independent Set ≤_p Vertex-Cover +
-
Gallai's theorem | Course booklet
-
Session 3:
-
CLIQUE ≤_p INDEPENDENT SET
-
CLIQUE ≤_p VERTEX COVER | CLRS Thm 34.12
-
SUBSET-SUM ≤_p PARTITION | NPC exes
-
SUBSET-SUM ≤_p KNAPSACK | NPC exes
​
Session 4:
-
Matchings in degree-regular bipartite graphs | Course booklet Sec. 1.2.1
-
Perfect matchings in dense bipartite graphs | Course booklet Theorem 1.25
-
Matchings covering a prescribed set of vertices | Course booklet Sec. 1.4.1
-
Finding min. vx. covers in bipartite graphs | Course booklet Prop. 1.30 + Algo 1.4.2
Session 5:
-
Extensions of Hall's thm | booklet Sec. 1.5
-
Perfect matchings in dense bipartite graphs via Tutte's theorem | booklet pg. 30
-
Tutte => Hall| booklet Sec. 1.8.1
-
Petersen's thm | booklet Sec 1.8.2
Reading Assignement:
Read about the structure of saturated non-factorisable graphs to complete the proof of Tutte's theorem | booklet Thm 1.56
Session 6:
​
-
Edge connectivity | Course booklet Sec. 2.3
-
Generalisations of Dirac's thm | Course booklet Sec. 3.1.1
-
Hamiltonian-connected graphs | Course booklet Sec. 3.3
-
Hamilton paths in tournaments | Course booklet Sec. 3.5
​
​
Session 7:
-
Colouring 3-colourable graphs | Course booklet Proposition 5.23
-
Vizing's Theorem | Course booklet Them 4.5
-
Vizing via Brooks: a special case | Exe 6 in col. notes
-
Colouring interval graphs | Exe 1 in col. notes
-
Colouring graphs whose odd cycles intersect | Exe 2 in col. notes
Session 8:
-
Flow in a network | [1] Sec. 2.2
-
Fitting a line | [1] Sec. 2.4
-
Separating points | [1] Sec. 2.5
-
Max weight matchings | [1] Sec. 3.2
-
Max. independent set | [1] Sec 3.4
​
[1] = Gärtner-Matoušk Understanding LP book
​
Session 9:
-
Steiner trees | Sec. 7.4 booklet
-
Steiner trees Exes. 10,11,12,13 | Apx. notes
-
Minimum dominating sets | Sec. 7.7 booklet
Session 10:
Algorithms for MAX-SAT | Sec. 7.9 booklet
​
Randomised and all LP based versions.