problems in P
for n size of the input, there is an algorithm that solves the problem in running time O(n^c), so in polynomial time
problems in NP
problems that can be verified in polynomial time
Boolean satisfiability problem (SAT)
Asks whether there exists an interpretation that satisfies a given Boolean formula. SAT is in NP, because it can be verified quickly. It’s also NP hard (some theorem), thus it is NP-complete.
It can be answered in O(2^n)
Reduction: If we reduce a problem B to another problem A …
… A is at least as difficult as B
Linked List
adjacency matrix
List of edges
Upper bound for |E|
depth first search algorithm
breadth first search algorithm
O notation
halting problem
decision problem
example
optimisation problem
language
when does a Turing Machine decide a language?
The class P (using languages)
The class NP (using languages)
Instance
CNF
3-SAT
Reduction 3-SAT -> independent set
block (2 definitions)
Menger’s Theorem
Reduction 3-SAT -> 3-colouring
block graph
FPT: A parameterized problem is called fixed parameter tractable if …
definition tree-decomposition
Lemma: transfer of separation properties from tree-decomposition to G
width
tree-width
small tree-decomposition
property that follows
How to generate a tree-decomposition of small tree-width
reduction: SAT -> 3-SAT
tree-decomposition Äquivalenz
Vertex Cover FPT?
Yes! Dedenping on k (size of vertex cover)
Minors and planarity (2 theorems)
1) Any minor of a planar graph is planar.
2) G is planar. <=> G is the minor of a grid.
Beziehung: Kanten und Ecken Dreiecksfreie Graphen
Minimalgrad >= 5, was impliziert das für Kanten und Ecken?
m <= 2n - 4
5n <= 2m
connection: vertex cover and tree-width
VC(G) >= tw(G)
(VC is an upper bound for tw)
definition nice tree-decomposition
circumference
circumference and tree-width
the maximum length of a cycle of G
circ(G) - 1 >= tw(G)
let A, B, C be parameterized problems …
… if there are parameterized reductions from A to B and from B to C, then there is a parameterized reduction from A to C
1) set cover
2) parameterized reduction dom set -> set cover
grid tiling hardness
reduction
grid tiling is W[1]-hard
reduction from clique:
balanced V-separator hardness
balanced V-separator is W[1]-hard
What holds for planar graphs of bounded diameter?
planar graph G of diameter d: tw(G) <= 3d
planar dominating set: running time, algorithm
running time is linear (in n, not in k):
minor and minor model
tree-width for subgraphs and minors
Helly property
proof
touching subsets
bramble
cover
order of a bramble
Bramble Duality Theorem (two statements)
tree-width of a (kxk)-grid (with proof)
tw(kxk-grid) = k
Euler’s Formula
inequality for planar graphs with |V(G)| >= 3
algorithm ind set of size k on planar graphs (parameterized by the size of ind set), runtime
it’s linear (in n):
complexity class tree-width (without parameter)
Bodlaender’s Algorithm
complexity
balanced W-separator
statement about connection of tree-width and W-separator
Proof
definition separator width
Theorem about tree-width and separator width
Idea how to proof the other inequality
tree-width, existence of a vertex of certain degree
how to find it
What is W[1]?
Relation to …
Name a problem in it
W[1] is the space of problems which are not FPT (intractable)
It is related to the circuit weft
clique (parameterized by size k) is W[1]-complete
parameterized reduction A -> B
parameterized reduction from A to B and … is FPT, what is then true?
Examples for W[2]-hard problems
Dom set and set cover
reduction clique -> clique on regular graphs
reduction clique on regular graphs -> MultiColClique
In which complexity class is ListColouring, paramerterized by what?
Reduction
minor containment complexity
definition G-admissible
H-bridge B of G
attachments of B
definition directed spanning tree
theorem about tree-width of planar graphs
running time
excluded grid theorem
bidimensional problems
parameterized minor-bidimensional problems
how to solve them
planar excluded grid theorem
corollary
the contraction grid
how to build it
planar excluded grid theorem for edge contractions
contraction bidimensional problem
how to solve it
neighbourhood, sphere, slice
definition r-neighbourhood cover
Lemma: r-neighbourhood cover on planar graphs
NP-optimization problem
epsilon-close solution
polynomial time approximation scheme
min vertex cover on graphs of bounded tree-width, running time
polytime algorithm for planar H-subgraph isomorphism, what assumption has to be made?
Baker’s technique: k := diam(H), solve problems on all layers, which have bounded tree-width
assumption: planar H-subgraph isomorphism is solvable in linear time on graphs of bounded tree-width
Last changed20 days ago
