Advanced Algorithms Exam

Satisfying conditions of a tree decomposition of a graph

$G=\left(V,E\right)$ ?

1. Vertex coverage: every vertex of G appears at least in one bag

2. Edge coverage: for every edges (u,v), at least one bag contains both u and v

3. Connectedness: for each vertex v, all bags containing v form a connected subtree of T

Mathematical definition of treewidth tw(G)?

$$tw\left(G\right)=\min_{T}\left(\max_{i\in V\left(T\right)}\left|X_{i}\right|-1\right)$$

Weighted centroid lemma?

Let T be a finite tree with nonnegative vertex weights total W. A weighted centroid is a vertex t such that every component of T – t has a weight at most half of W.

Treewidth and balanced separators lemma?

If tw(G) <= k, every subgraph H of G has a separator of size at most k + 1 leaving components of size at most |V(H)| / 2.

Dvorak–Norin theorem?

Suppose every subgraph H of G has a separator of size at most the same bound s, leaving components of size at most 2 |V(H)| / 3. Then tw(G) = O(s).

Korhonen theorem?

Given a graph G on n vertices and an integer k, there is a

$2^{o\left(k\right)}n$ time algorithm that either returns a tree decomposition of width at most 2k + 1 or correctly reports that tw(G) > k.

Given a tree decomposition of width w, what is the DP running time to solve e.g. MIS, MVC, MDS, max cut, odd cycle transversal, …?

$$2^{O\left(w\right)}\cdot n^{O\left(1\right)}$$

The grid minor theorem?

Coping with NP completeness with algorithms?

• Sacrifice generality (trees instead of graphs)

