Two edge modification problems without polynomial kernels. (English) Zbl 1506.68040
Summary: Given a graph \(G\) and an integer \(k\), the \(\varPi\) Edge Completion/Editing/Deletion problem asks whether it is possible to add, edit, or delete at most \(k\) edges in \(G\) such that one obtains a graph that fulfills the property \(\varPi\). Edge modification problems have received considerable interest from a parameterized point of view. When parameterized by \(k\), many of these problems turned out to be fixed-parameter tractable and some are known to admit polynomial kernelizations, i.e., efficient preprocessing with a size guarantee that is polynomial in \(k\). This paper answers an open problem posed by L. Cai [Inf. Process. Lett. 58, No. 4, 171–176 (1996; Zbl 0875.68702)], namely, whether the \(\varPi\) Edge Deletion problem, parameterized by the number of deletions, admits a polynomial kernelization when \(\varPi\) can be characterized by a finite set of forbidden induced subgraphs. We answer this question negatively based on the framework for kernelization lower bounds of H. L. Bodlaender et al. [J. Comput. Syst. Sci. 75, No. 8, 423–434 (2009; Zbl 1192.68288)] and L. Fortnow and R. Santhanam [J. Comput. Syst. Sci. 77, No. 1, 91–106 (2011; Zbl 1233.68144)]. We present a graph \(H\) on seven vertices such that \(H\)-free Edge Deletion and \(H\)-free Edge Editing do not admit polynomial kernelizations, unless \(\mathrm{NP}\subseteq\mathrm{coNP}/\mathrm{poly}\). The application of the framework is not immediate and requires a lower bound for a Not-1-in-3 SAT problem that may be of independent interest.
MSC:
| 68Q27 | Parameterized complexity, tractability and kernelization |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | Brügmann, D.; Komusiewicz, C.; Moser, H., On generating triangle-free graphs, Electronic Notes in Discrete Mathematics, 32, 51-58, (2009) · Zbl 1267.05246 |
| [2] | Díaz, J.; Thilikos, D. M., Fast FPT-algorithms for cleaning grids, (Durand, B.; Thomas, W., STACS, LNCS, vol. 3884, (2006), Springer), 361-371 · Zbl 1136.68456 |
| [3] | Guo, J., Problem kernels for NP-complete edge deletion problems: split and related graphs, (Tokuyama, T., ISAAC, LNCS, vol. 4835, (2007), Springer), 915-926 · Zbl 1193.68194 |
| [4] | Guo, J., A more effective linear kernelization for cluster editing, Theoretical Computer Science, 410, 8-10, 718-726, (2009) · Zbl 1162.68025 |
| [5] | J. Guo, J. Uhlmann, Kernelization and complexity results for connectivity augmentation problems, in: Dehne et al. [25], pp. 483-494. · Zbl 1209.68370 |
| [6] | Burzyn, P.; Bonomo, F.; Durán, G., NP-completeness results for edge modification problems, Discrete Applied Mathematics, 154, 13, 1824-1844, (2006) · Zbl 1110.68094 |
| [7] | Natanzon, A.; Shamir, R.; Sharan, R., Complexity classification of some edge modification problems, Discrete Applied Mathematics, 113, 1, 109-128, (2001) · Zbl 0982.68104 |
| [8] | Rose, D. J., A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations, (Graph Theory and Computing, (1972)), 183-217 · Zbl 0266.65028 |
| [9] | Sharan, R.; Maron-Katz, A.; Shamir, R., CLICK and EXPANDER: a system for clustering and visualizing gene expression data, Bioinformatics, 19, 14, 1787-1799, (2003) |
| [10] | Flum, J.; Grohe, M., (Parameterized Complexity Theory, Texts in Theoretical Computer Science. An EATCS Series, (2006), Springer) · Zbl 1143.68016 |
| [11] | Cai, L., Fixed-parameter tractability of graph modification problems for hereditary properties, Information Processing Letters, 58, 4, 171-176, (1996) · Zbl 0875.68702 |
| [12] | F.N. Abu-Khzam, Kernelization algorithms for \(d\)-hitting set problems, in: Dehne et al. [25], pp. 434-445. · Zbl 1209.68610 |
| [13] | H.L. Bodlaender, L. Cai, J. Chen, M.R. Fellows, J.A. Telle, D. Marx, Open problems in parameterized and exact computation—IWPEC 2006, 2006. |
| [14] | Yap, C.-K., Some consequences of non-uniform conditions on uniform classes, Theoretical Computer Science, 26, 287-300, (1983) · Zbl 0541.68017 |
| [15] | Bodlaender, H. L.; Downey, R. G.; Fellows, M. R.; Hermelin, D., On problems without polynomial kernels, Journal of Computer and System Sciences, 75, 8, 423-434, (2009) · Zbl 1192.68288 |
| [16] | Fortnow, L.; Santhanam, R., Infeasibility of instance compression and succinct PCPs for NP, Journal of Computer and System Sciences, 77, 1, 91-106, (2011) · Zbl 1233.68144 |
| [17] | Kratsch, S.; Wahlström, M., Two edge modification problems without polynomial kernels, (Chen, J.; Fomin, F. V., IWPEC, LNCS, vol. 5917, (2009), Springer), 264-275 · Zbl 1273.68181 |
| [18] | Kratsch, S.; Wahlström, M., Preprocessing of MIN ones problems: a dichotomy, (Abramsky, S.; Gavoille, C.; Kirchner, C.; Meyer auf der Heide, F.; Spirakis, P. G., ICALP (1), LNCS, vol. 6198, (2010), Springer), 653-665 · Zbl 1288.68132 |
| [19] | Downey, R. G.; Fellows, M. R., (Parameterized Complexity, Monographs in Computer Science, (1998), Springer) · Zbl 0914.68076 |
| [20] | Bodlaender, H. L.; Jansen, B. M.P.; Kratsch, S., Cross-composition: a new technique for kernelization lower bounds, (Schwentick, T.; Dürr, C., STACS, LIPIcs, vol. 9, (2011), Schloss Dagstuhl—Leibniz-Zentrum fuer Informatik), 165-176 · Zbl 1230.68085 |
| [21] | H.L. Bodlaender, B.M.P. Jansen, S. Kratsch, Kernelization lower bounds by cross-composition, CoRR abs/1206.5941. · Zbl 1295.05222 |
| [22] | Bodlaender, H. L.; Thomassé, S.; Yeo, A., Kernel bounds for disjoint cycles and disjoint paths, Theoretical Computer Science, 412, 35, 4570-4578, (2011) · Zbl 1221.68099 |
| [23] | Guillemot, S.; Paul, C.; Perez, A., On the (non-)existence of polynomial kernels for \(P_l\)-free edge modification problems, (Raman, V.; Saurabh, S., IPEC, LNCS, vol. 6478, (2010), Springer), 147-157 · Zbl 1309.68151 |
| [24] | A. Perez, Algorithmes de noyau pour des problèmes d’édition de graphes et autres structures, Ph.D. Thesis, Université Montpellier II—LIRMM, Montpellier, France, 2011. |
| [25] | (Dehne, F. K.H. A.; Sack, J.-R.; Zeh, N., 10th International Workshop Algorithms and Data Structures, WADS 2007, Halifax, Canada, August 15-17, 2007, Proceedings, LNCS, vol. 4619, (2007), Springer) · Zbl 1123.68006 |
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.
