Generalising the maximum independent set algorithm via Boolean networks

Gadouleau, Maximilien; Kutner, David C.

Abstract

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 the digraph. Deciding whether the kernel network of a given digraph is fixable is coNP-hard, even for digraphs that have a kernel. As an alternative, we introduce two further Boolean networks, namely the independent and the dominating networks, whose sets of fixed points contain all kernels. Unlike the kernel network, those networks are always fixable and their fixing word problem is in P.

Citation

Gadouleau, M., & Kutner, D. C. (2025). Generalising the maximum independent set algorithm via Boolean networks. Information and Computation, 303, Article 105266. https://doi.org/10.1016/j.ic.2025.105266

• Journal Article Type: Article
• Acceptance Date: Jan 10, 2025
• Online Publication Date: Jan 17, 2025
• Publication Date: 2025-03
• Deposit Date: Jan 22, 2025
• Publicly Available Date: Jan 23, 2025
• Journal: Information and Computation
• Print ISSN: 0890-5401
• Electronic ISSN: 1090-2651
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 303
• Article Number: 105266
• DOI: https://doi.org/10.1016/j.ic.2025.105266
• Public URL: https://durham-repository.worktribe.com/output/3346389