• Sacrifice optimality (find solution in range$\left\lbrack\left(\frac{1}{c}\right)\cdot OPT,c\cdot OPT\right\rbrack$

• Sacrifice efficiency (find algorithm faster than brute-force)

Sacrifice generality in Independent Set problem approach for trees?

$A_1\left\lbrack v\right\rbrack=$ size of a largest IS of Tv containing v

$A_2\left\lbrack v\right\rbrack=$ size of a largest IS of Tv not containing v

Recursion:

$A_1\left\lbrack v\right\rbrack=1,A_2\left\lbrack v\right\rbrack=0$ (leaf)

$$A_1\left\lbrack v\right\rbrack=1+\sum_{u}A_2\left\lbrack v\right\rbrack$$

$$A_2\left\lbrack v\right\rbrack=\sum_{u}^{a}\max\left(A_1\left\lbrack u\right\rbrack,A_2\left\lbrack u\right\rbrack\right)$$

Sacrificing optimality with the set cover problem (smallest-cardinally sub collection of S whose union is B)?

Approximation ratio of non-optimal algorithm?

• For instance I, let us denote OPT(I) the value of the optimum solution.

• Ratio:

$$\alpha_{A}=\max_{I}\frac{A\left(I\right)}{OPT\left(I\right)}$$

The approximation factor of a greedy algorithm is …

… at most ln(n).

Sparsity: Euler’s formula?

Let G be a connected plane graph. Then we have

$$v-e+f=2$$

(f = # of faces of G)

Corollary about number of faces in planar embedding of G?

For a connected planar graph G, every planar embedding of G has the same number of faces.

For a connected, simple (no self-cycles, no double edges) with at least three vertices how many edges?

$$e\le3v-6$$

Let G be a connected, simple planar graph with at least g vertices, where g >= 3. If G has no cycle of length < g, e is what?

$$e\le\frac{g}{g-2}\left(v-2\right)$$

Subdivision of a graph G how do we obtain it?

Insert vertices into edges zero or more times.

Kuratowski theorem?

What is a minor of a graph G?

Take its subgraph and repeatedly contract and edge into a vertex.

Wagner theorem?

Fary’s theorem?

Any simple planar graph can be drawn without crossings so that its edges are line segments.

Known graph coloring results?

• 2-coloring can be solved in polynomial time.

• 3-coloring is NP-complete for planar graphs

• 3-color can be solved in $2^{O\left(\sqrt{\left(n\right)}\right)}$ for planar graphs

• 4-coloring can be solved in polynomial time for planar graphs

• Every planar graph has a 6-coloring and a 5-coloring

Proving the running time of $2^{O\left(\sqrt{\left(n\right)}\right)}$ for 3-coloring planar graphs?

1. Every planar graph has balanced separator S of size sqrt(n)

2. Split G with S to components C of size 2n/3

3. Color S with 2^(O(sqrt(n)) time (brute-force)

4. Split & color again

How fast can we compute planar separator?

In linear time.

No algorithm for the 3-coloring problem on general graphs runs in polynomial time unless

P=NP

No algorithm for the 3-coloring problem on general graphs runs in

$2^{o\left(n\right)}$ time unless

ETH fails.

No algorithm for the 3-coloring problem on planar graphs runs in

$2^{o\left(\sqrt{n}\right)}$ time unless

ETH fails.

Exponential-Time Hypothesis (ETH)?

• No subexponential-time algorithm exits for the 3-SAT problem.

• There is a value c>0 such that 3-SAT cannot be solved in O(2^(cn)) time.

Centroids in trees?

Every n-vertex tree has a vertex c such that each component T-c has at most n/2 vertices.

Grids balanced separator size?

An r x r grid with n = r², has minimum balanced separator size O(r)=O(sqrt(n)).

Tree decomposition (with bags) conditions?

1. Vertex coverage (every v belongs to at least one bag)

2. Edge coverage (for every edge uv, some bag contains both u and v)

3. Connectedness (for every v, the nodes t with v in Bt, induce a connected subtree of T)

Width of a tree decomposition?

Size of its largest bag minus one.

Treewidth of a tree decomposition?

tw(G) is the minimum width over all valid tree decompositions of G

Every nonempty n-vertex graph satisfies what in regards to tw(G)?

$$0\le tw\left(G\right)\le n-1$$

Every tree containing an edge has what treewidth?

1.

Clique-bag lemma?

In every tree decomposition of G, each clique Q is contained in a single bag.

How does treewidth relate to the largest clique size?

$w\left(G\right)$ = largest clique size

$$tw\left(G\right)\ge\omega\left(G\right)-1$$

The Helly property for subtrees?

If a finite collection of nonempty subtrees of a tree intersect pairwise, then all its members share a vertex.

Sparsification lemma?

There is a $2^{\epsilon\cdot n}$ time algorithm that takes an instance of 3SAT with n variables and produces max$2^{\epsilon\cdot n}$ instances of 3SAT s.t.

• at least one satistifiable if the original 3SAT is satisfiable

• each of the new instances have n variables and $C_{\epsilon}\cdot n$ clauses, where C depends on epsilon → much sparser!

How fast can we compute a balanced separator S for a planar graph with diameter of $O\left(\sqrt{\left(n\right)}\right)$

In linear time.

Steps of proving planar separator theorem?

1. Triangulation

2. Find a small balanced separator for a planar graph with small diameter

3. Reduce the original problem to the problem in Step 2

How fast can we compute a balanced separator S for a maximal planar graph?

In linear time.

Treewidth of forests?

$$tw\left(G\right)\le1$$

The Helly property for subtrees.

If you have a finite collection of nonempty subtrees of a larger tree, and every single pair of subtrees overlaps, then there is at least one universal vertex shared by all of the subtrees simultaneously.

Treewidth under minor operations?

If H is a minor of G, then tw(H) <= tw(G).

Weighted centroids in trees?

Let T be a finite tree with nonnegative vertex weights totaling W. A weighted centroid is a vertex t such that every component of T – t has weight at most half of W.

Dvorak-Norin theorem?

Suppose every subgraph H of G has a separator of size at most the same bound s, leaving components of size at most 2|V(H)|/3. Then tw(G) = O(s).

Treewidth and balanced separators?

If tw(G) <= k, every subgraph H of G has a separator of size at most k+1 leaving components of size at most |V(H)|/2.

Korhonen theorem?

Given a graph G on n vertices and an integer k, there is a $2^{o\left(k\right)}n$-time algorithm that either returns a tree decomposition of width at most 2k+1 or correctly reports that tw(G) > k.

The grid minor theorem?

Given a tree decomposition of width k with N bags, we can decide 3-colorability in

$2^{O\left(k\right)}\left(n+N\right)^{O\left(1\right)}$ time.