{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,18]],"date-time":"2026-06-18T11:17:04Z","timestamp":1781781424270,"version":"3.54.5"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2016,11]]},"abstract":"<jats:p>The minimum feedback arc set problem is an NP-hard problem on graphs that seeks a minimum set of arcs which, when removed from the graph, leave it acyclic. In this work, we investigate several approximations for computing a minimum feedback arc set with the goal of comparing the quality of the solutions and the running times. Our investigation is motivated by applications in Social Network Analysis such as misinformation removal and label propagation. We present careful algorithmic engineering for multiple algorithms to improve the scalability of each approach. In particular, two approaches we optimize (one greedy and one randomized) provide a nice balance between feedback arc set size and running time complexity. We experimentally compare the performance of a wide range of algorithms on a broad selection of large online networks including Twitter, LiveJournal, and the Clueweb12 dataset. The experiments reveal that our greedy and randomized implementations outperform the other approaches by simultaneously computing a feedback arc set of competitive size and scaling to web-scale graphs with billions of vertices and tens of billions of arcs. Finally, we extend the algorithms considered to the probabilistic case in which arcs are realized with some fixed probability and provide detailed experimental comparisons.<\/jats:p>","DOI":"10.14778\/3021924.3021930","type":"journal-article","created":{"date-parts":[[2017,1,24]],"date-time":"2017-01-24T15:29:41Z","timestamp":1485271781000},"page":"133-144","source":"Crossref","is-referenced-by-count":28,"title":["Efficient computation of feedback arc set at web-scale"],"prefix":"10.14778","volume":"10","author":[{"given":"Michael","family":"Simpson","sequence":"first","affiliation":[{"name":"University of Victoria, Victoria, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Venkatesh","family":"Srinivasan","sequence":"additional","affiliation":[{"name":"University of Victoria, Victoria, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alex","family":"Thomo","sequence":"additional","affiliation":[{"name":"University of Victoria, Victoria, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411513"},{"key":"e_1_2_1_2_1","volume-title":"An exact method for the min. feedback arc set problem","author":"Baharev A.","year":"2015","unstructured":"A. Baharev , H. Schichl , and A. Neumaier . An exact method for the min. feedback arc set problem , 2015 . A. Baharev, H. Schichl, and A. Neumaier. An exact method for the min. feedback arc set problem, 2015."},{"key":"e_1_2_1_3_1","volume-title":"JAIR","author":"Bar-Yehuda R.","year":"2000","unstructured":"R. Bar-Yehuda , A. Becker , and D. Geiger . Randomized algorithms for the loop cutset problem . JAIR , 2000 . R. Bar-Yehuda, A. Becker, and D. Geiger. Randomized algorithms for the loop cutset problem. JAIR, 2000."},{"key":"e_1_2_1_4_1","volume-title":"SODA '90","author":"Berger B.","year":"1990","unstructured":"B. Berger and P. W. Shor . Approximation algorithms for the maximum acyclic subgraph problem . In SODA '90 , 1990 . B. Berger and P. W. Shor. Approximation algorithms for the maximum acyclic subgraph problem. In SODA '90, 1990."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622591.1622592"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350254"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_1_8_1","volume-title":"SODA'03","author":"Bollob\u00e1s B.","year":"2003","unstructured":"B. Bollob\u00e1s , C. Borgs , J. Chayes , and O. Riordan . Directed scale-free graphs . In SODA'03 , 2003 . B. Bollob\u00e1s, C. Borgs, J. Chayes, and O. Riordan. Directed scale-free graphs. In SODA'03, 2003."},{"key":"e_1_2_1_9_1","volume-title":"Sorting heuristics for the feedback arc set problem. Technical report","author":"Brandenburg F. J.","year":"2011","unstructured":"F. J. Brandenburg and K. Hanauer . Sorting heuristics for the feedback arc set problem. Technical report , University of Passau , Germany , 2011 . F. J. Brandenburg and K. Hanauer. Sorting heuristics for the feedback arc set problem. Technical report, University of Passau, Germany, 2011."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963499"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.118"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1498698.1537601"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90079-O"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/645586.659432"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735490"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972825.40"},{"key":"e_1_2_1_17_1","volume-title":"Complexity of computer computations","author":"Karp R. M.","year":"1972","unstructured":"R. M. Karp . Reducibility among combinatorial problems. In Complexity of computer computations . Springer US , 1972 . R. M. Karp. Reducibility among combinatorial problems. In Complexity of computer computations. Springer US, 1972."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17517-6_3"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250806"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792241175"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.243"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21958"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2485212"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1241540.1241551"},{"key":"e_1_2_1_26_1","volume-title":"Machine learning: a probabilistic perspective","author":"Murphy K. P.","year":"2012","unstructured":"K. P. Murphy . Machine learning: a probabilistic perspective . MIT press , 2012 . K. P. Murphy. Machine learning: a probabilistic perspective. MIT press, 2012."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.159"},{"key":"e_1_2_1_28_1","volume-title":"Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference","author":"Pearl J.","year":"1988","unstructured":"J. Pearl . Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference . Morgan Kaufmann Publishers Inc ., 1988 . J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers Inc., 1988."},{"key":"e_1_2_1_29_1","volume-title":"CoRR","author":"Perrot K.","year":"2013","unstructured":"K. Perrot and V. T. Pham . Np-hardness of minimum feedback arc set problem on eulerian digraphs and minimum recurrent configuration problem of chip-firing game . CoRR , 2013 . K. Perrot and V. T. Pham. Np-hardness of minimum feedback arc set problem on eulerian digraphs and minimum recurrent configuration problem of chip-firing game. CoRR, 2013."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011315014322"},{"key":"e_1_2_1_31_1","volume-title":"Algorithms","author":"Sedgewick R.","year":"2011","unstructured":"R. Sedgewick and K. Wayne . Algorithms , 4 th Edition. Addison-Wesley , 2011 . R. Sedgewick and K. Wayne. Algorithms, 4th Edition. Addison-Wesley, 2011.","edition":"4"},{"key":"e_1_2_1_32_1","volume-title":"Collective classification in network data. AI magazine","author":"Sen P.","year":"2008","unstructured":"P. Sen , G. Namata , M. Bilgic , L. Getoor , B. Galligher , and T. Eliassi-Rad . Collective classification in network data. AI magazine , 2008 . P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher, and T. Eliassi-Rad. Collective classification in network data. AI magazine, 2008."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2525993"},{"key":"e_1_2_1_34_1","volume-title":"Nature","author":"Watts D. J.","year":"1998","unstructured":"D. J. Watts and S. H. Strogatz . Collective dynamics of 'small-world' networks . Nature , 1998 . D. J. Watts and S. H. Strogatz. Collective dynamics of 'small-world' networks. Nature, 1998."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3021924.3021930","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:30:28Z","timestamp":1672219828000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3021924.3021930"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,11]]}},"alternative-id":["10.14778\/3021924.3021930"],"URL":"https:\/\/doi.org\/10.14778\/3021924.3021930","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2016,11]]}}}