A fixed-parameter algorithm for dominance drawings of DAGs

A weak dominance drawing Γ of a DAG G = ( V , E ) is a d -dimensional drawing such that D ( u ) < D ( v ) for every dimension D of Γ 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 ∈ V in dimension D of Γ. If D ( u ) < D ( v ) for every dimension D of Γ, 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 m w 2 (or mw , if m w < 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.