Metraipolis › archive › dc_e02ba9598115
Edge complexity of weighted graphs: involutory symmetries and NP-hardness — arXiv:2609.23842
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.23842
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-09T21:44:54.320Z
- SHA-256 of the archived text
8857435b5bbfecbd1fcec5008c426308574b68a5e44f7c99283ee43c23766824- Stable URL of this page
https://metraipolis.com/documento/dc_e02ba9598115
How to cite
Edge complexity of weighted graphs: involutory symmetries and NP-hardness — arXiv:2609.23842 — arXiv (en), https://arxiv.org/abs/2609.23842 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e02ba9598115 (Metraipolis archive dc_e02ba9598115, sha256 8857435b5bbfecbd1fcec5008c426308574b68a5e44f7c99283ee43c23766824)
BibTeX
@misc{dce02ba9598115,
title = {Edge complexity of weighted graphs: involutory symmetries and NP-hardness — arXiv:2609.23842},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.23842},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e02ba9598115; sha256 8857435b5bbfecbd1fcec5008c426308574b68a5e44f7c99283ee43c23766824},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.23842. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The edge complexity of a weighted graph is the smallest ratio of the Fourier $\ell^1$ and $\ell^2$ norms of its adjacency matrix over all vertex labelings. We study the difficulty of finding this minimum by relating it to a graph symmetry. Adding a universal vertex with sufficiently large incident weight produces an explicit Fourier $\ell^1$ lower bound. We show that equality holds exactly when the source graph has a fixed-point-free involutory automorphism. Two-sided estimates compare the excess above this bound with the squared Frobenius distance to the nearest weighted graph having such a symmetry. For sources of constant weighted degree, these estimates determine the exact leading term as the added weight tends to infinity. A stronger separation for simple source graphs proves that additive $\frac{1}{256N^{\frac{7}{2}}}$ approximation of weighted edge complexity is NP-hard, even on connected graphs of odd order $N$ with at most two distinct positive integer weights, each at most $N^2$. We also prove that recognizing a simple graph with a real Fourier labeling is NP-complete. A seven-vertex example shows that every minimizing labeling can have nonreal Fourier coefficients even when real Fourier labelings exist. An exact rational certificate for this example is included in the appendix.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-22 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.23842 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T21:26:41.136Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).