REVIEW 1 cited by
On the Minimum Degree up to Local Complementation: Bounds and Complexity
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
On the Minimum Degree up to Local Complementation: Bounds and Complexity
read the original abstract
The local minimum degree of a graph is the minimum degree reached by means of a series of local complementations. In this paper, we investigate on this quantity which plays an important role in quantum computation and quantum error correcting codes. First, we show that the local minimum degree of the Paley graph of order p is greater than sqrt{p} - 3/2, which is, up to our knowledge, the highest known bound on an explicit family of graphs. Probabilistic methods allows us to derive the existence of an infinite number of graphs whose local minimum degree is linear in their order with constant 0.189 for graphs in general and 0.110 for bipartite graphs. As regards the computational complexity of the decision problem associated with the local minimum degree, we show that it is NP-complete and that there exists no k-approximation algorithm for this problem for any constant k unless P = NP.
Forward citations
Cited by 1 Pith paper
-
Local Equivalences of Graph States
Graph states are LU-equivalent if and only if they are linked by r-local complementations for some integer r; LU-equivalence is decidable in quasi-polynomial time, and LU=LC holds on at most 19 qubits.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.