×

Efficient algorithms for measuring the funnel-likeness of DAGs. (English) Zbl 1434.05148

Summary: We propose funnels as a new natural subclass of DAGs. Intuitively, a DAG is a funnel if every source-sink path can be uniquely identified by one of its arcs. Funnels are an analogue to trees for directed graphs, being more restrictive than DAGs but more expressive than mere in-/out-trees. Computational problems such as finding vertex-disjoint paths or tracking the origin of memes remain NP-hard on DAGs while on funnels they become solvable in polynomial time. Our main focus is the algorithmic complexity of finding out how funnel-like a given DAG is. To this end, we identify the NP-hard problem of computing the arc-deletion distance of a given DAG to a funnel. We develop efficient exact and approximation algorithms for the problem and test them on synthetic random graphs and real-world graphs.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
05C20 Directed graphs (digraphs), tournaments
68W25 Approximation algorithms

Software:

KONECT
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Agrawal, A.; Saurabh, S.; Sharma, R.; Zehavi, M., Kernels for deletion to classes of acyclic digraphs, J Comput Syst Sci, 92, 9-21 (2018) · Zbl 1380.68207
[2] Agrawal, A.; Saurabh, S.; Sharma, R.; Zehavi, M., Parameterised algorithms for deletion to classes of DAGs, Theory Comput Syst, 62, 8, 1880-1909 (2018) · Zbl 1430.68170
[3] Ailon, N.; Alon, N., Hardness of fully dense problems, Inf Comput, 205, 8, 1117-1129 (2007) · Zbl 1121.68054
[4] Bang-Jensen, J.; Gutin, G., Classes of directed graphs. Springer Monographs in Mathematics Springer (2018), Berlin: Springer, Berlin · Zbl 1398.05002
[5] Bang-Jensen, J.; Gutin, Gz, Digraphs: theory, algorithms and applications (2009), Berlin: Springer, Berlin · Zbl 1170.05002
[6] Bessy, S.; Fomin, Fv; Gaspers, S.; Paul, C.; Perez, A.; Saurabh, S.; Thomassé, S., Kernels for feedback arc set in tournaments, J Comput Syst Sci, 77, 6, 1071-1078 (2011) · Zbl 1235.05134
[7] Bonsma, Paul; Lokshtanov, Daniel, Feedback Vertex Set in Mixed Graphs, Lecture Notes in Computer Science, 122-133 (2011), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1342.05180
[8] Cai, L., Parameterized complexity of vertex colouring, Discrete Appl Math, 127, 3, 415-429 (2003) · Zbl 1015.05027
[9] Charbit, P.; Thomassé, S.; Yeo, A., The minimum feedback arc set problem is NP-hard for tournaments, Combin Probab Comput, 16, 1, 1-4 (2007) · Zbl 1120.05038
[10] Chen, J.; Liu, Y.; Lu, S.; O’Sullivan, B.; Razgon, I., A fixed-parameter algorithm for the directed feedback vertex set problem, J ACM, 55, 5, 21 (2008) · Zbl 1325.68104
[11] Chitnis, R.; Cygan, M.; Hajiaghayi, M.; Marx, D., Directed subset feedback vertex set is fixed-parameter tractable, ACM Trans Algorithms, 11, 4, 28 (2015) · Zbl 1398.68222
[12] Cygan, M.; Fomin, Fv; Łukasz, K.; Marx, Dld; Pilipczuk, M.; Pilipczuk, M.; Saurabh, S., Parametr Algorithms (2015), Berlin: Springer International Publishing, Berlin
[13] Diestel, R., Graph theory. Graduate texts in mathematics (2016), Belrin: Springer, Belrin
[14] Dom, M.; Guo, J.; Hüffner, F.; Niedermeier, R.; Truß, A., Fixed-parameter tractability results for feedback set problems in tournaments, J Discrete Algorithms, 8, 1, 76-86 (2010) · Zbl 1191.68349
[15] Downey, Rg; Fellows, Mr, Fundamentals of parameterized complexity. Texts in computer science (2013), Berlin: Springer, Berlin
[16] Feige, U., A threshold of \(\ln n\) for approximating set cover, J ACM, 45, 4, 634-652 (1998) · Zbl 1065.68573
[17] Fortune, S.; Hopcroft, J.; Wyllie, J., The directed subgraph homeomorphism problem, Theor Comput Sci, 10, 2, 111-121 (1980) · Zbl 0419.05028
[18] Ganian, R.; Hlinený, P.; Kneis, J.; Langer, A.; Obdrzálek, J.; Rossmanith, P., Digraph width measures in parameterized algorithmics, Discrete Appl Math, 168, 88-107 (2014) · Zbl 1285.05077
[19] Ganian, R.; Hlinený, P.; Kneis, J.; Meister, D.; Obdrzálek, J.; Rossmanith, P.; Sikdar, S., Are there any good digraph width measures?, J Combin Theory Ser B, 116, 250-286 (2016) · Zbl 1327.05136
[20] Guo, Jiong; Hüffner, Falk; Niedermeier, Rolf, A Structural View on Parameterizing Problems: Distance from Triviality, Parameterized and Exact Computation, 162-173 (2004), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1104.68050
[21] Impagliazzo, R.; Paturi, R., On the complexity of \(k\)-SAT, J Comput Syst Sci, 62, 2, 367-375 (2001) · Zbl 0990.68079
[22] Impagliazzo, R.; Paturi, R.; Zane, F., Which problems have strongly exponential complexity?, J Comput Syst Sci, 63, 4, 512-530 (2001) · Zbl 1006.68052
[23] Johnson, T.; Robertson, N.; Seymour, Pd; Thomas, R., Directed tree-width, J Combin Theory Ser B, 82, 1, 138-154 (2001) · Zbl 1027.05045
[24] Kenyon-Mathieu C, Schudy W (2007) How to rank with few errors. In: Proceedings of the 39th ACM symposium on theory of computing (STOC ’07), pp 95-103. ACM · Zbl 1232.68181
[25] Kunegis J (2013) KONECT—The Koblenz network collection. In: Proceedings of the 22nd international world wide web conference (WWW ’13), pp 1343-1350. ACM
[26] Lehmann J (2017) The computational complexity of worst case flows in unreliable flow networks. Bachelor thesis, Institut für Theoretische Informatik, Universität zu Lübeck
[27] Leskovec J, Backstrom L, Kleinberg J (2009) Meme-tracking and the dynamics of the news cycle. In: Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining (KDD ’09), pp 497-506. ACM
[28] Lund C, Yannakakis M (1993) The approximation of maximum subgraph problems. In: Proceedings of the 20th international colloquium on automata, languages, and programming (ICALP ’93), LNCS, vol 700, pp 40-51. Springer · Zbl 1422.68087
[29] Millani MG (2017) Funnels—algorithmic complexity of problems on special directed acyclic graphs. Master thesis, Algorithmics and computational complexity (AKT), TU Berlin. http://fpt.akt.tu-berlin.de/publications/theses/MA-marcelo-millani.pdf
[30] Millani MG (2017) Parfunn—parameters for funnels. https://gitlab.tubit.tu-berlin.de/mgmillani1/parfunn
[31] Millani MG, Molter H, Niedermeier R, Sorge M (2018) Efficient algorithms for measuring the funnel-likeness of DAGs. In: Proceedings of the 5th international symposium on combinatorial optimization (ISCO ’18), LNCS, vol 10856, pp 183-195. Springer · Zbl 1404.90133
[32] Mnich, M.; Van Leeuwen, Ej, Polynomial kernels for deletion to classes of acyclic digraphs, Discrete Optim, 25, 48-76 (2017) · Zbl 1387.68137
[33] Niedermeier R (2010) Reflections on multivariate algorithmics and problem parameterization. In: Proceedings of the 27th international symposium on theoretical aspects of computer science (STACS ’10), pp 17-32. Schloss Dagstuhl-Leibniz-Zentrum für Informatik · Zbl 1230.68096
[34] Van Bevern, R.; Bredereck, R.; Chopin, M.; Hartung, S.; Hüffner, F.; Nichterlein, A.; Suchý, O., Fixed-parameter algorithms for DAG partitioning, Discrete Appl Math, 220, 134-160 (2017) · Zbl 1355.05204
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.