Fixed points in conjunctive networks and maximal independent sets in graph contractions

2015/07/22 by Aracena, Julio, Richard, Adrien, Salinas, Lilian
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1507.06141

Abstract

Given a graph G, viewed as a loop-less symmetric digraph, we study the maximum number of fixed points in a conjunctive boolean network with G as interaction graph. We prove that if G has no induced C₄, then this quantity equals both the number of maximal independent sets in G and the maximum number of maximal independent sets among all the graphs obtained from G by contracting some edges. We also prove that, in the general case, it is coNP-hard to decide if one of these equalities holds, even if G has a unique induced C₄.

Related

• Fixed point theorems for Boolean networks expressed in terms of forbidden subnetworks
• K-Independent Boolean Networks
• Fixed points and connections between positive and negative cycles in Boolean networks
• Positive circuits and maximal number of fixed points in discrete dynamical systems
• The Dynamics of Conjunctive and Disjunctive Boolean Networks