A fixed-parameter algorithm for dominance drawings of DAGs

A weak dominance drawing Gamma of a DAG G = (V,E) is a d-dimensional drawing such that D(u) < D(v) for every dimension D of Gamma if there is a directed path from a vertex u to a vertex v in G, where D(w) is the coordinate of vertex w is an element of V in dimension D of Gamma. If D(u) < D(v) for every dimension D of Gamma, but there is no path from u to v, we have a falsely implied path (fip). Minimizing the number of fips is an important theoretical and practical problem. Computing 2-dimensional weak dominance drawings with minimum number of fips is NP-hard. We show that this problem is FPT parameterized by the dimension d and the modular width mw. A key ingredient of our proof is the Compaction Lemma, where we show an interesting property of any weak dominance drawing of G with the minimum number of fips. This FPT result in weak dominance, which is interesting by itself because the fip-minimization problem is NP-hard, is used to prove our main contributions. Computing the dominance dimension of G, that is, the minimum number of dimensions d for which G has a d-dimensional dominance drawing (a weak dominance drawing with 0 fips), is a well-known NP-hard problem. We show that the dominance dimension of G is bounded by mw/2 (or mw, if mw < 4) and that computing the dominance dimension of G is an FPT problem with parameter mw. As far as we know, this the first FPT-algorithm to compute the dominance dimension of a DAG.