×
Agrawal, Akanksha; Lokshtanov, Daniel; Misra, Pranabendu; Saurabh, Saket; Zehavi, Meirav

Polynomial kernel for interval vertex deletion. (English) Zbl 07753162

ACM Trans. Algorithms 19, No. 2, Article No. 11, 68 p. (2023).

MSC:

68-XX Computer science

Keywords:

interval vertex deletion; kernelization; polynomial kernel; parameterized complexity

Citations:

Zbl 1282.68131; Zbl 1421.68066; Zbl 1398.68220
Cite Review PDF
Full Text: DOI

References:

[1] Agrawal, Akanksha, Kolay, Sudeshna, Lokshtanov, Daniel, and Saurabh, Saket. 2016. A faster FPT algorithm and a smaller kernel for block graph vertex deletion. In LATIN 2016: Theoretical Informatics. Lecture Notes in Computer Science, Vol. 9644. Springer, 1-13. · Zbl 1417.68145
[2] Agrawal, Akanksha, Lokshtanov, Daniel, Misra, Pranabendu, Saurabh, Saket, and Zehavi, Meirav. 2017. Feedback vertex set inspired kernel for chordal vertex deletion. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’17). SIAM, 1383-1398. · Zbl 1410.68270
[3] Agrawal, Akanksha, Lokshtanov, Daniel, Misra, Pranabendu, Saurabh, Saket, and Zehavi, Meirav. 2019. Feedback vertex set inspired kernel for chordal vertex deletion. ACM Transactions on Algorithms15, 1 (2019), Article 11, 28 pages. · Zbl 1454.68088
[4] Agrawal, Akanksha, Lokshtanov, Daniel, Mouawad, Amer E., and Saurabh, Saket. 2018. Simultaneous feedback vertex set: A parameterized perspective. ACM Transactions on Computation Theory10, 4 (2018), Article 18, 25 pages. · Zbl 1485.68169
[5] Bar-Noy, Amotz, Bar-Yehuda, Reuven, Freund, Ari, Naor, Joseph, and Schieber, Baruch. 2001. A unified approach to approximating resource allocation and scheduling. Journal of the ACM48, 5 (2001), 1069-1090. · Zbl 1323.68564
[6] Bodlaender, Hans L., Downey, Rodney G., Fellows, Michael R., and Hermelin, Danny. 2009. On problems without polynomial kernels. Journal of Computer and System Sciences75, 8 (2009), 423-434. · Zbl 1192.68288
[7] Bollobás, Béla. 1965. On generalized graphs. Acta Mathematica Hungarica16, 3-4 (1965), 447-452. · Zbl 0138.19404
[8] Brandstädt, Andreas, Le, Van Bang, and Spinrad, Jeremy P.. 1999. Graph Classes: A Survey. SIAM, Philadelphia, PA. · Zbl 0919.05001
[9] Cao, Yixin. 2016. Linear recognition of almost interval graphs. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’16). SIAM, 1096-1115. · Zbl 1410.68284
[10] Cao, Yixin. 2017. Unit interval editing is fixed-parameter tractable. Information and Computation253 (2017), 109-126. · Zbl 1359.68230
[11] Cao, Yixin and Marx, Dániel. 2015. Interval deletion is fixed-parameter tractable. ACM Transactions on Algorithms11, 3 (2015), Article 21, 35 pages. · Zbl 1398.68220
[12] Cao, Yixin and Marx, Dániel. 2016. Chordal editing is fixed-parameter tractable. Algorithmica75, 1 (2016), 118-137. · Zbl 1344.68095
[13] Cygan, Marek, Fomin, Fedor V., Kowalik, Łukasz, Lokshtanov, Daniel, Marx, Daniel, Pilipczuk, Marcin, Pilipczuk, Michal, and Saurabh, Saket. 2015. Parameterized Algorithms. Springer-Verlag, Cham, Switzerland. · Zbl 1334.90001
[14] Cygan, Marek, Kowalik, Łukasz, and Pilipczuk, Marcin. 2013. Open problems from Workshop on Kernels.
[15] Dell, Holger and Marx, Dániel. 2012. Kernelization of packing problems. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’12). SIAM, 68-81. · Zbl 1421.68072
[16] Dell, Holger and Melkebeek, Dieter van. 2014. Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. Journal of the ACM61, 4 (2014), Article 23, 27 pages. · Zbl 1321.68274
[17] Diestel, Reinhard. 2010. Graph Theory (4th ed.). Springer-Verlag, Heidelberg, Germany. · Zbl 1204.05001
[18] Downey, Rodney G. and Fellows, Michael R.. 2013. Fundamentals of Parameterized Complexity. Springer, London. · Zbl 1358.68006
[19] Drucker, Andrew. 2015. New limits to classical and quantum instance compression. SIAM Journal on Computing44, 5 (2015), 1443-1479. · Zbl 1330.68092
[20] Flum, Jörg and Grohe, Martin. 2006. Parameterized Complexity Theory. Springer-Verlag, Berlin, Germany. · Zbl 1143.68016
[21] Fomin, Fedor V., Jansen, Bart M. P., and Pilipczuk, Michal. 2014. Preprocessing subgraph and minor problems: When does a small vertex cover help?Journal of Computer and System Sciences80, 2 (2014), 468-495. · Zbl 1277.68095
[22] Fomin, Fedor V., Lokshtanov, Daniel, Misra, Neeldhara, and Saurabh, Saket. 2012. Planar f-deletion: Approximation, kernelization and optimal FPT algorithms. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS’12). IEEE, Los Alamitos, CA, 470-479.
[23] Fomin, Fedor V., Lokshtanov, Daniel, Panolan, Fahad, and Saurabh, Saket. 2016. Efficient computation of representative families with applications in parameterized and exact algorithms. Journal of the ACM63, 4 (2016), Article 29, 60 pages. · Zbl 1410.05212
[24] Fomin, Fedor V. and Saurabh, Saket. 2014. Kernelization methods for fixed-parameter tractability. In Tractability: Practical Approaches to Hard Problems, L. Bordeaux, Y. Hamadi, and P. Kohli (Eds.). Cambridge University Press, Cambridge, UK, 260-282.
[25] Fortnow, Lance and Santhanam, Rahul. 2011. Infeasibility of instance compression and succinct PCPs for NP. Journal of Computer and System Sciences77, 1 (2011), 91-106. · Zbl 1233.68144
[26] Fujito, Toshihiro. 1998. A unified approximation algorithm for node-deletion problems. Discrete Applied Mathematics86, 2-3 (1998), 213-231. · Zbl 0906.68106
[27] Fulkerson, Delbert and Gross, Oliver. 1965. Incidence matrices and interval graphs. Pacific Journal of Mathematics15, 3 (1965), 835-855. · Zbl 0132.21001
[28] Golumbic, Martin Charles. 1980. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, NY. · Zbl 0541.05054
[29] Guo, Jiong and Niedermeier, Rolf. 2007. Invitation to data reduction and problem kernelization. ACM SIGACT News38, 1 (2007), 31-45.
[30] Hermelin, Danny, Kratsch, Stefan, Soltys, Karolina, Wahlström, Magnus, and Wu, Xi. 2015. A completeness theory for polynomial (turing) kernelization. Algorithmica71, 3 (2015), 702-730. · Zbl 1312.68102
[31] Hermelin, Danny and Wu, Xi. 2012. Weak compositions and their applications to polynomial lower bounds for kernelization. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’12). SIAM, 104-113. · Zbl 1421.68086
[32] Jansen, Bart M. P.. 2013. The Power of Data Reduction: Kernels for Fundamental Graph Problems. . Utrecht University.
[33] Jansen, Bart M. P., Lokshtanov, Daniel, and Saurabh, Saket. 2014. A near-optimal planarization algorithm. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’14). SIAM, 1802-1811. · Zbl 1423.68341
[34] Jansen, Bart M. P. and Pilipczuk, Marcin. 2017. Approximation and kernelization for chordal vertex deletion. In Proceedings of the T28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’17). SIAM, 1399-1418. · Zbl 1410.68300
[35] Jansen, Bart M. P. and Pilipczuk, Marcin. 2017. Approximation and kernelization for chordal vertex deletion. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’17. SIAM, 1399-1418. · Zbl 1410.68300
[36] Jansen, Bart M. P. and Pilipczuk, Marcin. 2018. Approximation and kernelization for chordal vertex deletion. SIAM Journal on Discrete Mathematics32, 3 (2018), 2258-2301. · Zbl 1394.05124
[37] Ke, Yuping, Cao, Yixin, Ouyang, Xiating, Li, Wenjun, and Wang, Jianxin. 2018. Unit interval vertex deletion: Fewer vertices are relevant. Journal of Computer and System Sciences95 (2018), 109-121. · Zbl 1391.68058
[38] Kendall, David. 1969. Incidence matrices, interval graphs and seriation in archeology. Pacific Journal of Mathematics28, 3 (1969), 565-570. · Zbl 0185.03301
[39] Kim, Eun Jung and Kwon, O-Joung. 2017. A polynomial kernel for block graph deletion. Algorithmica79, 1 (2017), 251-270. · Zbl 1372.68134
[40] Kim, Eun Jung, Langer, Alexander, Paul, Christophe, Reidl, Felix, Rossmanith, Peter, Sau, Ignasi, and Sikdar, Somnath. 2016. Linear kernels and single-exponential algorithms via protrusion decompositions. ACM Transactions on Algorithms12, 2 (2016), Article 21, 41 pages. · Zbl 1398.68245
[41] Kratsch, Stefan. 2014. Recent developments in kernelization: A survey. · Zbl 1409.68144
[42] Kratsch, Stefan and Wahlström, Magnus. 2012. Representative sets and irrelevant vertices: New tools for kernelization. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS’12). IEEE, Los Alamitos, CA, 450-459.
[43] Lay, David C.. 2006. Linear Algebra and Its Applications. Pearson/Addison-Wesley.
[44] Lekkeikerker, C. and Boland, J.. 1962. Representation of a finite graph by a set of intervals on the real line. Fundamenta Mathematicae51, 1 (1962), 45-64. · Zbl 0105.17501
[45] Lewis, John M. and Yannakakis, Mihalis. 1980. The node-deletion problem for hereditary properties is NP-complete. Journal of Computer and System Sciences20, 2 (1980), 219-230. · Zbl 0436.68029
[46] Lokshtanov, Daniel, Misra, Neeldhara, and Saurabh, Saket. 2012. Kernelization—Preprocessing with a guarantee. In The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday. Springer, Heidelberg, Germany, 129-161. · Zbl 1358.68141
[47] Lovász, László. 1972. A characterization of perfect graphs. Journal of Combinatorial Theory, Series B13, 2 (1972), 95-98. · Zbl 0241.05107
[48] Lund, Carsten and Yannakakis, Mihalis. 1994. On the hardness of approximating minimization problems. Journal of the ACM41, 5 (1994), 960-981. · Zbl 0814.68064
[49] Marx, Dániel. 2009. A parameterized view on matroid optimization problems. Theoretical Computer Science410, 44 (2009), 4471-4479. · Zbl 1180.90275
[50] Marx, Dániel. 2010. Chordal deletion is fixed-parameter tractable. Algorithmica57, 4 (2010), 747-768. · Zbl 1220.05066
[51] Niedermeier, Rolf. 2006. Invitation to Fixed-Parameter Algorithms. Vol. 31. Oxford University Press, Oxford, UK. · Zbl 1095.68038
[52] Oxley, James G.. 2006. Matroid Theory. Vol. 3. Oxford University Press, New York, NY. · Zbl 1115.05001
[53] Yannakakis, Mihalis. 1978. Node- and edge-deletion NP-complete problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC’78). ACM, New York, NY, 253-264. · Zbl 1282.68131
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.