Computing Weak Dominance Drawings with Minimum Number of Fips
share
A weak dominance drawing Γ of a DAG G=(V,E), is a d-dimensional drawing such that there is a directed path from a vertex u to a vertex v in G if D(u) <D(v) for every dimension D of Γ. We have a falsely implied path (fip) when D(u) < D(v) for every dimension D of Γ, but there is no path from u to v. Minimizing the number of fips is an important theoretical and practical problem, which is NP-hard. We show that it is an FPT problem for parameter k, where k is the maximum degree of a vertex of the modular decomposition tree of G. Namely, for any constant d, we present an O(nm+ndk^2(k!)^d) time algorithm to compute a weak d-dimensional dominance drawing Γ of a DAG G having the minimum number of fips. An interesting implication of this result is that we can decide if a DAG has dominance dimension 3 (a well-known NP-complete problem) in time O(nm+nk^2(k!)^3).
READ FULL TEXT