Movatterモバイル変換

[0]ホーム
URL:

Skip to main content
Springer Nature Link
Log in

On Polynomial Kernelization of\(\mathcal {H}\)-free Edge Deletion

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

For a set\(\mathcal {H}\) of graphs, the\(\mathcal {H}\)-free Edge Deletion problem is to decide whether there exist at mostk edges in the input graph, for some\(k\in \mathbb {N}\), whose deletion results in a graph without an induced copy of any of the graphs in\(\mathcal {H}\) . The problem is known to be fixed-parameter tractable if\(\mathcal {H}\) is of finite cardinality. In this paper, we present a polynomial kernel for this problem for any fixed finite set\(\mathcal {H}\) of connected graphs for the case where the input graphs are of bounded degree. We use a single kernelization rule which deletes vertices ‘far away’ from the induced copies of every\(H\in \mathcal {H}\) in the input graph. With a slightly modified kernelization rule, we obtain polynomial kernels for\(\mathcal {H}\)-free Edge Deletion under the following three settings:

  • \(\mathcal {H}\) contains\(K_{1,s}\) and\(K_t\);

  • \(\mathcal {H}\) contains\(K_{1,s}\) and the input graphs are\(K_t\)-free;

  • \(\mathcal {H}\) contains\(K_{t}\) and the input graphs are\(K_{1,s}\)-free;

where\(s>1\) and\(t>2\) are any fixed integers. Our result provides the first polynomial kernels forClaw-free Edge Deletion andLine Edge Deletion for\(K_t\)-free input graphs which are known to be NP-complete even for\(K_4\)-free graphs.

