<p>Here's how to do (2) for Dominating Set. Since Dominating Set is contraction-bidimensional, we need to show the solution value is $\Omega(r^2)$ on a partially triangulated $r*r$ grid. So consider a partially triangulated $r*r$ grid. There might be vertices on the outer cycle of the grid of large degree (for example, one vertex might be adjacent to all other vertices on the outer cycle). Therefore, we are going to ignore the outermost 2 cycles of the grid, so we look at the $(r-4) * (r-4)$ partially triangulated subgrid "in the center", which has $\Omega(r^2)$ vertices, and we consider which vertices may be used to dominate this subgrid. Due to planarity, no vertex in this inner grid can be adjacent to a vertex on the outer cycle. All vertices which do not lie on the outer cycle have degree at most 8, as the partial triangulation has to keep the graph planar and can only make edges to the 8 vertices which are above, below, left, right, and diagonally adjacent to a vertex. So the $\Theta(r^2)$ vertices of the inner $(r-4)*(r-4)$ grid must be dominated by vertices which have degree at most 8 each. So when it comes to this inner grid, at best each vertex can dominate 8 other vertices and itself, for a total of 9. So you need at least $(r-4)^2 / 9$ vertices to dominate the inner grid, so a dominating set on the partially triangulated grid has size $\Theta(r^2)$.</p>

CC BY-SA 3.0
2012-01-19T15:42:51.530Z
We consider the inner grid, and due to planarity the degree is at most 8 (and thus each vertex dominates at most 9 vertices), implying we need (r-4)^2/9 vertices at least. Clear, thanks a lot! I wonder if proving (2) is problems specific as Suresh suggests. There are problems listed as minor- or contraction-bidimensional. Are they all proved to be so indivisually?
user8003
CC BY-SA 3.0
2012-01-18T10:02:51.807Z
2012-01-18T10:02:51.807Z
Bart Jansen
<p>I'm looking for a formal proof that a problem (say, dominating set) is bidimensional/contraction-bidimensional. Either a reference or a proof sketch is fine.</p>

<p>There are two elements in the definition of (contraction-)bidimensionality (1) taking minor/contraction does not increase the parameter (2) on r*r-grid/triangulated grid, the solution value is at least theta(r*r). 
In particular, I'd like to know how the proof goes regarding (2). </p>

CC BY-SA 3.0
2012-01-17T17:52:25.600Z
I'd be surprised if there's a generic proof technique for *any* graph property more specific than what you outline.
Suresh Venkat
<cc.complexity-theory>
how to prove bidimensionality
user8003
# how to prove bidimensionality

(Asked by: username_0 on 2012-01-17)

I'm looking for a formal proof that a problem (say, dominating set) is bidimensional/contraction-bidimensional. Either a reference or a proof sketch is fine.

There are two elements in the definition of (contraction-)bidimensionality (1) taking minor/contraction does not increase the parameter (2) on r\*r-grid/triangulated grid, the solution value is at least theta(r\*r).
In particular, I'd like to know how the proof goes regarding (2).

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: I'd be surprised if there's a generic proof technique for *any* graph property more specific than what you outline.  

---

## 1 answers

### Answer by username_2 on 2012-01-18. Score: 7 | Accepted answer

Here's how to do (2) for Dominating Set. Since Dominating Set is contraction-bidimensional, we need to show the solution value is $\Omega(r^2)$ on a partially triangulated $r\*r$ grid. So consider a partially triangulated $r\*r$ grid. There might be vertices on the outer cycle of the grid of large degree (for example, one vertex might be adjacent to all other vertices on the outer cycle). Therefore, we are going to ignore the outermost 2 cycles of the grid, so we look at the $(r-4) \* (r-4)$ partially triangulated subgrid "in the center", which has $\Omega(r^2)$ vertices, and we consider which vertices may be used to dominate this subgrid. Due to planarity, no vertex in this inner grid can be adjacent to a vertex on the outer cycle. All vertices which do not lie on the outer cycle have degree at most 8, as the partial triangulation has to keep the graph planar and can only make edges to the 8 vertices which are above, below, left, right, and diagonally adjacent to a vertex. So the $\Theta(r^2)$ vertices of the inner $(r-4)\*(r-4)$ grid must be dominated by vertices which have degree at most 8 each. So when it comes to this inner grid, at best each vertex can dominate 8 other vertices and itself, for a total of 9. So you need at least $(r-4)^2 / 9$ vertices to dominate the inner grid, so a dominating set on the partially triangulated grid has size $\Theta(r^2)$.

> **Comments:**
> **username_0**: We consider the inner grid, and due to planarity the degree is at most 8 (and thus each vertex dominates at most 9 vertices), implying we need (r-4)^2/9 vertices at least. Clear, thanks a lot! I wonder if proving (2) is problems specific as Suresh suggests. There are problems listed as minor- or contraction-bidimensional. Are they all proved to be so indivisually?  

---

