[Solved]: Minimal size of contracting a DAG into a new DAG

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 $vto 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 $vto 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?