Minimal size of contracting a DAG into a new DAG

Question

We have a DAG. We have a function on the nodes $F\colon V\to \mathbb N$ (loosely speaking, we number the nodes). We would like to create a new directed graph with these rules:

1. Only nodes with the same number can be contracted into the same new node. $F(x) \neq F(y) \Rightarrow x' \neq y'$. (However, $x' \neq y'\nRightarrow F(x) \neq F(y)$.)
2. We add all the old edges between new nodes: $(x,y) \in E \land x' \neq y' \iff (x',y')\in E'$.
3. This new graph is still a DAG.

What is the minimal $|V'|$? What is an algorithm creating a minimal new graph?

Answer 1

One approach to solving this problem would be to use integer linear programming (ILP). Let's tackle the decision version of the problem: given $k$, is there a way to contract same-color vertices to get a DAG of size $\le k$?

This can be expressed as an ILP instance using standard techniques. We're given the color of each vertex in the original graph. I suggest that we label each vertex with a label in $\{1,2,\dots,k\}$; all vertices with the same label and same color will be contracted. So, the decision problem becomes: does there exist a labelling, such that contracting all same-color same-label vertices yields a DAG?

To express this as an integer linear program, introduce an integer variable $\ell_v$ for each vertex $v$, to represent the label on vertex $v$. Add the inequality $1 \le \ell_v \le k$.

The next step is to express the requirement that the contracted graph must be a DAG. Notice that if there is a labelling of the form listed above, without loss of generality there exists such a labelling where the labels induce a topological sort on the contracted graph (i.e., if $v$ precedes $w$ in the contracted graph, then $v$'s label is smaller than $w$'s label). So, for each edge $v\to w$ in the original graph, we'll add the constraint that either $v$ and $w$ have the same label and same color, or else $v$'s label is smaller than $w$'s label. Specifically, for each edge $v\to w$ in the initial graph where $v,w$ have the same color, add the inequality $\ell_v \le \ell_w$. For each edge $v \to w$ where $v,w$ have different colors, add the inequality $\ell_v < \ell_w$.

Now see if there is any feasible solution to this integer linear program. There will be a feasible solution if and only if the labelling is of the desired form (i.e., contracting all same-color same-label vertices yields a DAG). In other words, there will be a feasible solution if and only if there is a way to contract the original graph to a DAG of size $\le k$. We can use any integer linear programming solver; if the ILP solver gives us an answer, we have an answer to the original decision problem.

Of course, this isn't guaranteed to complete in polynomial time. There are no guarantees. However, ILP solvers have gotten pretty good. I would expect that, for a reasonable-sized graph, you've got a decent chance that an ILP solver might be able to solve this problem in a reasonable amount of time.

It's also possible to encode this as a SAT instance and use a SAT solver. I don't know whether that would be more effective. The ILP version is probably easier to think about, though.

(I hope this is right. I haven't checked every detail carefully, so please double-check my reasoning! I hope I haven't gone awry somewhere.)

---

Update (10/21): It looks like ILPs of this form can be solved in linear time, by processing the DAG in topologically sorted order and keeping track of the lower bound on the label for each vertex. This has me suspicious of my solution: have I made a mistake somewhere?

Answer 2

NOTE: AFAICT, D.W found a hole in this reduction and it is wrong (see comments). Keeping it here for historical reasons.

Intro: first I will reduce the Monotone 3SAT problem to our problem. Though the Monotone 3SAT problem is trivially satisfiable, our problem can further solve the Minimum True Monotone 3SAT problem, which is NP-hard; thus this problem is NP-hard.

Reduction from Monotone 3SAT to our problem

We have a monotone boolean formula expressed as a sequence of variables, and a sequence of clauses. The CNF is of the form $\Phi = (\mathcal V,\mathcal C)$ such that:

$$\forall_{\left(c_i \in \mathcal C\right)} ~ \left.c_i=\left(x_j \vee x_k \vee x_l\right) \vphantom{\LARGE | } \right|_{\left(x_j,x_k,x_l \in \mathcal V\right)}$$ and

$$\left.{\Large{\bigwedge}}_{i=1}^{n}{c_i}\right|_{\genfrac{}{}{0}{}{c_i\in \mathcal C,}{n=\left|\mathcal C\right|}}.$$

Conversion

We construct a graph, $G'=V',E'$. Each vertex in $G'$ has a label; vertices with the same label are eligible for contraction.

First we construct the graph as follows: for each $x_i \in \mathcal V$, we make two nodes, each labeled $x_i$, and a directed edge from one to the other (click images for high resolution view).

These nodes can of course be contracted, because they have the same label. We will consider variable/nodes that are contracted to be valued as false, and those that are uncontracted to be valued as true:

After this step, $V'$ should contain $2\cdot \left|\mathcal V\right|$ nodes. Next, we introduce the clause constraints. For each clause, $c_i \in \mathcal C, ~ \left.c_i = (x_j \vee x_k \vee x_l) \right|_{x_j,x_k,x_l \in \mathcal V}$, we introduce one node $c_i$, and the following edges:

