Treewidth

Question 1

What is Elimination Ordering

Answer 1

Elimination ordering is an ordering of eliminating vertices of G. Each elimination ordering is different in terms of treewidth. One elimination ordering may have different width than another elimination ordering.

Question 2

What is k-Tree?

Answer 2

k-Trees are recursively defined as follows:
-A clique of size k+1 is a k-tree.
- Given a k-tree T, one can construct a new
k-tree by creating a new vertex and making
it adjacent to a size k k clique of T.

Question 3

Treewidth definition (by elimination ordering)

Answer 3

Correction: The treewidth of a graph G is the minimum width out of all elimination orderings of G .

Question 4

Treewidth definition (by k-Tree)

Answer 4

The treewidth of a graph G is the minimum k

such that G is a partial k-tree.

Question 5

Tree Decomposition definition

Answer 5

Let G = (V, E) be a graph. A tree decomposition
of G is a pair (T, χ) consisting of a tree T = (V′ , E′ )
and a mapping χ : V′ → 2^V such that:

1. union of χ(v) for each v ∈ V is equal to V
2. For each vw ∈ E, there is a v′ ∈ V’ with v, w ∈ χ(v′  χ(v').
3. Ked zoberiem v \in V(G) a zoberiem vsetky t \in V(T) take, ze v patri t, tak nam vznikne connected subtree. To plati pre vsetky v \in V(G).

Question 6

Courcelle’s theorem

Answer 6

MSO2 MODEL CHECKING is FPT parameterized by the treewidth of G and the length ∥φ∥ of φ.

Question 7

INDEPENDENT SET parametrization

Answer 7

INDEPENDENT SET is FPT parameterized by the treewidth of G and k.