One-sided weak dominance drawing (Q1711831)

This paper studies the One-Sided Weak Dominance Drawing (OSWDD) problem from the perspectives of computational complexity and approximability. The authors formalize the problem, show that it is NP-hard and describe a half-approximation algorithm for a special case of the general problem. The Weak Dominance Drawing problem (WDD) is defined as follows: Given a DAG \(G\), find two topological sorts such that the intersection between them is minimized. WDD is a well-studied problem and there exist several papers in the literature that have studied aspects of this problem. The authors, though, are concerned with the variant called OSWDD. Both WDD and OSWDD are important problems and arise in a number of practical settings. The authors mention social networks, article citations, web graphs and traffic routing. Another application area would be switch-box routing in VLSI design. In short, the problems considered by the authors are of enormous practical significance. The paper is extremely well-written and the related work is comprehensive. The authors have taken great pains to flesh out every single detail. The results are easily seen to be correct. The NP-completeness result is somewhat complex, and consists of several steps, and the starting point of their reduction is the One-Sided Crossing Minimization 4-Star problem, which is not exactly a well-known problem. An interesting problem is to see if there is a simple reduction to the OSWDD problem from a standard problem such as 3SAT. The approximation algorithm developed by the authors is novel. They first establish a dimension-dependent lower bound. While the bound they provide is not useful for dimensions greater than 2, since computing the dimension is itself NP-complete, it is useful when \(d=2\), since we can check for this case in polynomial time. In this case, the authors' algorithm is a half-approximation algorithm. The authors have obtained some neat results and present them in an elegant fashion.