Abstract

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. © 2008 Elsevier B.V. All rights reserved.