On making directed graphs transitive

摘要

We present a first thorough theoretical analysis of the Transitivity Editing problem on digraphs. Herein, the task is to make a given digraph transitive by a minimum number of arc insertions or deletions. Transitivity Editing has applications in the detection of hierarchical structure in molecular characteristics of diseases. We demonstrate that if the input digraph does not contain “diamonds”, then there is an optimal solution that performs only arc deletions. This fact helps us construct a first proof of NP-hardness, which also extends to the restricted cases in which the input digraph is acyclic or has maximum degree three. By providing an O(k2)-vertex problem kernel, we answer an open question from the literature. In case of digraphs with maximum degree d, an O(k⋅d)-vertex problem kernel can be shown. Moreover, we improve previous fixed-parameter algorithms, now achieving a running time of O(2.57k+n3) for an n-vertex digraph if k arc modifications are sufficient to make it transitive. Our hardness as well as algorithmic results transfer to Transitivity Deletion, where only arc deletions are allowed.