TY - JOUR
T1 - On the complexity of feedback set problems in signed digraphs
AU - Montalva, Marco
AU - Aracena, Julio
AU - Gajardo, Anahí
N1 - Funding Information:
1 This work was partially supported by FONDECYT #1061008. 2 This work was partially supported by FONDECYT #1030706. 3 Email:[email protected] 4 Email:[email protected] 5 Email:[email protected]
PY - 2008/2/20
Y1 - 2008/2/20
N2 - Given a directed graph G = (V, E) and w : E → {- 1, + 1} a sign function on the arcs of G, we study the positive feedback vertex set problem (PFVS) which consists on finding a minimum cardinality set of vertices that meets all the cycles with an even number of negative arcs. This problem is closely related with the number of steady states of Regulatory Boolean Networks. We also study the negative feedback vertex set problem which consists on finding a minimum cardinality set of vertices that meets all the cycles with an odd number of negative arcs, and the analogous problems for arc sets. We prove that all of these problems are NP-complete.
AB - Given a directed graph G = (V, E) and w : E → {- 1, + 1} a sign function on the arcs of G, we study the positive feedback vertex set problem (PFVS) which consists on finding a minimum cardinality set of vertices that meets all the cycles with an even number of negative arcs. This problem is closely related with the number of steady states of Regulatory Boolean Networks. We also study the negative feedback vertex set problem which consists on finding a minimum cardinality set of vertices that meets all the cycles with an odd number of negative arcs, and the analogous problems for arc sets. We prove that all of these problems are NP-complete.
KW - Feedback Set problems
KW - NP-complete
KW - Regulatory Boolean Networks
KW - signed digraph
UR - http://www.scopus.com/inward/record.url?scp=39149089277&partnerID=8YFLogxK
U2 - 10.1016/j.endm.2008.01.043
DO - 10.1016/j.endm.2008.01.043
M3 - Article
AN - SCOPUS:39149089277
SN - 1571-0653
VL - 30
SP - 249
EP - 254
JO - Electronic Notes in Discrete Mathematics
JF - Electronic Notes in Discrete Mathematics
IS - C
ER -