Edge complexity of weighted graphs: involutory symmetries and NP-hardness
Abstract
The edge complexity of a weighted graph is the smallest ratio of the Fourier ℓ1 and ℓ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 ℓ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 1/256N7/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 N2. 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.
Related
- A Complete Proof of QMA1-Hardness for Weighted Gapped Clique Homology
- Strong NP-Hardness and Approximation Algorithm for Weighted Tardiness with Release Dates and Identical Processing Times
- Acyclic 2-edge-coloured graphs: polynomial-time linkages and colouring hardness
- Weighted Gagliardo--Nirenberg Inequalities of Grushin Type: Symmetries, Compactness, and Optimizers
- Extremal Asymmetric Depth of Planar Graphs and Hidden Near-Mirror Symmetries of IPR Fullerenes
BibTeX
@misc{gupta2026edge,
title = {{Edge complexity of weighted graphs: involutory symmetries and NP-hardness}},
author = {Vishal Gupta and Alex Iosevich},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.23842},
eprint = {2609.23842},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.23842},
}
RIS
TY - UNPB
TI - Edge complexity of weighted graphs: involutory symmetries and NP-hardness
AU - Vishal Gupta
AU - Alex Iosevich
PY - 2026
DA - 2026/09/20
PB - arXiv
DO - 10.48550/arxiv.2609.23842
UR - https://arxiv.org/abs/2609.23842
AB - The edge complexity of a weighted graph is the smallest ratio of the Fourier ℓ^1 and ℓ^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 ℓ^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 1/256N^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.
ER -