HEXAGONbeta

Universal-Clique Amplification and Hardness of Assignment-Optimal Edge Clique Covers

Primarily AI-generated textHuman understanding: some partscs.CC — Computational Complexitycs.DS — Data Structures and Algorithmsmath.CO — Combinatorics

Contributed by Matěj Kripner ↗, Václav Rozhoň ↗, Robert Šámal ↗, Martin Šindelář, Adrián Zámečník

Version 1 / Nov 04, 2026 / CC BY 4.0

Abstract

An edge clique cover has assignment cost equal to the sum of its clique sizes. Unless P=NPP=NP, this cost admits no polynomial-time O(N1/2−η)O(N^{1/2-\eta})-approximation for any fixed 0<η<1/20<\eta<1/2, even on connected NN-vertex graphs. A universal-clique join transfers coloring hardness without the additive obstruction in earlier reductions. Its exact residual formula also exhibits a change of optimal cover when a universal twin is added. Explicit counterexamples refute two proposed twin-extension rules, while weighted compression of true-twin classes preserves the optimum.

Provenance statement

This work was produced within the Bolzano project (https://bolzano.app), using AI systems for mathematical research and manuscript preparation. The listed authors contributed to the project and the preparation of this release. The manuscript received only limited human checking.

Tools used

Bolzano team
Bolzano

References

  1. W. M. Abdullah and S. Hossain. A sparse matrix approach for covering large complex networks by cliques. In Computational Science---ICCS 2022 , LNCS 13352, pp. 505--517, 2022. doi:10.1007/978-3-031-08757-8_43 (https://doi.org/10.1007/978-3-031-08757-8_43). Author manuscript (https://waliabdullah.github.io/papers/iccs2022_abdullah_clique.pdf).DOI
  2. V. Chvátal. A greedy heuristic for the set-covering problem. Mathematics of Operations Research , 4(3):233--235, 1979. doi:10.1287/moor.4.3.233 (https://doi.org/10.1287/moor.4.3.233).DOI
  3. A. Davoodi, R. Javadi, and B. Omoomi. Edge clique covering sum of graphs. Acta Mathematica Hungarica , 149(1):82--91, 2016. doi:10.1007/s10474-016-0586-1 (https://doi.org/10.1007/s10474-016-0586-1).DOI
  4. A. Davoodi, D. Gerbner, A. Methuku, and M. Vizer. On clique coverings of complete multipartite graphs. Discrete Applied Mathematics , 276:19--23, 2020. doi:10.1016/j.dam.2019.09.014 (https://doi.org/10.1016/j.dam.2019.09.014); arXiv:1809.01443 (https://arxiv.org/abs/1809.01443).arXivDOI
  5. A. Davoodi. Local clique covers and chromatic number. arXiv:2609.07988v1 (https://arxiv.org/abs/2609.07988v1), 7 September 2026.arXiv
  6. J. M. Ennis, C. M. Fayle, and D. M. Ennis. Assignment-minimum clique coverings. ACM Journal of Experimental Algorithmics , 17(1):1.5:1--1.5:17, 2012. doi:10.1145/2133803.2275596 (https://doi.org/10.1145/2133803.2275596).DOI
  7. A. Firbas, A. Dobler, F. Holzer, J. Schafellner, M. Sorge, A. Villedieu, and M. Wiß mann. The complexity of cluster vertex splitting and company. Discrete Applied Mathematics , 365:190--207, 2025. doi:10.1016/j.dam.2025.01.012 (https://doi.org/10.1016/j.dam.2025.01.012).DOI
  8. A. V. Goldberg. Finding a maximum density subgraph. Technical Report UCB/CSD-84-171, EECS Department, University of California, Berkeley, 1984. Berkeley EECS technical-report record (https://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/5956.html).link
  9. D. S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences , 9(3):256--278, 1974. doi:10.1016/S0022-0000(74)80044-9 (https://doi.org/10.1016/S0022-0000(74)80044-9).DOI
  10. L. T. Kou, L. J. Stockmeyer, and C.-K. Wong. Covering edges by cliques with regard to keyword conflicts and intersection graphs. Communications of the ACM , 21(2):135--139, 1978. doi:10.1145/359340.359346 (https://doi.org/10.1145/359340.359346).DOI
Show all 16 referencesShow fewer references
  1. L. Lovász. On the ratio of optimal integral and fractional covers. Discrete Mathematics , 13(4):383--390, 1975. doi:10.1016/0012-365X(75)90058-8 (https://doi.org/10.1016/0012-365X(75)90058-8).DOI
  2. C. Lund and M. Yannakakis. On the hardness of approximating minimization problems. Journal of the ACM , 41(5):960--981, 1994. doi:10.1145/185675.306789 (https://doi.org/10.1145/185675.306789).DOI
  3. D. J. Rose, R. E. Tarjan, and G. S. Lueker. Algorithmic aspects of vertex elimination on graphs. SIAM Journal on Computing , 5(2):266--283, 1976. doi:10.1137/0205021 (https://doi.org/10.1137/0205021).DOI
  4. A. Ullah. Computing clique cover with structural parameterization. arXiv:2208.12438v1 (https://arxiv.org/abs/2208.12438), 2022.arXiv
  5. A. Ullah and A. Pothen. Succinct graph representations and algorithmic applications. arXiv:2604.28096v1 (https://arxiv.org/abs/2604.28096), 2026.arXiv
  6. D. Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing , 3(6):103--128, 2007. doi:10.4086/toc.2007.v003a006 (https://doi.org/10.4086/toc.2007.v003a006).DOI

Version history

  1. v1Submitted by Václav RozhoňInitial depositCurrentNov 03, 2026