×

zbMATH — the first resource for mathematics

Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP. (English) Zbl 1236.68097
Summary: It has been observed in many places that constant-factor approximable problems often admit polynomial or even linear problem kernels for their decision versions, e.g., Vertex Cover, Feedback Vertex Set, and Triangle Packing. While there exist examples like Bin Packing, which does not admit any kernel unless P = NP, there apparently is a strong relation between these two polynomial-time techniques. We add to this picture by showing that the natural decision versions of all problems in two prominent classes of constant-factor approximable problems, namely MIN \(F^{+}\Pi _{1}\) and MAX NP, admit polynomial problem kernels. Problems in MAX SNP, a subclass of MAX NP, are shown to admit kernels with a linear base set, e.g., the set of vertices of a graph. This extends results of L. Cai and J. Chen [J. Comput. Syst. Sci. 54, No. 3, 465–474 (1997; Zbl 0882.68064)], stating that the standard parameterizations of problems in MAX SNP and MIN \(F^{+}\Pi _{1}\) are fixed-parameter tractable, and complements recent research on problems that do not admit polynomial kernelizations [H. L. Bodlaender et al., J. Comput. Syst. Sci. 75, No. 8, 423–434 (2009; Zbl 1192.68288)].

MSC:
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abu-Khzam, F.N.: A kernelization algorithm for d-hitting set. J. Comput. Syst. Sci. 76(7), 524–531 (2010) · Zbl 1197.68083 · doi:10.1016/j.jcss.2009.09.002
[2] Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. J. ACM 45(3), 501–555 (1998) · Zbl 1065.68570 · doi:10.1145/278298.278306
[3] Bafna, V., Berman, P., Fujito, T.: A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discrete Math. 12(3), 289–297 (1999) · Zbl 0932.68054 · doi:10.1137/S0895480196305124
[4] Bodlaender, H.L.: Kernelization: new upper and lower bound techniques. In: Chen, J., Fomin, F.V. (eds.) Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Revised Selected Papers, Copenhagen, Denmark, 10–11 September 2009. Lecture Notes in Computer Science, vol. 5917, pp. 17–37. Springer, Berlin (2009) · Zbl 1273.68158
[5] Bodlaender, H.L., Thomassé, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. In: Fiat, A., Sanders, P. (eds.) ESA. Lecture Notes in Computer Science, vol. 5757, pp. 635–646. Springer, Berlin (2009) · Zbl 1256.68081
[6] Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) Kernelization. In: FOCS, pp. 629–638. IEEE Computer Society, Los Alamitos (2009) · Zbl 1292.68089
[7] Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423–434 (2009) · Zbl 1192.68288 · doi:10.1016/j.jcss.2009.04.001
[8] Cai, L., Chen, J.: On fixed-parameter tractability and approximability of NP optimization problems. J. Comput. Syst. Sci. 54(3), 465–474 (1997) · Zbl 0882.68064 · doi:10.1006/jcss.1997.1490
[9] Cai, L., Huang, X.: Fixed-parameter approximation: conceptual framework and approximability results. Algorithmica 57(2), 398–412 (2010) · Zbl 1186.68557 · doi:10.1007/s00453-008-9223-x
[10] Chen, J., Fomin, F.V. (eds.): Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Revised Selected Papers, Copenhagen, Denmark, 10–11 September 2009. Lecture Notes in Computer Science, vol. 5917. Springer, Berlin (2009) · Zbl 1178.68005
[11] Chen, J., Kanj, I.A., Jia, W.: Vertex cover: further observations and further improvements. J. Algorithms 41(2), 280–301 (2001) · Zbl 1017.68087 · doi:10.1006/jagm.2001.1186
[12] Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. In: Schulman, L.J. (ed.) STOC, pp. 251–260. ACM, New York (2010) · Zbl 1293.68132
[13] Dom, M., Lokshtanov, D., Saurabh, S.: Incompressibility through colors and ids. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S.E., Thomas, W. (eds.) ICALP (1). Lecture Notes in Computer Science, vol. 5555, pp. 378–389. Springer, Berlin (2009) · Zbl 1248.68243
[14] Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, Berlin (1998) · Zbl 0914.68076
[15] Erdos, P., Rado, R.: Intersection theorems for systems of sets. J. Lond. Math. Soc. 35, 85–90 (1960) · Zbl 0103.27901 · doi:10.1112/jlms/s1-35.1.85
[16] Fagin, R.: Generalized first-order spectra and polynomial-time recognizable sets. In: Complexity of Computation. SIAM-AMS Proceedings, vol. 7, pp. 43–73. SIAM, Philadelphia (1974) · Zbl 0303.68035
[17] Feige, U., Hajiaghayi, M., Lee, J.R.: Improved approximation algorithms for minimum weight vertex separators. SIAM J. Comput. 38(2), 629–657 (2008) · Zbl 1172.68063 · doi:10.1137/05064299X
[18] Fernau, H., Fomin, F.V., Lokshtanov, D., Raible, D., Saurabh, S., Villanger, Y.: Kernel(s) for problems with no kernel: on out-trees with many leaves. In: Albers, S., Marion, J.-Y. (eds.) STACS. Dagstuhl Seminar Proceedings, vol. 09001, pp. 421–432. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Germany (2009) · Zbl 1236.68087
[19] Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An Eatcs Series. Springer, Berlin (2006)
[20] Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: Charikar, M. (ed.) SODA, pp. 503–510. SIAM, Philadelphia (2010) · Zbl 1288.68116
[21] Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77(1), 91–106 (2011) · Zbl 1233.68144 · doi:10.1016/j.jcss.2010.06.007
[22] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of Np-completeness. Freeman, New York (1979) · Zbl 0411.68039
[23] Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. SIGACT News 38(1), 31–45 (2007) · doi:10.1145/1233481.1233493
[24] Halperin, E.: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM J. Comput. 31(5), 1608–1623 (2002) · Zbl 1041.68130 · doi:10.1137/S0097539700381097
[25] Khanna, S., Motwani, R., Sudan, M., Vazirani, U.V.: On syntactic versus computational views of approximability. SIAM J. Comput. 28(1), 164–191 (1998) · Zbl 0915.68068 · doi:10.1137/S0097539795286612
[26] Kolaitis, P.G., Thakur, M.N.: Logical definability of NP optimization problems. Inf. Comput. 115(2), 321–353 (1994) · Zbl 0820.68048 · doi:10.1006/inco.1994.1100
[27] Kolaitis, P.G., Thakur, M.N.: Approximation properties of NP minimization classes. J. Comput. Syst. Sci. 50(3), 391–411 (1995) · Zbl 0837.68028 · doi:10.1006/jcss.1995.1031
[28] Kratsch, S., Wahlström, M.: Two edge modification problems without polynomial kernels. In: Chen, J., Fomin, F.V. (eds.) Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Revised Selected Papers, Copenhagen, Denmark, 10–11 September 2009. Lecture Notes in Computer Science, vol. 5917, pp. 264–275. Springer, Berlin (2009) · Zbl 1273.68181
[29] Kratsch, S., Wahlström, M.: Preprocessing of min ones problems: a dichotomy. In: Abramsky, S., Gavoille, C., Kirchner, C., auf der Heide, F.M., Spirakis, P.G. (eds.) ICALP (1). Lecture Notes in Computer Science, vol. 6198, pp. 653–665. Springer, Berlin (2010) · Zbl 1288.68132
[30] Kratsch, S., Marx, D., Wahlström, M.: Parameterized complexity and kernelizability of max ones and exact ones problems. In: Hlinený, P., Kucera, A. (eds.) MFCS. Lecture Notes in Computer Science, vol. 6281, pp. 489–500. Springer, Berlin (2010) · Zbl 1287.68077
[31] Mahajan, M., Raman, V., Sikdar, S.: Parameterizing MAX SNP problems above guaranteed values. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC. Lecture Notes in Computer Science, vol. 4169, pp. 38–49. Springer, Berlin (2006) · Zbl 1154.68430
[32] Mahajan, M., Raman, V., Sikdar, S.: Parameterizing above or below guaranteed values. J. Comput. Syst. Sci. 75(2), 137–153 (2009) · Zbl 1155.68400 · doi:10.1016/j.jcss.2008.08.004
[33] Mölle, D., Richter, S., Rossmanith, P.: Enumerate and expand: improved algorithms for connected vertex cover and tree cover. Theory Comput. Syst. 43(2), 234–253 (2008) · Zbl 1148.68041 · doi:10.1007/s00224-007-9089-3
[34] Natanzon, A., Shamir, R., Sharan, R.: A polynomial approximation algorithm for the minimum fill-in problem. SIAM J. Comput. 30(4), 1067–1079 (2000) · Zbl 0969.68194 · doi:10.1137/S0097539798336073
[35] Niedermeier, R.: Invitation to Fixed Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press, London (2006) · Zbl 1095.68038
[36] Papadimitriou, C.H.: Computational Complexity. Addison Wesley, Reading (1993) · Zbl 0557.68033
[37] Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425–440 (1991) · Zbl 0765.68036 · doi:10.1016/0022-0000(91)90023-X
[38] Savage, C.D.: Depth-first search and the vertex cover problem. Inf. Process. Lett. 14(5), 233–237 (1982) · Zbl 0498.68041 · doi:10.1016/0020-0190(82)90022-9
[39] Simchi-Levi, D.: New worst-case results for the bin-packing problem. Nav. Res. Logist. 41, 579–585 (1994) · Zbl 0809.90111 · doi:10.1002/1520-6750(199406)41:4<579::AID-NAV3220410409>3.0.CO;2-G
[40] Thomassé, S.: A quadratic kernel for feedback vertex set. In: Mathieu, C. (ed.) SODA, pp. 115–119. SIAM, Philadelphia (2009)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.