Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

On the (Non-)Existence of Polynomial Kernels forPl-Free Edge Modification Problems

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

Given a graphG=(V,E) and a positive integerk, an edge modification problem for a graph property Π consists in deciding whether there exists a setF of pairs ofV of size at mostk such that the graph\(H=(V,E\vartriangle F)\) satisfies the property Π. In theΠedge-completion problem, the setF is constrained to be disjoint from E; in theΠedge-deletion problem,F is a subset ofE; no constraint is imposed onF in theΠedge-editing problem. A number of optimization problems can be expressed in terms of graph modification problems which have been extensively studied in the context of parameterized complexity (Cai in Inf. Process. Lett. 58:171–176,1996; Fellows et al. in FCT, pp. 312–321,2007; Heggernes et al. in STOC, pp. 374–381,2007). When parameterized by the sizek of the setF, it has been proved that ifΠ is a hereditary property characterized by a finite set of forbidden induced subgraphs, then the threeΠ edge-modification problems are FPT (Cai in Inf. Process. Lett. 58:171–176,1996). It was then natural to ask (Bodlaender et al. in IWPEC,2006) whether these problems also admit a polynomial kernel. in polynomial time to an equivalent instance (G′,k′) with size bounded by a polynomial ink). Using recent lower bound techniques, Kratsch and Wahlström answered this question negatively (Kratsch and Wahlström in IWPEC, pp. 264–275,2009). However, the problem remains open on many natural graph classes characterized by forbidden induced subgraphs. question to characterize for which type of graph properties, the parameterized edge-modification problems have polynomial kernels. Kratsch and Wahlström asked whether the result holds when the forbidden subgraphs are paths or cycles and pointed out that the problem is already open in the case ofP4-free graphs (i.e. cographs). This paper provides positive and negative results in that line of research. We prove thatParameterized cograph edge-modification problems have cubic vertex kernels whereas polynomial kernels are unlikely to exist for thePl-free edge-deletion and theCl-free edge-deletion problems forl⩾7 andl≥4 respectively. Indeed, if they exist, thenNP⊆coNP/poly.

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.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Explore related subjects

Discover the latest articles and news from researchers in related subjects, suggested using machine learning.

