Document Open Access Logo

Parameterized Lower Bound and Improved Kernel for Diamond-free Edge Deletion

Authors R. B. Sandeep, Naveen Sivadasan

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2015.365.pdf
  • Filesize: 485 kB
  • 12 pages

Document Identifiers

Author Details

R. B. Sandeep
Naveen Sivadasan

Cite As Get BibTex

R. B. Sandeep and Naveen Sivadasan. Parameterized Lower Bound and Improved Kernel for Diamond-free Edge Deletion. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 365-376, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.IPEC.2015.365

Abstract

A diamond is a graph obtained by removing an edge from a complete graph on four vertices. A graph is diamond-free if it does not contain an induced diamond. The Diamond-free Edge Deletion problem asks to find whether there exist at most k edges in the input graph whose deletion results in a diamond-free graph. The problem was proved to be NP-complete and a polynomial kernel of O(k^4) vertices was found by Fellows et. al. (Discrete Optimization, 2011). 

In this paper, we give an improved kernel of O(k^3) vertices for Diamond-free Edge Deletion. We give an alternative proof of the NP-completeness of the problem and observe that it cannot be solved in time 2^{o(k)} * n^{O(1)}, unless the Exponential Time Hypothesis fails.

Subject Classification

Keywords
  • edge deletion problems
  • polynomial kernelization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. N. R. Aravind, R. B. Sandeep, and Naveen Sivadasan. On polynomial kernelization of ℋ-free edge deletion. In Parameterized and Exact Computation, pages 28-38. Springer International Publishing, 2014. Google Scholar
  2. Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Machine Learning, 56(1-3):89-113, 2004. Google Scholar
  3. Hans L. Bodlaender and Babette van Antwerpen-de Fluiter. On intervalizing k-colored graphs for DNA physical mapping. Discrete Applied Mathematics, 71(1-3):55-77, 1996. Google Scholar
  4. Leizhen Cai. Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett., 58(4):171-176, 1996. Google Scholar
  5. Leizhen Cai and Yufei Cai. Incompressibility of H-free edge modification problems. Algorithmica, 71(3):731-757, 2015. Google Scholar
  6. Yufei Cai. 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, China, 2012. Google Scholar
  7. Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Erik Jan van Leeuwen, and Marcin Wrochna. Polynomial kernelization for removing induced claws and diamonds. In WG, 2015. Google Scholar
  8. Pål Grønås Drange and Michał Pilipczuk. A polynomial kernel for trivially perfect editing. In ESA, 2015. Google Scholar
  9. Ehab S El-Mallah and Charles J Colbourn. The complexity of some edge deletion problems. Circuits and Systems, IEEE Transactions on, 35(3):354-362, 1988. Google Scholar
  10. A Farrugia. Clique-helly graphs and hereditary clique-helly graphs, a mini-survey. Algoritmic graph theory (CS 762)-2002-Project, Dept. of Comb., University of Waterloo, 2002. Google Scholar
  11. Michael R. Fellows, Jiong Guo, Christian Komusiewicz, Rolf Niedermeier, and Johannes Uhlmann. Graph-based data clustering with overlaps. Discrete Optimization, 8(1):2-17, 2011. Google Scholar
  12. M. R. Garey, David S. Johnson, and Larry J. Stockmeyer. Some simplified NP-complete graph problems. Theor. Comput. Sci., 1(3):237-267, 1976. Google Scholar
  13. Paul W. Goldberg, Martin Charles Golumbic, Haim Kaplan, and Ron Shamir. Four strikes against physical mapping of DNA. Journal of Computational Biology, 2(1):139-152, 1995. Google Scholar
  14. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. Google Scholar
  15. Stefan Kratsch and Magnus Wahlström. Two edge modification problems without polynomial kernels. Discrete Optimization, 10(3):193-199, 2013. Google Scholar
  16. Bojan Mohar. Face covers and the genus problem for apex graphs. J. Comb. Theory, Ser. B, 82(1):102-117, 2001. Google Scholar
  17. Stephan Olariu. Paw-fee graphs. Inf. Process. Lett., 28(1):53-54, 1988. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact