title: Complexity of branch and bound for finding optimal Boolean assignment in a logic-constrained graph
body: <p>The problem:</p>
  
  <p>I have a graph in which the boolean state of each vertex is constrained by a logical relation given the states of connected vertices. The edges describe reactions, where each reaction has a set of activators (that promote it), repressors (that inhibit the reaction), and products (that can be turned on when the reaction occurs). For some of the vertices, there is a known boolean assignment of which state they should be in. My goal is to find an assignment of all the booleans in the graph that maximizes agreement with the known assignments while obeying the logical constraints of the graph.</p>
  
  <p>EDIT:
  Here is the ILP objective and the constraints I am proposing to use: <img src="https://i.stack.imgur.com/ccc6p.jpg" alt="http://i.imgur.com/kSUoVdt.jpg"></p>
  
  <p>Basically, my objective is to find an assignment of state to all species in the graph that most closely agrees with the "true" assignment of states (M), which are known from data. Not all species in the graph have a known state. </p>
  
  <p>The first constraint specifies that a reaction can only occur if all of the activating species and none of the inhibiting species are TRUE.</p>
  
  <p>The second constraint says that a species can be TRUE if one of the reactions that produces it is TRUE, or if it is specified as an input node. </p>
  
  <p>From what I've read so far, this problem is a good candidate for a B&amp;B approach. However, I am having trouble estimating what the time complexity will be for B&amp;B and for a brute force search. My guess is that a brute force search will be 2^n, where n=number of vertices, since this is the total number of nodes that would be generated by the B&amp;B tree in the worst case. But it seems like the number of constraints that have to be evaluated should also factor into the complexity for B&amp;B and brute force, but I'm not sure how.</p>