Maximum independent sets near the upper bound
type: Item
instance of: scholarly article
title: Maximum independent sets near the upper bound
zbMATH Open document ID: 1473.05232
author: Ingo Schiermeyer
published in: Discrete Applied Mathematics
publication date: 2021-05-19T00:00:00Z
full work available at URL: https://arxiv.org/abs/1709.02475
review text: An independent set of a graph \(G\) is a set of vertices where no two vertices are adjacent. The independence number is the size of a maximum independent set in the graph and is denoted by \(\alpha(G)\). Let us recall the following upper bound for \(\alpha(G)\): Theorem. Let \(G\) be a graph of order \(n\) and size \(m\). Then \[\alpha(G)\leq p:=\lfloor \frac{1}{2}+\sqrt{\frac{1}{4}+n^2-n-2m}\rfloor.\] The author considers independent sets near the above upper bound and proved the following result: Theorem. There exists an algorithm with time complexity \(O(n^2)\) that, given as an input a graph \(G\) of order \(n\), size \(m\), \(p:=\lfloor \frac{1}{2}+\sqrt{\frac{1}{4}+n^2-n-2m}\rfloor\) and an integer \(k\geq 0\) with \(p\geq2k+1\), returns an induced subgraph \(G_{p,k}\) of \(G\) with \(n_0\leq p+2k+1\) vertices such that \(\alpha(G) \leq p-k\) if and only if \(\alpha(G_{p,k})\leq p-k.\) Furthermore, he shows that one can decide in \(O(1.2738^{3k}+n^2)\) time whether \(\alpha(G_{p,k})\leq p-k\).
reviewed by: Saeid Alikhani
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 7349658
zbMATH Keywords: maximum independent set
zbMATH Keywords: independence number
zbMATH Keywords: upper bound
zbMATH Keywords: fast parameter tractable
zbMATH Keywords: fpt-algorithm
MaRDI profile type: MaRDI publication profile
OpenAlex ID: W2963358149
arXiv ID: 1709.02475
cites work: The maximum independent set problem in subclasses of subcubic graphs
cites work: Q5782525
cites work: Improved upper bounds for vertex cover
cites work: Independent sets near the lower bound in bounded degree graphs
cites work: The Rectilinear Steiner Tree Problem is $NP$-Complete
cites work: On maximal independent sets of vertices in claw-free graphs
cites work: Q4770411
cites work: Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
cites work: Problems remaining NP-complette for sparse or dense graphs
cites work: An upper bound for the chromatic number of a graph and its application to timetabling problems
Wikidata QID: Q129403042
DOI: 10.1016/J.DAM.2018.06.042
description: scientific article