Fixed-parameter algorithms for DAG Partitioning

详细信息    查看全文

• 作者：René ; van Bevern^a ; ^b ; ^rvb@nsu.ru ; Robert Bredereck^b ; ^{robert.bredereck@tu-berlin.de} ; Morgan Chopin^c ; ^{morgan.chopin@gmail.com} ; Sepp Hartung^b ; Falk Hü ; ffner^b ; André ; Nichterlein^b ; ^{andre.nichterlein@tu-berlin.de} ; Ondřej Suchý ; ^d ; ^b ; ^{ondrej.suchy@fit.cvut.cz}
• 关键词：NP-hard problem ; Graph algorithms ; Polynomial-time data reduction ; Multiway cut ; Linear-time algorithms ; Algorithm engineering ; Evaluating heuristics
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：31 March 2017
• 年：2017
• 卷：220
• 期：Complete
• 页码：134-160
• 全文大小：797 K
• 卷排序：220

文摘

Finding the origin of short phrases propagating through the web has been formalized by Leskovec et al. (2009) as DAG Partitioning: given an arc-weighted directed acyclic graph on nn vertices and mm arcs, delete arcs with total weight at most kk such that each resulting weakly-connected component contains exactly one sink—a vertex without outgoing arcs. DAG Partitioning is NP-hard.We show an algorithm to solve DAG Partitioning in O(2k⋅(n+m))O(2k⋅(n+m)) time, that is, in linear time for fixed kk. We complement it with linear-time executable data reduction rules. Our experiments show that, in combination, they can optimally solve DAG Partitioning on simulated citation networks within five minutes for k≤190k≤190 and mm being 107107 and larger. We use our obtained optimal solutions to evaluate the solution quality of Leskovec et al.’s heuristic.We show that Leskovec et al.’s heuristic works optimally on trees and generalize this result by showing that DAG Partitioning is solvable in 2O(t2)⋅n2O(t2)⋅n time if a width-tt tree decomposition of the input graph is given. Thus, we improve an algorithm and answer an open question of Alamdari and Mehrabian (2012).We complement our algorithms by lower bounds on the running time of exact algorithms and on the effectivity of data reduction.