Bidimensionality

Bidimensionality theory characterizes a broad range of graph problems (bidimensional) that admit efficient approximate, fixed-parameter or kernel solutions in a broad range of graphs. These graph classes include planar graphs, map graphs, bounded-genus graphs and graphs excluding any fixed minor. In particular, bidimensionality theory builds on the Graph Minor Theory of Robertson and Seymour by extending the mathematical results and building new algorithmic tools. The theory was introduced in the work of Demaine, Fomin, Hajiaghayi, and Thilikos.

Definition

A parameterized problem $\Pi$ is a subset of $\Gamma ^{*}\times \mathbb {N}$ for some finite alphabet $\Gamma$. An instance of a parameterized problem consists of (x,k), where k is called the parameter.

A parameterized problem $\Pi$ is minor-bidimensional if

1. For any pair of graphs $H,G$, such that $H$ is a minor of $G$ and integer $k$, $(G,k)\in \Pi$ yields that $(H,k)\in \Pi$. In other words, contracting or deleting an edge in a graph $G$ cannot increase the parameter; and
2. there is $\delta >0$ such that for every $(r\times r)$-grid $R$, $(R,k)\not \in \Pi$ for every $k\leq \delta r^{2}$. In other words, the value of the solution on $R$ should be at least $\delta r^{2}$.

Examples of minor-bidimensional problems are the parameterized versions of Vertex Cover, Independent Set, Feedback Vertex Set, Minimum Maximal Matching, and Longest Path.

Graph $\Gamma _{6}$

Let $\Gamma _{r}$ be the graph obtained from the $(r\times r)$-grid by triangulating internal faces such that all internal vertices become of degree 6, and then one corner of degree two joined by edges with all vertices of the external face. A parameterized problem $\Pi$ is contraction-bidimensional if

1. For any pair of graphs $H,G$, such that $H$ is a contraction of $G$ and integer $k$, $(G,k)\in \Pi$ yields that $(H,k)\in \Pi$. In other words, contracting an edge in a graph $G$ cannot increase the parameter; and
2. there is $\delta >0$ such that $(\Gamma _{r},k)\not \in \Pi$ for every $k\leq \delta r^{2}$.

Examples of contraction-bidimensional problems are Dominating Set, Connected Dominating Set, Max-Leaf Spanning Tree, and Edge Dominating Set|.

Excluding Grid Theorems

All algorithmic applications of bidimensionality are based on the following combinatorial property: either the treewidth of a graph is small, or the graph contains a large grid as a minor or contraction. More precisely,

1. There is a function f such that every graph G excluding a fixed h-vertex graph as a minor and of treewidth at least f(h)r contains (r x r)-grid as a minor.
2. There is a function g such that every graph G excluding a fixed h-vertex apex graph as a minor and of treewidth at least g(h) r can be edge-contracted to $\Gamma _{r}$.

Subexponential parameterized algorithms

Let $\Pi$ be a minor-bidimensional problem such that for any graph G excluding some fixed graph as a minor and of treewidth at most t, deciding whether $(G,k)\in \Pi$ can be done in time $2^{O(t)}\cdot |G|^{O(1)}$. Then for every graph G excluding some fixed graph as a minor, deciding whether $(G,k)\in \Pi$ can be done in time $2^{O({\sqrt {k}})}\cdot |G|^{O(1)}$. Similarly, for contraction-bidimensional problems, for graph G excluding some fixed apex graph as a minor, inclusion $(G,k)\in \Pi$ can be decided in time $2^{O({\sqrt {k}})}\cdot |G|^{O(1)}$.

Thus many bidimensional problems like Vertex Cover, Dominating Set, k-Path, are solvable in time $2^{O({\sqrt {k}})}\cdot |G|^{O(1)}$ on graphs excluding some fixed graph as a minor.

Polynomial Time Approximation Schemes (PTAS)

Bidimensionality theory has been used to obtain Polynomial Time Approximation Schemes (PTAS) for many bidimensional problems. If a minor (contraction) bidimensional problem has several additional properties then the problem poses Efficient Polynomial Time Approximation Scheme (EPTAS) on (apex) minor-free graphs.

In particular, by making use of Bidimensionality, it was shown that Feedback Vertex Set, Vertex Cover, Connected Vertex Cover, Cycle Packing, Diamond Hitting Set, Maximum Induced Forest, Maximum Induced Bipartite Subgraph and Maximum Induced Planar Subgraph admit an EPTAS on H-minor-free graphs. Edge Dominating Set, Dominating Set, r-Dominating Set, Connected Dominating Set, r-Scattered Set, Minimum Maximal Matching, Independent Set, Maximum Full-Degree Spanning Tree, Max Induced at most d-Degree Subgraph, Max Internal Spanning Tree, Induced Matching, Triangle Packing, Partial r-Dominating Set and Partial Vertex Cover admit an EPTAS on apex-minor-free graphs.

Kernelization

A parameterized problem with a parameter k is said to admit a linear kernel if there is a polynomial time algorithm (the degree of polynomial is independent of k), called a kernelization algorithm, that reduces the input instance down to an instance with size bounded by O(k) - while preserving the answer.

Every minor-bidimensional problem $\Pi$ with additional properties, namely, with the separation property and with finite integer index, has a linear kernel on graphs excluding some fixed graph as a minor. Similarly, every contraction- bidimensional problem $\Pi$ with the separation property and with finite integer index has a linear kernel on graphs excluding some fixed apex graph as a minor.

References

• Demaine, Erik D.; Fomin, Fedor V.; Hajiaghayi, MohammadTaghi; Thilikos, Dimitrios M. (2005), "Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs", J. ACM, 52 (6): 866–893, doi:10.1145/1101821.1101823.
• Demaine, Erik D.; Fomin, Fedor V.; Hajiaghayi, MohammadTaghi; Thilikos, Dimitrios M. (2004), "Bidimensional parameters and local treewidth", SIAM J. Discrete Math., 18 (3): 501–511, doi:10.1137/S0895480103433410.
• Demaine, Erik D.; Hajiaghayi, MohammadTaghi (2005), "Bidimensionality: new connections between FPT algorithms and PTASs", 16th ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 590–601.
• Demaine, Erik D.; Hajiaghayi, MohammadTaghi (2008), "Linearity of grid minors in treewidth with applications through bidimensionality", Combinatorica, 28 (1): 19–36, doi:10.1007/s00493-008-2140-4.
• Demaine, Erik D.; Hajiaghayi, MohammadTaghi (2008), "The bidimensionality theory and its algorithmic applications", The Computer Journal, 51 (3): 332–337, doi:10.1093/comjnl/bxm033.
• Fomin, Fedor V.; Golovach, Petr A.; Thilikos, Dimitrios M. (2009), "Contraction Bidimensionality: The Accurate Picture", 17th Annual European Symposium on Algorithms (ESA 2009), Lecture Notes in Computer Science, vol. 5757, pp. 706–717, doi:10.1007/978-3-642-04128-0_63.
• Fomin, Fedor V.; Lokshtanov, Daniel; Raman, Venkatesh; Saurabh, Saket (2010), arXiv.org, arXiv:1005.5449v1 {{citation}}: |contribution= ignored (help); Missing or empty |title= (help).
• Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Thilikos, Dimitrios M. (2010), "Bidimensionality and Kernels", 21th ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pp. 503–510.