On the minimum degree up to local complementation: bounds and complexity
From MaRDI portal
Publication:5200501
DOI10.1007/978-3-642-34611-8_16zbMATH Open1341.05031arXiv1204.4564OpenAlexW3098082123MaRDI QIDQ5200501FDOQ5200501
Jérôme Javelle, Simon Perdrix, Mehdi Mhalla
Publication date: 6 November 2012
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1204.4564
Recommendations
- Minimum degree up to local complementation: bounds, parameterized complexity, and exact algorithms
- Quantum and classical query complexities of local search are polynomially related
- Enhanced algorithms for local search
- Quantum and classical query complexities of local search are polynomially related
- Quantum and randomized lower bounds for local search on vertex-transitive graphs
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Approximation algorithms (68W25) Vertex degrees (05C07)
Cited In (2)
This page was built for publication: On the minimum degree up to local complementation: bounds and complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5200501)
