IEICE TRANSACTIONS on Fundamentals
On the Complexity of Inference and Completion of Boolean Networks from Given Singleton Attractors
Summary :
In this paper, we consider the problem of inferring a Boolean network (BN) from a given set of singleton attractors, where it is required that the resulting BN has the same set of singleton attractors as the given one. We show that the problem can be solved in linear time if the number of singleton attractors is at most two and each Boolean function is restricted to be a conjunction or disjunction of literals. We also show that the problem can be solved in polynomial time if more general Boolean functions can be used. In addition to the inference problem, we study two network completion problems from a given set of singleton attractors: adding the minimum number of edges to a given network, and determining Boolean functions to all nodes when only network structure of a BN is given. In particular, we show that the latter problem cannot be solved in polynomial time unless P=NP, by means of a polynomial-time Turing reduction from the complement of the another solution problem for the Boolean satisfiability problem.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E96-A No.11 pp.2265-2274
- Publication Date
- 2013/11/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E96.A.2265
- Type of Manuscript
- PAPER
- Category
- General Fundamentals and Boundaries
Authors
Hao JIANG
Renmin University of China,The University of Hong Kong
Takeyuki TAMURA
Kyoto University
Wai-Ki CHING
The University of Hong Kong
Tatsuya AKUTSU
Kyoto University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Hao JIANG, Takeyuki TAMURA, Wai-Ki CHING, Tatsuya AKUTSU, "On the Complexity of Inference and Completion of Boolean Networks from Given Singleton Attractors" in IEICE TRANSACTIONS on Fundamentals,
vol. E96-A, no. 11, pp. 2265-2274, November 2013, doi: 10.1587/transfun.E96.A.2265.
Abstract: In this paper, we consider the problem of inferring a Boolean network (BN) from a given set of singleton attractors, where it is required that the resulting BN has the same set of singleton attractors as the given one. We show that the problem can be solved in linear time if the number of singleton attractors is at most two and each Boolean function is restricted to be a conjunction or disjunction of literals. We also show that the problem can be solved in polynomial time if more general Boolean functions can be used. In addition to the inference problem, we study two network completion problems from a given set of singleton attractors: adding the minimum number of edges to a given network, and determining Boolean functions to all nodes when only network structure of a BN is given. In particular, we show that the latter problem cannot be solved in polynomial time unless P=NP, by means of a polynomial-time Turing reduction from the complement of the another solution problem for the Boolean satisfiability problem.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E96.A.2265/_p
Copy
@ARTICLE{e96-a_11_2265,
author={Hao JIANG, Takeyuki TAMURA, Wai-Ki CHING, Tatsuya AKUTSU, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On the Complexity of Inference and Completion of Boolean Networks from Given Singleton Attractors},
year={2013},
volume={E96-A},
number={11},
pages={2265-2274},
abstract={In this paper, we consider the problem of inferring a Boolean network (BN) from a given set of singleton attractors, where it is required that the resulting BN has the same set of singleton attractors as the given one. We show that the problem can be solved in linear time if the number of singleton attractors is at most two and each Boolean function is restricted to be a conjunction or disjunction of literals. We also show that the problem can be solved in polynomial time if more general Boolean functions can be used. In addition to the inference problem, we study two network completion problems from a given set of singleton attractors: adding the minimum number of edges to a given network, and determining Boolean functions to all nodes when only network structure of a BN is given. In particular, we show that the latter problem cannot be solved in polynomial time unless P=NP, by means of a polynomial-time Turing reduction from the complement of the another solution problem for the Boolean satisfiability problem.},
keywords={},
doi={10.1587/transfun.E96.A.2265},
ISSN={1745-1337},
month={November},}
Copy
TY - JOUR
TI - On the Complexity of Inference and Completion of Boolean Networks from Given Singleton Attractors
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2265
EP - 2274
AU - Hao JIANG
AU - Takeyuki TAMURA
AU - Wai-Ki CHING
AU - Tatsuya AKUTSU
PY - 2013
DO - 10.1587/transfun.E96.A.2265
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E96-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 2013
AB - In this paper, we consider the problem of inferring a Boolean network (BN) from a given set of singleton attractors, where it is required that the resulting BN has the same set of singleton attractors as the given one. We show that the problem can be solved in linear time if the number of singleton attractors is at most two and each Boolean function is restricted to be a conjunction or disjunction of literals. We also show that the problem can be solved in polynomial time if more general Boolean functions can be used. In addition to the inference problem, we study two network completion problems from a given set of singleton attractors: adding the minimum number of edges to a given network, and determining Boolean functions to all nodes when only network structure of a BN is given. In particular, we show that the latter problem cannot be solved in polynomial time unless P=NP, by means of a polynomial-time Turing reduction from the complement of the another solution problem for the Boolean satisfiability problem.
ER -
English
