TY - GEN
T1 - Bidimensionality and kernels
AU - Fomin, Fedor V.
AU - Lokshtanov, Daniel
AU - Saurabh, Saket
AU - Thilikos, Dimitrios M.
PY - 2010
Y1 - 2010
N2 - Bidimensionality theory appears to be a powerful framework in the development of meta-algorithmic techniques. It was introduced by Demaine et al. [J. ACM 2005] as a tool to obtain sub-exponential time parameterized algorithms for bidimensional problems on H-minor free graphs. Demaine and Hajiaghayi [SODA 2005] extended the theory to obtain polynomial time approximation schemes (PTASs) for bidimensional problems. In this paper, we establish a third meta-algorithmic direction for bidimensionality theory by relating it to the existence of linear kernels for parameterized problems. In parameterized complexity, each problem instance comes with a parameter k and the parameterized problem is said to admit a linear kernel if there is a polynomial time algorithm, called a kernelization algorithm, that reduces the input instance to an equivalent instance (called kernel) with size linearly bounded by k. We show that "essentially" all bidimensional problems not only have sub-exponential time algorithms and PTASs but they also have linear kernels, affirmatively answering an open question from [J. ACM 2005] where the existence of linear kernels was conjectured for the first time. In particular, we prove that every minor (respectively contraction) bidimensional problem that satisfies the separation property and is of finite integer index, admits a linear kernel for classes of graphs that exclude a fixed graph (respectively an apex graph H) H as a minor. Recently, Bodlaender et al. [FOCS 2009] laid the foundation for obtaining meta-algorithmic results for kernelization and showed that various problems satisfying some logical and compactness properties have polynomial, even linear kernels on graphs of bounded genus. With the use of bidimensionality we are able to extend these results to minor-free and apex-minor-free graphs. Our results imply that a multitude of bidimensional problems, which include DOMINATING SET, FEEDBACK VERTEX SET, EDGE DOMINATING SET, VERTEX COVER, r-DOMINATING SET, CONNECTED DOMINATING SET, CYCLE PACKING, CONNECTED VERTEX COVER, ALMOST CONSTANT TREEWIDTH, and various other vertex covering and packing problems, admit linear kernels on the corresponding graph classes. For most of these problems no polynomial kernels on H-minor-free graphs were known prior to our work.
AB - Bidimensionality theory appears to be a powerful framework in the development of meta-algorithmic techniques. It was introduced by Demaine et al. [J. ACM 2005] as a tool to obtain sub-exponential time parameterized algorithms for bidimensional problems on H-minor free graphs. Demaine and Hajiaghayi [SODA 2005] extended the theory to obtain polynomial time approximation schemes (PTASs) for bidimensional problems. In this paper, we establish a third meta-algorithmic direction for bidimensionality theory by relating it to the existence of linear kernels for parameterized problems. In parameterized complexity, each problem instance comes with a parameter k and the parameterized problem is said to admit a linear kernel if there is a polynomial time algorithm, called a kernelization algorithm, that reduces the input instance to an equivalent instance (called kernel) with size linearly bounded by k. We show that "essentially" all bidimensional problems not only have sub-exponential time algorithms and PTASs but they also have linear kernels, affirmatively answering an open question from [J. ACM 2005] where the existence of linear kernels was conjectured for the first time. In particular, we prove that every minor (respectively contraction) bidimensional problem that satisfies the separation property and is of finite integer index, admits a linear kernel for classes of graphs that exclude a fixed graph (respectively an apex graph H) H as a minor. Recently, Bodlaender et al. [FOCS 2009] laid the foundation for obtaining meta-algorithmic results for kernelization and showed that various problems satisfying some logical and compactness properties have polynomial, even linear kernels on graphs of bounded genus. With the use of bidimensionality we are able to extend these results to minor-free and apex-minor-free graphs. Our results imply that a multitude of bidimensional problems, which include DOMINATING SET, FEEDBACK VERTEX SET, EDGE DOMINATING SET, VERTEX COVER, r-DOMINATING SET, CONNECTED DOMINATING SET, CYCLE PACKING, CONNECTED VERTEX COVER, ALMOST CONSTANT TREEWIDTH, and various other vertex covering and packing problems, admit linear kernels on the corresponding graph classes. For most of these problems no polynomial kernels on H-minor-free graphs were known prior to our work.
UR - http://www.scopus.com/inward/record.url?scp=77951687684&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77951687684&partnerID=8YFLogxK
U2 - 10.1137/1.9781611973075.43
DO - 10.1137/1.9781611973075.43
M3 - Conference contribution
AN - SCOPUS:77951687684
SN - 9780898717013
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 503
EP - 510
BT - Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms
PB - Association for Computing Machinery (ACM)
T2 - 21st Annual ACM-SIAM Symposium on Discrete Algorithms
Y2 - 17 January 2010 through 19 January 2010
ER -