The maximum independent set problem is a classic and fundamental combinatorial challenge, where the objective is to find the largest subset of vertices in a graph such that no two vertices are adjacent. In this paper, we introduce a novel linear prioritized local algorithm tailored to address this problem on random d-regular graphs with a small and fixed degree d. Through exhaustive numerical simulations, we empirically investigated the independence ratio, i.e., the ratio between the cardinality of the independent set found and the order of the graph, which was achieved by our algorithm across random d-regular graphs with degree d ranging from 5 to 100. Remarkably, for every d within this range, our results surpassed the existing lower bounds determined by theoretical methods. Consequently, our findings suggest new conjectured lower bounds for the MIS problem on such graph structures. This finding has been obtained using a prioritized local algorithm. This algorithm is termed ‘prioritized’ because it strategically assigns priority in vertex selection, thereby iteratively adding them to the independent set.

Large Independent Sets on Random d-Regular Graphs with Fixed Degree d / Raffaele Marino. - In: COMPUTATION. - ISSN 2079-3197. - ELETTRONICO. - 11:(2023), pp. 1-17. [10.3390/computation11100206]

Large Independent Sets on Random d-Regular Graphs with Fixed Degree d

Raffaele Marino
2023

Abstract

The maximum independent set problem is a classic and fundamental combinatorial challenge, where the objective is to find the largest subset of vertices in a graph such that no two vertices are adjacent. In this paper, we introduce a novel linear prioritized local algorithm tailored to address this problem on random d-regular graphs with a small and fixed degree d. Through exhaustive numerical simulations, we empirically investigated the independence ratio, i.e., the ratio between the cardinality of the independent set found and the order of the graph, which was achieved by our algorithm across random d-regular graphs with degree d ranging from 5 to 100. Remarkably, for every d within this range, our results surpassed the existing lower bounds determined by theoretical methods. Consequently, our findings suggest new conjectured lower bounds for the MIS problem on such graph structures. This finding has been obtained using a prioritized local algorithm. This algorithm is termed ‘prioritized’ because it strategically assigns priority in vertex selection, thereby iteratively adding them to the independent set.
2023
11
1
17
Raffaele Marino
File in questo prodotto:
File Dimensione Formato  
computation-11-00206.pdf

accesso aperto

Tipologia: Pdf editoriale (Version of record)
Licenza: Open Access
Dimensione 4.93 MB
Formato Adobe PDF
4.93 MB Adobe PDF

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/1335053
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact