Maximum independent sets near the upper bound

DOI10.1016/J.DAM.2018.06.042MaRDI QIDQ2026337zbMATH OpenOpenAlexWikidataFDO

Authors Ingo Schiermeyer

Publication date 19 May 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.02475

zbMATH Keywords

fast parameter tractablefpt-algorithmindependence numbermaximum independent setupper bound

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: The size of a largest independent set of vertices in a given graph $G$ is denoted by $alpha(G)$ and is called its independence number (or stability number). Given a graph $G$ and an integer $K,$ it is NP-complete to decide whether $alpha(G)geqK.$ An upper bound for the independence number $alpha(G)$ of a given graph $G$ with $n$ vertices and $m$ edges is given by $alpha(G)leqp:=lfloorfrac12+sqrtfrac14+n^2-n-2mfloor.$ In this paper we will consider maximum independent sets near this upper bound. Our main result is the following: There exists an algorithm with time complexity $O(n^2)$ that, given as an input a graph $G$ with $n$ vertices, $m$ edges, $p:=lfloorfrac12+sqrtfrac14+n^2-n-2mfloor,$ and an integer $kgeq0$ with $pgeq2k+1,$ returns an induced subgraph $G_{p,k}$ of $G$ with $n_{0}leqp+2k+1$ vertices such that $alpha(G)leqp-k$ if and only if $alpha(G_{p,k})leqp-k.$ Furthermore, we will show that we can decide in time $O(1.2738^{3k}+kn)$ whether $alpha(G_{p,k})leqp-k.$

Recommendations

• Algorithms for maximum independent sets
• An upper bound on the independence number of a graph computable in polynomial-time
• scientific article; zbMATH DE number 1305487
• scientific article; zbMATH DE number 867639
• Exact Algorithms for Maximum Independent Set

Cites work

• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• An upper bound for the chromatic number of a graph and its application to timetabling problems
• scientific article; zbMATH DE number 3445275 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• Improved upper bounds for vertex cover
• Independent sets near the lower bound in bounded degree graphs
• On maximal independent sets of vertices in claw-free graphs
• Problems remaining NP-complette for sparse or dense graphs
• The maximum independent set problem in subclasses of subcubic graphs
• The Rectilinear Steiner Tree Problem is NP-Complete

Cited in

(12)

• On generating all maximal independent sets
• On the maximum number of maximum independent sets
• Analysis of the influence of the number of edges on the complexity of the independent set problem
• The max quasi-independent set Problem
• scientific article; zbMATH DE number 1305522 (Why is no real title available?)
• scientific article; zbMATH DE number 3995720 (Why is no real title available?)
• scientific article; zbMATH DE number 4122023 (Why is no real title available?)
• Lower Bounds for Maximal Matchings and Maximal Independent Sets
• The star degree centrality problem: a decomposition approach
• A note on -redundant vertices in graphs
• A generalization of maximal independent sets
• On the independence number of a graph in terms of order and size

This page was built for publication: Maximum independent sets near the upper bound

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2026337)