Fixed points in conjunctive networks and maximal independent sets in graph contractions
Preprint
Abstract
For a graph $G$, let $\mathcal{C}$ be the set of conjunctive networks with interaction graph $G$, and let $\mathcal{H}$ be the set of graphs obtained from $G$ by contracting some edges. Let $\mathrm{fix}(f)$ be the number of fixed points in a network $f\in \mathcal{C}$, and let $\mathrm{mis}(H)$ be the number of maximal independent sets in $H\in\mathcal{H}$. Our main result is \[\mathrm{mis}(G)~\leq~\max_{H\in\mathcal{H}}\mathrm{mis}(H)~\leq~ \max_{f\in\mathcal{C}}\mathrm{fix}(f)~\leq~ \left(\frac{3}{2}\right)^{m(G)}\mathrm{mis}(G) \] where $m(G)$ is the maximum size of a matching $M$ of $G$ such that every edge of $M$ is contained in an induced copy of $C_4$ that contains no other edge of $M$. Thus if $G$ has no induced $C_4$ then $\max_{H\in\mathcal{H}}\mathrm{mis}(H)=\max_{f\in\mathcal{C}}\mathrm{fix}(f)=\mathrm{mis}(G)$, and this contrasts with following complexity result: It is coNP-hard to decide if $\max_{f\in\mathcal{C}}\mathrm{fix}(f)=\mathrm{mis}(G)$ or if $\max_{H\in\mathcal{H}}\mathrm{mis}(H)=\mathrm{mis}(G)$, even if $G$ has a unique induced copy of $C_4$.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Maximum number of fixed points in AND–OR–NOT networksJournal of Computer and System Sciences, 2014
- Maximum Number of Fixed Points in Regulatory Boolean NetworksBulletin of Mathematical Biology, 2008
- Multistationarity, the basis of cell differentiation and memory. II. Logical analysis of regulatory networks in terms of feedback circuitsChaos: An Interdisciplinary Journal of Nonlinear Science, 2001
- On generating all maximal independent setsInformation Processing Letters, 1988
- The number of maximal independent sets in a connected graphDiscrete Mathematics, 1988
- The number of maximal independent sets in connected graphsJournal of Graph Theory, 1987
- Iterative behaviour of generalized majority functionsMathematical Social Sciences, 1983
- On periodical behaviour in societies with symmetric influencesCombinatorica, 1983
- Neural networks and physical systems with emergent collective computational abilities.Proceedings of the National Academy of Sciences, 1982
- Boolean formalization of genetic control circuitsJournal of Theoretical Biology, 1973