Advertisement
Published in:
2015 | OriginalPaper | Chapter
Minimum Degree Up to Local Complementation: Bounds, Parameterized Complexity, and Exact Algorithms
Authors : David Cattanéo, Simon Perdrix
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
The local minimum degree of a graph is the minimum degree that can be reached by means of local complementation. For any n, there exist graphs of order n which have a local minimum degree at least 0.189n, or at least 0.110n when restricted to bipartite graphs. Regarding the upper bound, we show that the local minimum degree is at most \(\frac{3}{8}n+o(n)\) for general graphs and \(\frac{n}{4}+o(n)\) for bipartite graphs, improving the known \(\frac{n}{2}\) upper bound. We also prove that the local minimum degree is smaller than half of the vertex cover number (up to a logarithmic term). The local minimum degree problem is NP-Complete and hard to approximate. We show that this problem, even when restricted to bipartite graphs, is in W[2] and FPT-equivalent to the EvenSet problem, whose W[1]-hardness is a long standing open question. Finally, we show that the local minimum degree is computed by a \(\mathcal O^*(1.938^n)\)-algorithm, and a \(\mathcal O^*(1.466^n)\)-algorithm for the bipartite graphs.