Computing Weak Dominance Drawings with Minimum Number of Fips

Abstract

A weak dominance drawing $\Gamma$ 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 $\Gamma$. We have a \emph{falsely implied path (fip)} when $D(u)<D(v)$ for every dimension $D$ of~$\Gamma$, 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 \emph{modular~decomposition~tree} of~$G$. Namely, for any constant $d$, we present an $O(nm+nd{k}^2(k!{)}^d)$ time algorithm to compute a weak $d$-dimensional dominance drawing $\Gamma$ 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+n{k}^2(k!{)}^3)$.