^{Note the duplicatation of $c_i$ is for viewing purposes only; there is only $1$ node labeled $c_i$. (click image for full view)}

After this step, we should have $2\cdot \left|\mathcal V\right| + |\mathcal C|$ nodes.

Now, if $x_i$, $x_j$ and $x_k$ get contracted, $c_i \rightarrow c_i$ will result in a cycle.

Here is another visualization, unrolling the clause constraint:

Thus, each clause constraint requires that at least one of the variables it contains remain uncontracted; since the uncontracted nodes are valued as true, this requires that one of the variables be true; exactly what Monotone SAT requires for its clauses.

Reduction from Minimum True Monotone 3SAT

Monotone 3SAT is trivially satisfiable; you can simply set all the variables to true.

However, since our DAG minimization problem is to find the most contractions, this translates to finding the satisfying assignment that produces the most false variables in our CNF; which is the same as finding the minimum true variables. This problem is sometimes called Minimum True Monotone 3SAT or here (as an optimization problem, or decision problem), or k-True Monotone 2SAT (as a weaker decision problem); both NP-hard problems. Thus our problem is NP-hard.

---

References:

• Minimum True Monotone 3SAT
• Prove NP-completeness of deciding satisfiability of monotone boolean formula
• Monotone-2SAT and Vertex Cover

Graph sources:

• source on gist
• view on writelatex

Answer 3

With each replacement (except for direct-parent-child replacements), you add new ancestor-descendant relationships that make it non-trivial to determine which one is actually worth it in the long-term. Therefore, a simple greedy algorithm will fail in the general case. However, if you do a brute-force approach, you can determine the smallest graph:

Python-ish (not tested):

def play((V,E),F,sequence=[]):
  """
  (V,E) -- a dag.
  V     -- a set of vertices.
  E     -- a set of directed-edge-tuples.
  F     -- a function that takes a vertex, returns an integer.
  sequence -- the sequence of moved taken so far; starts with/defaults to
              an empty list, will contain tuples of the form (x,y)
              where x is removed and replaced with y.

  Returns the best recursively found solution.
  """

  #find all the integer values in the graph, remember which
  # values correspond to what vertices. Of the form {integer => {vertices}}.
  n2v = {}
  for x in V:
    n = F(x)

    #for each integer, make sure you have a set to put the vertices in.
    if n not in n2v:
      n2v[n] = set()

    #for each integer, add the vertex to the equivalent set.
    n2v[n].add(v)

  #record the best sequence/solution. You start with the current sequence,
  # and see if you can obtain anything better.
  best_solution = list(sequence)

  #Now you will try to combine a single pair of vertices, obtain a new
  # graph and then recursively play the game again from that graph. 

  #for each integer and equivalent set of vertices,
  for n,vset in n2v.iteritems():

    #pick a pair of vertices
    for x in vset:
      for y in vset:

        #no point if they are the same.
        if x == y:
          continue

        #If there is a path from x => y or y => x, then you will be
        # introducing a cycle, breaking a rule. So in that case, disregard
        # this pair.
        #However, the exception is when one is a direct child of the other;
        # in that case you can safely combine the vertices.
        if pathtest((V,E),x,y) and (x,y) not in E and (x,y) not in E:
          continue

        #combine the vertices (function is defined below), discard x,
        # replace it with y, obtain the new graph, (V',E').
        Vp,Ep = combine_vertex((V,E),x,y))

        #record the sequence for this move.
        sequencep = list(sequence) + [(x,y)]

        #recurse and play the game from this new graph.
        solution = play(Vp,Ep,F,sequencep)

        #if the returned solution is better than the current best,
        if len(solution) > len(best_solution):
          #record the new best solution
          best_solution = solution
  #return the best recorded solution
  return best_solution


def combine_vertex((V0,E0),x,y):
  """
  (V0,E0)   -- an initial digraph.
  V0        -- a set of vertices.
  E0        -- a set of directed-edge-tuples.
  x         -- vertex to discard.
  y         -- vertex to replace it with.

  returns a new digraph replacing all relationships to and from x to relate
   to y instead, and removing x from the graph entirely.
  """

  #the final vertex set will have everything except x
  V = set(V0)
  V.discard(x)

  #now you construct the edge set.
  E = set()

  #for every edge,
  for (u0,v0) in E0:
    #recreate the edge in the new graph, but replace any occurence
    # of x.  
    u,v = u0,v0
    #if x is in the edge: replace it
    if u == x:
      u = y
    if v == x:
      v == y

    #sometimes u=v=y and can now be pointing to itself, don't add that
    # edge
    if u == v:
      continue

    #add the new/replaced edge into the edge-set.
    E.add( (u,v) )
  return (V,E)

I am not sure if it really a hard problem, but playing with some graphs manually, it seems very combinatorial. I am curious if something difficult can be reduced to this problem, or if there is an algorithm with better running time.