Logarithmic-Space Six-Clique Counting and Linear-Space Max Cut
We refine the two-order equality contraction of Jabal Ameli, Mohrin, and Nederlof (arXiv:2611.24750). In the same read-only adjacency-matrix model we count six-cliques deterministically in O(n^5.907770) time and O(log n) work bits. With unequal groups and recursive evaluation of exact score constraints, we obtain an O(1.970617^n)-time algorithm for unweighted Max Cut with O(n) work bits, including recovery of an optimal cut. We characterize the exact exponent envelope of the balanced alphabet bound and the limiting base of the specified recursive cost model. Neither limit is a lower bound for the graph problem.
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-21
- DOI
- https://doi.org/10.5281/zenodo.24417480
- Primary Topic
- Complexity and Algorithms in Graphs
- Type
- preprint