15
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ So the decision problem seems to be: given a vertex-coloured DAG and an integer $k$, decide whether there is a DAG with at most $k$ vertices formed by contracting vertices with the same colour. $\endgroup$ – András Salamon Sep 23 '13 at 13:09
  • 1
    $\begingroup$ If you contract two connected nodes, do you get a forbidden self-loop? $\endgroup$ – Yuval Filmus Oct 20 '13 at 6:39
  • 1
    $\begingroup$ Nope. Read 2. again: we only add the edge if the two nodes after contraction are still different. If two nodes get contracted into one, we don't add the edge. $\endgroup$ – chx Oct 20 '13 at 7:12
  • 1
    $\begingroup$ @chx Are you asking for "minimal" or "minimum"? $\endgroup$ – Realz Slaw Oct 20 '13 at 10:42
  • 1
    $\begingroup$ can you give some motivation/bkg? $\endgroup$ – vzn Oct 24 '13 at 16:08
5
+50
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Thanks for the detailed answer! I get the restrictions and they do look reasonable. However, while I am not well versed in ILP I thought integer linear programming needed a function you wanted to maximize (or minimize) and I do not see that anywhere. I counterchecked only in Wikipedia so I might be wrong. $\endgroup$ – chx Oct 21 '13 at 6:16
  • $\begingroup$ @chx, I'm using ILP to test feasibility of the constraints. This can be done by asking the ILP solver to maximize any objective function you like (e.g., maximize 0), and then ignoring the value of the objective function and only looking to see whether the ILP is feasible or not. Either the ILP solver responds "Infeasible" (which means there's no contracted DAG of size $\le k$) or it responds "Feasible" and provides the best value of the objective function it could find; in that case you ignore the value of the objective function (and you know that there does exist a DAG of size $\le k$). $\endgroup$ – D.W. Oct 21 '13 at 6:18
  • $\begingroup$ See, e.g., engineering.purdue.edu/~engelb/abe565/… ("I just want to know whether or not a feasible solution exists.") $\endgroup$ – D.W. Oct 21 '13 at 6:21
  • $\begingroup$ Regarding your linear time solution; I have not digested your ILP formulation, so I can't judge it, but I am pretty sure I can prove the problem is NP-hard, which would make a linear time solution quite handy :P. I'm gonna post it soon. $\endgroup$ – Realz Slaw Oct 28 '13 at 8:04
  • $\begingroup$ @RealzSlaw, thank you! In that case, I strongly suspect I might have erred somewhere (though I'm not sure where just yet). $\endgroup$ – D.W. Oct 28 '13 at 12:12
5
$\begingroup$

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).

enter image description here

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:

enter image description here

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:

enter image description here

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:

enter image description here

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:

Graph sources:

$\endgroup$
  • 1
    $\begingroup$ wow. then D.W.'s solution must be wrong (or we have proven NP=P which I somewhat at least doubt :P ) -- but where? $\endgroup$ – chx Oct 28 '13 at 9:38
  • $\begingroup$ I think there's something wrong with this reduction. Consider $(x_1 \lor x_2 \lor x_6) \land (x_1 \lor x_4 \lor x_5) \land (x_3 \lor x_4 \lor x_6)$. Your reduction rules out the assignment $x_1=x_4=x_6=\text{False}$ $x_2=x_3=x_5=\text{True}$, as that would create a cycle $c_1 \to x_1 \to x_4 \to x_6 \to c_1$. However, that assignment should not be ruled out, as it satisfies the formula (it doesn't violate any of the clauses). More fundamentally, the answer lacks a proof that solutions to the DAG problem map one-to-one to satisfying assignments to the 3SAT formula. $\endgroup$ – D.W. Jun 26 '15 at 17:00
  • $\begingroup$ @D.W. Also nice to talk to you again :D, and good luck, if we are both right we might have P=NP in your answer! /jk $\endgroup$ – Realz Slaw Jun 26 '15 at 17:45
  • $\begingroup$ @D.W. unless I am misunderstanding something, your formula has to be converted into the Minimum True Monotone 3SAT problem I linked, or one of the equivalent ones, before you can apply my own reduction. A solution to my own would then have to be converted back to 3SAT. Therefore, I don't think you can just point out a formula that would fail in my own; it needs to be reduced first, then you can talk about "ruling out assignment[s]". (incidentally a minimally true solution for your formula is probably $\left(x_1, x_3\right)$ ) $\endgroup$ – Realz Slaw Jun 26 '15 at 17:49
  • $\begingroup$ @RealzSlaw, I'm afraid I don't follow yet... I don't see any reason why my formula would have to be converted. I believe it already is an instance of Minimum True Monotone 3SAT. But let me take it up a level. More broadly, I see a proposed reduction, but I don't see any argument that the reduction is correct -- that's missing. For the reduction to be correct, it has to map YES instances to YES instances, and NO instances, to NO instances. I suspect that if you try to write out a proof of correctness for your reduction, you will run into a problem when you consider the formula I gave. $\endgroup$ – D.W. Jun 26 '15 at 19:29
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I am curious too :) $\endgroup$ – chx Oct 20 '13 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.