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:marco@ing-mat.udec.cl 4 Email:jaracena@ing-mat.udec.cl 5 Email:anahi@ing-mat.udec.cl

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

VL - 30

SP - 249

EP - 254

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

SN - 1571-0653

IS - C

ER -