×

Kernel for \(K_t\)-free Edge Deletion. (English) Zbl 1512.05377

Summary: In the \(K_t\)-free Edge Deletion problem the input is a graph \(G\) and an integer \(k\), and the goal is to decide whether there is a set of at most \(k\) edges of \(G\) whose removal results in a graph with no clique of size \(t\). In this paper we give a kernel to this problem with \(O(k^{t-1})\) vertices and edges.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
68Q27 Parameterized complexity, tractability and kernelization
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abu-Khzam, Faisal N., A kernelization algorithm for d-hitting set, J. Comput. Syst. Sci., 76, 7, 524-531 (2010) · Zbl 1197.68083
[2] Brügmann, Daniel; Komusiewicz, Christian; Moser, Hannes, On generating triangle-free graphs, Electron. Notes Discrete Math., 32, 51-58 (2009) · Zbl 1267.05246
[3] Cai, Leizhen; Cai, Yufei, Incompressibility of H-free edge modification problems, Algorithmica, 71, 3, 731-757 (2015) · Zbl 1312.68096
[4] Cai, Yufei, Polynomial kernelisation of H-free edge modification problems (2012), Chinese University of Hong Kong, PhD thesis
[5] Cao, Yixin; Chen, Jianer, Cluster editing: kernelization based on edge cuts, Algorithmica, 64, 1, 152-169 (2012) · Zbl 1253.68144
[6] Cao, Yixin; Ke, Yuping; Yuan, Hanchun, Polynomial kernels for paw-free edge modification problems (2020), arXiv preprint · Zbl 07636422
[7] Cao, Yixin; Rai, Ashutosh; Sandeep, R. B.; Ye, Junjie, A polynomial kernel for diamond-free editing, (Proc. 26th European Symposium on Algorithms (ESA) (2018)), Article 10 pp. · Zbl 1518.68252
[8] Chen, Jianer; Meng, Jie, A 2k kernel for the cluster editing problem, J. Comput. Syst. Sci., 78, 1, 211-220 (2012) · Zbl 1238.68062
[9] Dell, Holger; Marx, Dániel, Kernelization of packing problems, (Proc. 23rd Symposium on Discrete Algorithms (SODA) (2012)), 68-81 · Zbl 1421.68072
[10] Eiben, Eduard; Lochet, William; Saurabh, Saket, A polynomial kernel for paw-free editing (2019), arXiv preprint
[11] Erdös, Paul; Rado, Richard, Intersection theorems for systems of sets, J. Lond. Math. Soc., 1, 1, 85-90 (1960) · Zbl 0103.27901
[12] Fellows, Michael R.; Guo, Jiong; Komusiewicz, Christian; Niedermeier, Rolf; Uhlmann, Johannes, Graph-based data clustering with overlaps, Discrete Optim., 8, 1, 2-17 (2011) · Zbl 1248.90070
[13] Gramm, Jens; Guo, Jiong; Hüffner, Falk; Niedermeier, Rolf, Graph-modeled data clustering: exact algorithms for clique generation, Theory Comput. Syst., 38, 4, 373-392 (2005) · Zbl 1084.68117
[14] Guillemot, Sylvain; Havet, Frédéric; Paul, Christophe; Perez, Anthony, On the (non-) existence of polynomial kernels for \(P_l\)-free edge modification problems, Algorithmica, 65, 4, 900-926 (2013) · Zbl 1262.68048
[15] Marx, Dániel; Sandeep, R. B., Incompressibility of H-free edge modification problems: towards a dichotomy, (Proc. 28th European Symposium on Algorithms (ESA) (2020)), Article 72 pp. · Zbl 07651211
[16] Sandeep, R. B.; Sivadasan, Naveen, Parameterized lower bound and improved kernel for diamond-free edge deletion, (Proc. 10th International Symposium on Parameterized and Exact Computation (IPEC) (2015)) · Zbl 1378.68092
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.