Logic in Computer Science Prof. Dr. Martin Grohe

• Tue, 13.4.2010: Strategies for Coping with hard algorithmic problems; exact exponential algorithms and the idea of fixed-parameter tractability; comparison between SQL-Query Evaluation and LTL-Model Checking; different parameterizations of SAT; general notation; parameterizations and parameterized problems
• Tue, 20.4.2010: Fixed-Parameter Tractability; Hitting Set; Dominating Set; Independent Set
• Tue, 27.4.2010: fpt-algorithm for p-size-Hitting Set and its consequences; characterisations of FPT: eventually PTIME, PTIME after pre-computation on parameter; Kernelisations
• Tue, 4.5.2010: Kernelisation algorithms for:
  k-Vertex Cover (Buss kernel). See also [Nie], p.54.
  k-MaxSat. See also [Nie], p.58-60.
  k-d-Hitting Set. See also [FG], p.210-212.
  k-Leaf Spanning Tree.
  k-Vertex Cover (Nemhauser-Trotter). See also [FG], p.218-228 and [Nie], p.64-72.
  The (corrected) slides of the lecture are here.
• Tue, 11.5.2010:
  * Kernelisation continued: k-Vertex Cover, Crowns.
  The (corrected) slides of the first part are here.
  * Branching algorithms:
  Analyzing advanced branching algorithms. See also [Nie], p.88-93.
  k-Vertex Cover: simple, fast, faster. See also [Nie], p.98-101.
  Vertex Coloring.
  The (corrected) slides of the second part are here.
• Tue, 18.5.2010:
  * Branching algorithms continued: k-skew separator.
  The slides of this first part are here.
  * Iterative compression:
  k-Vertex Cover. See also [Nie], p.184-186.
  k-Feedback Vertex Set. See also [Nie], p.187-190.
  The slides of the second part are here, with some corrections and additions (one proof is added).
  
• Tue, 25.5.2010:
  * Iterative compression continued: directed and undirected k-Feedback Vertex Set.
  The corrected slides of the first part are here (*NEW*).
  * Tree decompositions:
  Definitions and basic properties. See also [FG], p. 261-266.
  Dynamic programming for Vertex Coloring. See also [FG], p.278-279.
  The slides of the second part are here.
  
• Tue, 1.6.2010:
  * Tree decompositions continued:
  A dynamic programming algorithm for Vertex Cover. See also [Nie], p. 160-163.
  The slides of the first part are here.
  Monadic Second Order Logic. See also [Nie], p. 169-172, and [FG], p. 280-289.
  Tree width based algorithms. See also [FG], p. 292-293.
  The slides of the second part are here.
  
• Tue, 8.6.2010:
  * Tree decompositions continued:
  A tree width based algorithm for k-Max Leaves Spanning Tree.
  (Slides, with some additions: here)
  Planar graphs:
  Definitions and properties, and FPT algorithms for k-Planar Independent Set and k-Planar Dominating Set. See also [FG], p. 301-309.
  Layer decompositions: subexponential FPT algorithms for Vertex Cover and Independent Set. See also [Nie], p. 155-160.
  Grid minors: An FPT algorithm for k-Path, a subexponential FPT algorithm for k-Planar Dominating Set. See also [FG], p. 321-322.
  (Slides: here)
• Tue, 15.6.2010:
  * Color coding:
  k-path. See also [Nie], p. 178-181, and [FG], p. 342-347.
  k-Binary Tree Subgraph Isomorphism.
  k-Subgraph Isomorphism. See also [FG], p. 342-347.
  The slides are here.
• Tue, 22.6.2010:
  Parameterized intractability; important intractable parameterized problem: IS, DS, WSAT, SHORT-HALT; parameterized intractability through NP-hardness; the class XP; fpt-reductions; examples of reductions; the class W[P] (see [FG] Chapters 2 and 3)
• Tue, 29.6.2010:
  Characterisations of W[P]; W[P]-completeness of WSAT(CIRC); W[1]; W[1]-completeness of 1-SHORT-HALT
• Tue, 6.7.2010:
  W[1]-completeness of Independent Set; weightede satsifiability problems; W-hierarchy
• Tue, 13.7.2010:
  Kernel Lower Bounds for kPath and VertexCover under the assumption that coNP is not contained in NP/poly. (full paper: here)

(See `Literature' on the main page for more information on the books [FG] and [Nie].)