Generalising the maximum independent set algorithm via Boolean networks

作     者：Gadouleau, Maximilien Kutner, David C. 

作者机构：Department of Computer Science Durham University Durham United Kingdom 

出 版 物：《arXiv》 (arXiv)

年 卷 期：2024年

核心收录：

主　　题：Consensus algorithm 

摘      要：A simple greedy algorithm to find a maximal independent set (MIS) in a graph starts with the empty set and visits every vertex, adding it to the set if and only if none of its neighbours are already in the set. In this paper, we consider the generalisation of this so-called MIS algorithm by allowing it to start with any set of vertices and we prove the hardness of many decision problems related to this generalisation. Our results are based on two main strategies. Firstly, we view the MIS algorithm as a sequential update of a Boolean network, which we shall refer to as the MIS network, according to a permutation of the vertex set. The set of fixed points of the MIS network corresponds to the set of MIS of the graph. Our generalisation then consists in allowing to start from any configuration and to follow a sequential update given by a word of vertices. Secondly, we introduce the concept of a constituency of a graph, that is a set of vertices that is dominated by an independent set. Deciding whether a set of vertices is a constituency is NP-complete;decision problems related to the MIS algorithm will be reduced from the Constituency problem or its variants. In this paper, we first consider universal configurations, i.e. those that can reach all maximal independent sets;deciding whether a configuration is universal is coNP-complete. Second, we consider so-called fixing words, that allow to reach a MIS regardless of the starting configuration, and fixing permutations, which we call permises;deciding whether a permutation is fixing is coNP-complete. Third, we consider permissible graphs, i.e. those graphs that have a permis. We construct large classes of permissible and non-permissible graphs, notably near-comparability graphs which may be of independent interest;deciding whether a graph is permissible is coNP-hard. Finally, we generalise the MIS algorithm to digraphs. In this case, the algorithm uses the so-called kernel network, whose fixed points are the kernels of t