On the DAG Decomposition into Minimum Number of Chains

Abstract

By the DAG decomposition, we mean the decomposition of a directed acyclic graph G into a minimized set of node-disjoint chains, which cover all the nodes of G. For any two nodes u and v on a chain, if u is above v then there is a path from u to v in G. In this paper, we discuss an efficient algorithm for this problem. Its time complexity is bounded by O(max{k, } ×n²) while the best algorithm for this problem up to now needs O(n³) time, where n is the number of the nodes of G, and k is G’s width, defined to be the size of a largest node subset U of G such that for every pair of nodes x, y Î U, there does not exist a path from x to y or from y to x. k is in general much smaller than n. In addition, by the existing algorithm, Q(n²) extra space (besides the space for G itself) is required to maintain the transitive closure of G to do the task while ours needs only O(k×n) extra space. This is particularly important for some nowadays applications with massive graphs including millions and even billions of nodes, like the facebook, twitter, and some other social networks.