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

作者：

Highlights：

• We are interested in the number of fixed points (NFP) in conjunctive boolean networks (CBN).

• Given a graph G, we study the maximum NFP in all the CBN with G as interaction graph.

• We show connexions between this maximum and the number of maximal independent set (MIS) in G.

• We prove that if G is C4-free, then the maximum NFP equals the number of MIS in G.

• We prove that in the general case, it is coNP-Hard to decide is this equality holds.

摘要

•We are interested in the number of fixed points (NFP) in conjunctive boolean networks (CBN).•Given a graph G, we study the maximum NFP in all the CBN with G as interaction graph.•We show connexions between this maximum and the number of maximal independent set (MIS) in G.•We prove that if G is C4-free, then the maximum NFP equals the number of MIS in G.•We prove that in the general case, it is coNP-Hard to decide is this equality holds.

论文关键词：Boolean network,Fixed point,Maximal independent set,Edge contraction

论文评审过程：Received 1 September 2015, Revised 28 February 2017, Accepted 30 March 2017, Available online 14 April 2017, Version of Record 11 June 2017.

论文官网地址：https://doi.org/10.1016/j.jcss.2017.03.016