Article

Polynomial kernels for hard problems on disk graphs

Author:

Bart JansenAuthors Info & Claims

SWAT'10: Proceedings of the 12th Scandinavian conference on Algorithm Theory

Pages 310 - 321

https://doi.org/10.1007/978-3-642-13731-0_30

Published: 21 June 2010 Publication History

Abstract

Kernelization is a powerful tool to obtain fixed-parameter tractable algorithms. Recent breakthroughs show that many graph problems admit small polynomial kernels when restricted to sparse graph classes such as planar graphs, bounded-genus graphs or H-minor-free graphs. We consider the intersection graphs of (unit) disks in the plane, which can be arbitrarily dense but do exhibit some geometric structure. We give the first kernelization results on these dense graph classes. Connected Vertex Cover has a kernel with 12k vertices on unit-disk graphs and with 3k²+7k vertices on disk graphs with arbitrary radii. Red-Blue Dominating Set parameterized by the size of the smallest color class has a linear-vertex kernel on planar graphs, a quadratic-vertex kernel on unit-disk graphs and a quartic-vertex kernel on disk graphs. Finally we prove that H-Matching on unit-disk graphs has a linear-vertex kernel for every fixed graph H.

References

[1]

Downey, R., Fellows, M.R.: Parameterized complexity. Monographs in Computer Science. Springer, New York (1999)

Digital Library

[2]

Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. SIGACT News 38, 31-45 (2007)

Digital Library

[3]

Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75, 423-434 (2009)

Digital Library

[4]

Guo, J., Niedermeier, R.: Linear problem kernels for NP-hard problems on planar graphs. In: Proc. 34th ICALP, pp. 375-386 (2007)

Digital Library

[5]

Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) Kernelization. In: Proc. 50th FOCS, pp. 629-638 (2009)

Digital Library

[6]

Fomin, F., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: Proc. 21st SODA, pp. 503-510 (2010)

Digital Library

[7]

van Leeuwen, E.J.: Optimization and Approximation on Systems of Geometric Objects. PhD thesis, CWI Amsterdam (2009)

[8]

Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discrete Mathematics 86, 165-177 (1990)

Digital Library

[9]

Marx, D.: Efficient approximation schemes for geometric problems? In: Proc. 13th ESA, pp. 448-459 (2005)

Digital Library

[10]

Marx, D.: Parameterized complexity of independence and domination on geometric graphs. In: Proc. 2nd IWPEC, pp. 154-165 (2006)

Digital Library

[11]

Alber, J., Fiala, J.: Geometric separation and exact solutions for the parameterized independent set problem on disk graphs. J. Algorithms 52, 134-151 (2004)

Digital Library

[12]

Philip, G., Raman, V., Sikdar, S.: Solving dominating set in larger classes of graphs: Fpt algorithms and polynomial kernels. In: Proc. 17th ESA, pp. 694-705 (2009)

[13]

Dom, M., Lokshtanov, D., Saurabh, S.: Incompressibility through colors and ids. In: Proc. 36th ICALP, pp. 378-389 (2009)

Digital Library

[14]

Marathe, M., Breu, H., Iii, H.B.H., Ravi, S.S., Rosenkrantz, D.J.: Simple heuristics for unit disk graphs. Networks 25, 59-68 (1995)

[15]

Wiese, A., Kranakis, E.: Local PTAS for independent set and vertex cover in location aware unit disk graphs. In: Proc. 4th DCOSS, pp. 415-431 (2008)

Digital Library

[16]

Kratochvíl, J., Pergel, M.: Intersection graphs of homothetic polygons. Electronic Notes in Discrete Mathematics 31, 277-280 (2008)

[17]

Moser, H.: A problem kernelization for graph packing. In: Proc. 35th SOFSEM, pp. 401-412 (2009)

Digital Library

[18]

Hunt, H.B., Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. Journal of Algorithms 26, 238-274 (1998)

Digital Library

[19]

Chan, T.M., Har-Peled, S.: Approximation algorithms for maximum independent set of pseudo-disks. In: Proceedings 25th SCG, pp. 333-340 (2009)

Digital Library

[20]

Efrat, A., Sharir, M., Ziv, A.: Computing the smallest k-enclosing circle and related problems. Comput. Geom. 4, 119-136 (1994)

Digital Library

[21]

de Berg, M., Speckmann, B.: Computational geometry: Fundamental structures. In: Handbook of Data Structures and Applications, pp. 62.1-62.20 (2004)

Cited By

Panolan FSaurabh SZehavi M(2024)Contraction Decomposition in Unit Disk Graphs and Algorithmic Applications in Parameterized ComplexityACM Transactions on Algorithms10.1145/364859420:2(1-50)Online publication date: 13-Apr-2024
https://dl.acm.org/doi/10.1145/3648594
Panolan FSaurabh SZehavi MChan T(2019)Contraction decomposition in unit disk graphs and algorithmic applications in parameterized complexityProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310499(1035-1054)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310499
Fomin FLokshtanov DSaurabh S(2018)Excluded Grid Minors and Efficient Polynomial-Time Approximation SchemesJournal of the ACM10.1145/315483365:2(1-44)Online publication date: 31-Jan-2018
https://dl.acm.org/doi/10.1145/3154833
Show More Cited By

Polynomial kernels for hard problems on disk graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation

Recommendations

New kernels for several problems on planar graphs
Abstract
In this paper, we study the kernelization of the Induced Matching problem on planar graphs, the Parameterized Planar 4-Cycle Transversal problem and the Parameterized Planar Edge-Disjoint 4-Cycle Packing problem. For the Induced ...
Short Cycles Make W-hard Problems Hard: FPT Algorithms for W-hard Problems in Graphs with no Short Cycles
Parameterized and Exact Algorithms

We show that several problems that are hard for various parameterized complexity classes on general graphs, become fixed parameter tractable on graphs with no small cycles.

More specifically, we give fixed parameter tractable algorithms for Dominating ...
Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond

We show that for every fixed j ≥ i ≥ 1, the k-Dominating Set problem restricted to graphs that do not have K_ij (the complete bipartite graph on (i + j) vertices, where the two parts have i and j vertices, respectively) as a subgraph is fixed parameter ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

SWAT'10: Proceedings of the 12th Scandinavian conference on Algorithm Theory

June 2010

431 pages

ISBN:364213730X

Editor:
Haim Kaplan
School of Computer Science, Tel Aviv University, Tel Aviv, Israel

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 21 June 2010

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Panolan FSaurabh SZehavi M(2024)Contraction Decomposition in Unit Disk Graphs and Algorithmic Applications in Parameterized ComplexityACM Transactions on Algorithms10.1145/364859420:2(1-50)Online publication date: 13-Apr-2024
https://dl.acm.org/doi/10.1145/3648594
Panolan FSaurabh SZehavi MChan T(2019)Contraction decomposition in unit disk graphs and algorithmic applications in parameterized complexityProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310499(1035-1054)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310499
Fomin FLokshtanov DSaurabh S(2018)Excluded Grid Minors and Efficient Polynomial-Time Approximation SchemesJournal of the ACM10.1145/315483365:2(1-44)Online publication date: 31-Jan-2018
https://dl.acm.org/doi/10.1145/3154833
Fomin FLokshtanov DSaurabh S(2012)Bidimensionality and geometric graphsProceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms10.5555/2095116.2095240(1563-1575)Online publication date: 17-Jan-2012
https://dl.acm.org/doi/10.5555/2095116.2095240

View Options

View options

Figures

Tables

Media

View Table of Conten