Fixed-Parameter Tractability of the Weighted Edge Clique Partition Problem

Authors Andreas Emil Feldmann , Davis Issac , Ashutosh Rai



PDF
Thumbnail PDF

File

LIPIcs.IPEC.2020.17.pdf
  • Filesize: 0.57 MB
  • 16 pages

Document Identifiers

Author Details

Andreas Emil Feldmann
  • Department of Applied Mathematics, Charles University, Prague, Czech Republic
Davis Issac
  • Hasso Plattner Institute, Potsdam, Germany
Ashutosh Rai
  • Department of Applied Mathematics, Charles University, Prague, Czech Republic

Cite AsGet BibTex

Andreas Emil Feldmann, Davis Issac, and Ashutosh Rai. Fixed-Parameter Tractability of the Weighted Edge Clique Partition Problem. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.IPEC.2020.17

Abstract

We develop an FPT algorithm and a compression for the Weighted Edge Clique Partition (WECP) problem, where a graph with n vertices and integer edge weights is given together with an integer k, and the aim is to find k cliques, such that every edge appears in exactly as many cliques as its weight. The problem has been previously only studied in the unweighted version called Edge Clique Partition (ECP), where the edges need to be partitioned into k cliques. It was shown that ECP admits a kernel with k² vertices [Mujuni and Rosamond, 2008], but this kernel does not extend to WECP. The previously fastest algorithm known for ECP has a runtime of 2^𝒪(k²)n^O(1) [Issac, 2019]. For WECP we develop a compression (to a slightly more general problem) with 4^k vertices, and an algorithm with runtime 2^𝒪(k^(3/2)w^(1/2)log(k/w))n^O(1), where w is the maximum edge weight. The latter in particular improves the runtime for ECP to 2^𝒪(k^(3/2)log k)n^O(1).

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
Keywords
  • Edge Clique Partition
  • fixed-parameter tractability
  • kernelization

Metrics

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

References

  1. Mathieu Blanchette, Ethan Kim, and Adrian Vetta. Clique cover on sparse networks. In Proceedings of the Fourteenth Workshop on Algorithm Engineering and Experiments (ALENEX), pages 93-102, 2012. Google Scholar
  2. Parinya Chalermsook, Sandy Heydrich, Eugenia Holm, and Andreas Karrenbauer. Nearly tight approximability results for minimum biclique cover and partition. In European Symposium on Algorithms, pages 235-246. Springer, 2014. Google Scholar
  3. L Sunil Chandran, Davis Issac, and Andreas Karrenbauer. On the parameterized complexity of biclique cover and partition. In 11th International Symposium on Parameterized and Exact Computation, pages 1-13. Schloss Dagstuhl, 2017. Google Scholar
  4. Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms, volume 4 (8). Springer, 2015. Google Scholar
  5. Marek Cygan, Marcin Pilipczuk, and Michał Pilipczuk. Known algorithms for edge clique cover are probably optimal. SIAM Journal on Computing, 45(1):67-83, 2016. Google Scholar
  6. Andres Figueroa, James Borneman, and Tao Jiang. Clustering binary fingerprint vectors with missing values for dna array data analysis. Journal of Computational biology, 11(5):887-901, 2004. Google Scholar
  7. Rudolf Fleischer and Xiaotian Wu. Edge Clique Partition of K4-Free and Planar Graphs. In International Conference on Computational Geometry, Graphs and Applications, pages 84-95. Springer, 2010. Google Scholar
  8. Herbert Fleischner, Egbert Mujuni, Daniël Paulusma, and Stefan Szeider. Covering graphs with few complete bipartite subgraphs. Theoretical Computer Science, 410(21-23):2045-2053, 2009. Google Scholar
  9. Floris Geerts, Bart Goethals, and Taneli Mielikäinen. Tiling databases. In International conference on discovery science, pages 278-289. Springer, 2004. Google Scholar
  10. Jens Gramm, Jiong Guo, Falk Hüffner, and Rolf Niedermeier. Data reduction, exact, and heuristic algorithms for clique cover. In 2006 Proceedings of the Eighth Workshop on Algorithm Engineering and Experiments (ALENEX), pages 86-94. SIAM, 2006. Google Scholar
  11. Hermann Gruber and Markus Holzer. Inapproximability of nondeterministic state and transition complexity assuming p ≠ np. In International Conference on Developments in Language Theory, pages 205-216. Springer, 2007. Google Scholar
  12. Davis Issac. On some covering, partition and connectivity problems in graphs. PhD thesis, Saarland University, Saarbrücken, Germany, 2019. URL: https://doi.org/10.22028/D291-29620.
  13. Klaus Jansen, Felix Land, and Kati Land. Bounding the running time of algorithms for scheduling and packing problems. SIAM Journal on Discrete Mathematics, 30(1):343-366, 2016. Google Scholar
  14. Viggo Kann. Maximum bounded 3-dimensional matching is max snp-complete. Information Processing Letters, 37(1):27-35, 1991. Google Scholar
  15. L. T. Kou, L. J. Stockmeyer, and C. K. Wong. Covering edges by cliques with regard to keyword conflicts and intersection graphs. Commun. ACM, 21(2):135-139, 1978. URL: https://doi.org/10.1145/359340.359346.
  16. SH Ma, WD Wallis, and JL Wu. The complexity of the clique partition number problem. Congr. Numer, 67:59-66, 1988. Google Scholar
  17. J Matoušek and J Nešetřil. Invitation to Discrete Mathematics. Oxford University Press, 2009. Google Scholar
  18. Egbert Mujuni and Frances Rosamond. Parameterized complexity of the clique partition problem. In Proceedings of the fourteenth symposium on Computing: the Australasian theory-Volume 77, pages 75-78. Australian Computer Society, Inc., 2008. Google Scholar
  19. Vladimir Nikiforov. A contribution to the zarankiewicz problem. Linear algebra and its applications, 432(6):1405-1411, 2010. Google Scholar
  20. Blair Sullivan (University of Utah). Personal communication. Google Scholar
  21. Subramanian Rajagopalan, Manish Vachharajani, and Sharad Malik. Handling irregular ilp within conventional vliw schedulers using artificial resource constraints. In Proceedings of the 2000 international conference on Compilers, architecture, and synthesis for embedded systems, pages 157-164, 2000. Google Scholar
  22. Fred S Roberts. Applications of edge coverings by cliques. Discrete applied mathematics, 10(1):93-109, 1985. Google Scholar
  23. Howard Sachar. The f_p span of the incidence matrix of a finite projective plane. Geometriae Dedicata, 8(4):407-415, 1979. Google Scholar
  24. Xiao-tian Wu, Yu-Hao Lin, and R Fleischer. Research of fixed parameter algorithm for clique partition problem. Computer Engineering, 37(11):92-93, 2011. 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