Trees · Theory Problems

Lesson 4

Nikolai Chukhin · Alexander S. Kulikov

Optional Problems.

Treewidth.

  1. (10 points) Prove that a graph has treewidth at most \(1\) if and only if it is a forest.
  2. (15 points) A tree decomposition is called nice if it is rooted, its root bag is empty, all its leaf bags are empty, and every internal node \(t\) is one of the following types:
    • introduce node: it has one child \(s\), and \(B_{t}=B_{s}\cup\{v\}\) for some vertex \(v\);

    • forget node: it has one child \(s\), and \(B_{t}=B_{s}\setminus\{v\}\) for some vertex \(v\);

    • join node: it has two children \(s_{1},s_{2}\), and \(B_{t}=B_{s_1}=B_{s_2}\).

    Prove that every tree decomposition of width \(k\) with \(m\) bags can be transformed in polynomial time into a nice tree decomposition of the same graph, of width \(k\), with \(O((k+1)m)\) bags.
  3. (20 points) A set \(D\subseteq V(G)\) is called a dominating set if for every vertex \(v\in V(G)\), either \(v\in D\) or \(v\) has a neighbor in \(D\). Given a graph \(G\) and a tree decomposition of \(G\) of width \(k\) with \(O(n)\) bags, give an algorithm that finds a minimum-size dominating set in time \(2^{O(k)}\operatorname{poly}(n)\).
  4. (20 points) Given a graph \(G\) and a tree decomposition of \(G\), let \(H\) be a clique subgraph of \(G\). Prove that \(H\) is contained in some bag.
  5. (20 points) Prove that if there is a tree decomposition of a graph \(G\) with width \(k\), then there is another decomposition of width \(k\) using \(O(n)\) bags.
    Hint:
    Start with any tree decomposition of width \(k\). If two adjacent bags are equal, or one of them is contained in the other, contract the edge between them. This does not break the decomposition axioms and does not increase the width. Then root the remaining decomposition tree and assign to each non-root bag a vertex that appears there for the first time.
  6. (25 points)
    • (15 points) Prove that if \(\operatorname{tw}(G)\le k\), then \(G\) has a set \(S\subseteq V(G)\) with \(|S|\le k+1\) such that every connected component of \(G-S\) has at most \(|V(G)|/2\) vertices.

    • (10 points) Given a graph \(G\) and a number \(k\). It is promised that \(\operatorname{tw}(G)\le k\). Construct a tree decomposition of width \(O(k \log n)\) for \(G\) in time \(n^{O(k)}\). In particular, the running time is polynomial for every fixed \(k\).

    Hint:
    You might need to recall what a centroid is.