References

  1. Bessy, S., Fomin, F.V., Gaspers, S., Paul, C., Perez, A., Saurabh, S., Thomassé, S.: Kernels for feedback arc set in tournaments. J. Comput. Syst. Sci.77(6), 1071–1078 (2011)

    Article MATH  Google Scholar 

  2. Bessy, S., Paul, C., Perez, A.: Polynomial kernels for 3-leaf power graph modification problems. Discrete Appl. Math.158(16), 1732–1744 (2010)

    Article MathSciNet MATH  Google Scholar 

  3. Bodlaender, H.L., Cai, L., Chen, J., Fellows, M.R., Telle, J.A., Marx, D.: Open problems in parameterized and exact computation. In: International Workshop on Parameterized and Exact Computation (IWPEC) (2006)

    Chapter  Google Scholar 

  4. 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)

    Article MathSciNet MATH  Google Scholar 

  5. Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Cross-composition: A new technique for kernelization lower bounds. In: Symposium on Theoretical Aspects of Computer Science (STACS). Leibniz International Proceedings in Informatics, vol. 9, pp. 165–176 (2011)

    Google Scholar 

  6. Bodlaender, H.L., Thomassé, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci.412(35), 4570–4578 (2011)

    Article MATH  Google Scholar 

  7. Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications (1999)

    Book MATH  Google Scholar 

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

    Article  Google Scholar 

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

    Article MATH  Google Scholar 

  10. Chen, J., Meng, J.: A 2k kernel for the cluster editing problem. In: International Computing and Combinatorics Conference (COCOON). Lecture Notes in Computer Science, vol. 6196, pp. 459–468 (2010)

    Chapter  Google Scholar 

  11. Courcelle, B., Engelfriet, J., Rozenberg, G.: Handle-rewriting hypergraph grammars. J. Comput. Syst. Sci.46(2), 218–270 (1993)

    Article MathSciNet MATH  Google Scholar 

  12. Cunningham, W., Edmonds, J.: A combinatorial decomposition theory. Can. J. Math.32(3), 734–765 (1980)

    Article MathSciNet MATH  Google Scholar 

  13. Downey, R., Fellows, M.: Parameterized Complexity. Springer, Berlin (1999)

    Book  Google Scholar 

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

    Article MathSciNet MATH  Google Scholar 

  15. Fellows, M., Langston, M., Rosamond, F., Shaw, P.: Efficient parameterized preprocessing for cluster editing. In: Fundamentals of Computation Theory, 16th International Symposium (FCT). Lecture Notes in Computer Science, vol. 4639, pp. 312–321 (2007)

    Chapter  Google Scholar 

  16. Flum, J., Grohe, M.: Parameterized Complexity Theory. Text in Theoretical Computer Science. Springer, Berlin (2006)

    Google Scholar 

  17. Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci.77(1), 91–106 (2011)

    Article MathSciNet MATH  Google Scholar 

  18. Garey, M., Johnson, S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1978)

    Google Scholar 

  19. Golumbic, M., Kaplan, H., Shamir, R.: Graph sandwich problems. J. Algorithms19, 449–473 (1995)

    Article MathSciNet MATH  Google Scholar 

  20. Habib, M., Paul, C.: A survey on algorithmic aspects of modular decomposition. Comput. Sci. Rev.4(1), 41–59 (2010)

    Article  Google Scholar 

  21. Heggernes, P., Paul, C., Telle, J.A., Villanger, Y.: Interval completion with few edges. In: ACM Symposium on Theory of Computing (STOC), pp. 374–381 (2007)

    Google Scholar 

  22. Kenyon-Mathieu, C., Schudy, W.: How to rank with few errors. In: ACM Symposium on Theory of Computing (STOC), pp. 95–103 (2007)

    Google Scholar 

  23. Kratsch, S., Wahlström, M.: Two edge modification problems without polynomial kernels. In: International Workshop on Parameterized and Exact Computation (IWPEC). Lecture Notes in Computer Science, vol. 5917, pp. 264–275 (2009)

    Chapter  Google Scholar 

  24. Liu, Y., Wang, J., Guo, J., Chen, J.: Cograph editing: Complexity and parameterized algorithms. In: International Computing and Combinatorics Conference (COCOON). Lecture Notes in Computer Science, vol. 6842, pp. 110–121 (2011)

    Chapter  Google Scholar 

  25. Ma, T.-H., Spinrad, J.: AnO(n2) algorithm for undirected split decomposition. J. Algorithms16, 145–160 (1994)

    Article MathSciNet MATH  Google Scholar 

  26. 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 

  27. Niedermeier, R.: Invitation to Fixed Parameter Algorithms. Oxford Lectures Series in Mathematics and Its Applications, vol. 31. Oxford University Press, London (2006)

    Book MATH  Google Scholar 

  28. Niedermeier, R., Rossmanith, P.: A general method to speed up fixed-parameter-tractable algorithms. Inf. Process. Lett.73(3–4), 125–129 (2000)

    Article MathSciNet MATH  Google Scholar 

  29. Oum, S.: Graphs of bounded rank-width. PhD thesis, Princeton University (2005)

  30. Rose, D.: A graph-theoretic study of the numerical solution of sparse positive systems of linear equations. In: Graph Theory and Computing, pp. 183–217 (1972)

    Google Scholar 

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

    Article MathSciNet MATH  Google Scholar 

  32. Tarjan, R., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput.13, 566–579 (1984)

    Article MathSciNet MATH  Google Scholar 

  33. Thomassé, S.: A 4k2 kernel for feedback vertex set. ACM Trans. Algorithms6(2) (2010)

  34. van Zuylen, A., Williamson, D.P.: Deterministic pivoting algorithms for constrained ranking and clustering problems. Math. Oper. Res.34(3), 594–620 (2009)

    Article MathSciNet MATH  Google Scholar 

Download references

Acknowledgements

The authors would like to thank the anonymous referees for fruitful comments that improved the presentation of this paper. Research supported by the AGAPE project (ANR-09-BLAN-0159).

Author information

Authors and Affiliations

  1. Department of Computer Science, Iowa State University, Ames, IA, 50011, USA

    Sylvain Guillemot

  2. INRIA, CNRS, Université Nice–Sophia-Antipolis, Sophia-Antipolis, France

    Frédéric Havet

  3. LIRMM, Université Montpellier II, CNRS, Montpellier, France

    Christophe Paul

  4. LIFO, Université d’Orléans, Orleans, France

    Anthony Perez

Authors
  1. Sylvain Guillemot

    You can also search for this author inPubMed Google Scholar

  2. Frédéric Havet

    You can also search for this author inPubMed Google Scholar

  3. Christophe Paul

    You can also search for this author inPubMed Google Scholar

  4. Anthony Perez

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toAnthony Perez.

Rights and permissions

About this article

Cite this article

Guillemot, S., Havet, F., Paul, C.et al. On the (Non-)Existence of Polynomial Kernels forPl-Free Edge Modification Problems.Algorithmica65, 900–926 (2013). https://doi.org/10.1007/s00453-012-9619-5

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