This is a preview of subscription content,log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. Alon, N., Shapira, A., Sudakov, B.: Additive approximation for edge-deletion problems. Ann. Math.170(1), 371–411 (2009)

  2. Aravind, N.R., Sandeep, R.B., Sivadasan, N.: Parameterized lower bounds and dichotomy results for the NP-completeness of H-free edge modification problems. In: LATIN 2016: Theoretical Informatics —12th Latin American Symposium, pp. 82–95 (2016)

  3. Asano, T., Hirata, T.: Edge-deletion and edge-contraction problems. In: Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pp. 245–254. ACM (1982)

  4. Beineke, L.W.: Characterizations of derived graphs. J. Comb. Theory9(2), 129–135 (1970)

    Article MathSciNet MATH  Google Scholar 

  5. Brügmann, D., Komusiewicz, C., Moser, H.: On generating triangle-free graphs. Electron. Notes Discrete Math.32, 51–58 (2009)

    Article MathSciNet MATH  Google Scholar 

  6. Burzyn, P., Bonomo, F., Durán, G.: NP-completeness results for edge modification problems. Discrete Appl. Math.154(13), 1824–1844 (2006)

    Article MathSciNet MATH  Google Scholar 

  7. Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett.58(4), 171–176 (1996)

    Article MathSciNet MATH  Google Scholar 

  8. Cai, L., Cai, Y.: Incompressibility of H-free edge modification problems. Algorithmica71(3), 731–757 (2015)

    Article MathSciNet MATH  Google Scholar 

  9. Cai, Y.: Polynomial kernelisation of H-free edge modification problems. Mphil Thesis, Department of Computer Science and Engineering, The Chinese University of Hong Kong, Hong Kong SAR (2012)

  10. Cygan, M., Fomin, F.V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Switzerland (2015)

    Book MATH  Google Scholar 

  11. Cygan, M., Kowalik, Ł., Pilipczuk, M.: Open Problems from Workshop on Kernels. Worker 2013 (2013)

  12. Cygan, M., Pilipczuk, M., Pilipczuk, M., van Leeuwen, E.J., Wrochna, M.: Polynomial kernelization for removing induced claws and diamonds. In: Graph-Theoretic Concepts in Computer Science - 41st International Workshop, WG 2015, pp. 440–455 (2015)

  13. Drange, P.G., Dregi, M.S., Sandeep, R.B.: Compressing bounded degree graphs. In: LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, pp. 362–375 (2016)

  14. Drange, P.G., Pilipczuk, M.: A polynomial kernel for trivially perfect editing. In: Algorithms - ESA 2015 - 23rd Annual European Symposium, pp. 424–436 (2015)

  15. El-Mallah, E.S., Colbourn, C.J.: The complexity of some edge deletion problems. IEEE Trans. Circuits Syst.35(3), 354–362 (1988)

    Article MathSciNet MATH  Google Scholar 

  16. Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theor. Comput. Sci.1(3), 237–267 (1976)

    Article MathSciNet MATH  Google Scholar 

  17. Ghosh, E., Kolay, S., Kumar, M., Misra, P., Panolan, F., Rai, A., Ramanujan, M.: Faster parameterized algorithms for deletion to split graphs. Algorithmica71(4), 989–1006 (2013)

    Article MathSciNet MATH  Google Scholar 

  18. Goldberg, P.W., Golumbic, M.C., Kaplan, H., Shamir, R.: Four strikes against physical mapping of DNA. J. Comput. Biol.2(1), 139–152 (1995)

    Article  Google Scholar 

  19. Gramm, J., Guo, J., Hüffner, F., Niedermeier, R.: Graph-modeled data clustering: Fixed-parameter algorithms for clique generation. Theory Comput. Syst.38(4), 373–392 (2005)

    Article MathSciNet MATH  Google Scholar 

  20. Guillemot, S., Havet, F., Paul, C., Perez, A.: On the (non-) existence of polynomial kernels for\(P_l\)-free edge modification problems. Algorithmica65(4), 900–926 (2013)

    Article MathSciNet MATH  Google Scholar 

  21. Guo, J.: Problem kernels for NP-complete edge deletion problems: split and related graphs. In: Algorithms and Computation, 18th International Symposium, ISAAC 2007, pp. 915–926 (2007)

  22. Hadlock, F.: Finding a maximum cut of a planar graph in polynomial time. SIAM J. Comput.4(3), 221–225 (1975)

    Article MathSciNet MATH  Google Scholar 

  23. Komusiewicz, C., Uhlmann, J.: Cluster editing with locally bounded modifications. Discrete Appl. Math.160(15), 2259–2270 (2012)

    Article MathSciNet MATH  Google Scholar 

  24. Kratsch, S., Wahlström, M.: Two edge modification problems without polynomial kernels. Discrete Optim.10(3), 193–199 (2013)

    Article MathSciNet MATH  Google Scholar 

  25. Le, V.B., Mosca, R., Müller, H.: On stable cutsets in claw-free graphs and planar graphs. J. Discrete Algorithms6(2), 256–276 (2008)

    Article MathSciNet MATH  Google Scholar 

  26. Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci.20(2), 219–230 (1980)

    Article MathSciNet MATH  Google Scholar 

  27. Liu, P., Geldmacher, R.: On the deletion of nonplanar edges of a graph. In: Proceedings on 10th Southeastern Conference on Combinatorics, Graph Theory, and Computing, pp. 727–738 (1977)

  28. Margot, F.: Some complexity results about threshold graphs. Discrete Appl. Math.49(1), 299–308 (1994)

    Article MathSciNet MATH  Google Scholar 

  29. Nastos, J., Gao, Y.: Bounded search tree algorithms for parametrized cograph deletion: efficient branching rules by exploiting structures of special graph classes. Discrete Math. Algorithms Appl.4(01), 1250,008 (2012)

    Article MathSciNet MATH  Google Scholar 

  30. Natanzon, A.: Complexity and approximation of some graph modification problems. Master’s Thesis, Tel Aviv University (1999)

  31. Natanzon, A., Shamir, R., Sharan, R.: Complexity classification of some edge modification problems. Discrete Appl. Math.113(1), 109–128 (2001)

    Article MathSciNet MATH  Google Scholar 

  32. Peeters, R.: The maximum edge biclique problem is NP-complete. Discrete Appl. Math.131(3), 651–654 (2003)

    Article MathSciNet MATH  Google Scholar 

  33. Sandeep, R.B., Sivadasan, N.: Parameterized lower bound and improved kernel for diamond-free edge deletion. In: 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, pp. 365–376 (2015)

  34. Shamir, R., Sharan, R., Tsur, D.: Cluster graph modification problems. Discrete Appl. Math.144(1), 173–182 (2004)

    Article MathSciNet MATH  Google Scholar 

  35. Sharan, R.: Graph modification problems and their applications to genomic research. Ph.D. thesis, Tel-Aviv University (2002)

  36. Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM J. Algebraic Discrete Methods2(1), 77–79 (1981)

    Article MathSciNet MATH  Google Scholar 

  37. Yannakakis, M.: Edge-deletion problems. SIAM J. Comput.10(2), 297–309 (1981)

    Article MathSciNet MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science and Engineering Department, Indian Institute of Technology Hyderabad, Sangareddy, India

    N. R. Aravind & R. B. Sandeep

  2. TCS Innovation Labs, Hyderabad, India

    Naveen Sivadasan

Authors
  1. N. R. Aravind

    You can also search for this author inPubMed Google Scholar

  2. R. B. Sandeep

    You can also search for this author inPubMed Google Scholar

  3. Naveen Sivadasan

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toR. B. Sandeep.

Additional information

A preliminary version of this paper with the same title has appeared in the proceedings of IPEC 2014.

R. B. Sandeep: Supported by TCS Research Scholarship.

Rights and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Aravind, N.R., Sandeep, R.B. & Sivadasan, N. On Polynomial Kernelization of\(\mathcal {H}\)-free Edge Deletion .Algorithmica79, 654–666 (2017). https://doi.org/10.1007/s00453-016-0215-y

Download citation

Keywords

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Advertisement

[8]ページ先頭
©2009-2025 Movatter.jp