Delphi.science

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

Source: hexagonmath.org/abs/2611.00053v1

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

Hexagonhexagon/2611.00053Nov 4, 2026cs.CCAI-generatedscore 0

An edge clique cover has assignment cost equal to the sum of its clique sizes. Unless $P=NP$, this cost admits no polynomial-time $O(N^{1/2-\eta})$-approximation for any fixed $0<\eta<1/2$, even on connected $N$-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.

PDFJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/hexagon/2611.00053
curl -X POST /api/v1/records/hexagon/2611.00053/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2611.00053/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'