Top

Journal of Combinatorial Optimization

Published in:

07-11-2019

Efficient algorithms for measuring the funnel-likeness of DAGs

Authors: Marcelo Garlet Millani, Hendrik Molter, Rolf Niedermeier, Manuel Sorge

Published in: Journal of Combinatorial Optimization | Issue 1/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

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.

previous article Dynamic three-stage operating room scheduling considering patient waiting time and surgical overtime costs

next article Neighbor-distinguishing total coloring of planar graphs with maximum degree twelve

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Clearly, the problem can also be defined for general digraphs as input. In this work, however, we mainly focus on the case where the input is a DAG. Whenever results transfer to the general case we state them explicitly.

Informally, the Exponential Time Hypothesis states that there is no algorithm for 3SAT that runs in \(2^{o(n+m)}\cdot (n+m)^{O(1)}\) time, where n is the number of variables and m is the number of clauses in the formula (Impagliazzo and Paturi 2001; Impagliazzo et al. 2001).

To avoid confusion with the vertices of D, we refer to vertices of T as nodes.

Listed at https://www.archlinux.org/packages/ and obtained using pacman.

Agrawal A, Saurabh S, Sharma R, Zehavi M (2018) Kernels for deletion to classes of acyclic digraphs. J Comput Syst Sci 92:9–21MathSciNetCrossRef

Agrawal A, Saurabh S, Sharma R, Zehavi M (2018) Parameterised algorithms for deletion to classes of DAGs. Theory Comput Syst 62(8):1880–1909MathSciNetCrossRef

Ailon N, Alon N (2007) Hardness of fully dense problems. Inf Comput 205(8):1117–1129MathSciNetCrossRef

Bang-Jensen J, Gutin G (2018) Classes of directed graphs. Springer Monographs in Mathematics Springer. Springer, BerlinCrossRef

Bang-Jensen J, Gutin GZ (2009) Digraphs: theory, algorithms and applications. Springer, BerlinCrossRef

Bessy S, Fomin FV, Gaspers S, Paul C, Perez A, Saurabh S, Thomassé S (2011) Kernels for feedback arc set in tournaments. J Comput Syst Sci 77(6):1071–1078MathSciNetCrossRef

Bonsma P, Lokshtanov D (2011) Feedback vertex set in mixed graphs. In: Proceedings of the 12th international symposium on algorithms and data structures (WADS ’11), LNCS, vol 6844, pp 122–133. Springer, BerlinMATH

Cai L (2003) Parameterized complexity of vertex colouring. Discrete Appl Math 127(3):415–429MathSciNetCrossRef

Charbit P, Thomassé S, Yeo A (2007) The minimum feedback arc set problem is NP-hard for tournaments. Combin Probab Comput 16(1):1–4MathSciNetCrossRef

Chen J, Liu Y, Lu S, O’Sullivan B, Razgon I (2008) A fixed-parameter algorithm for the directed feedback vertex set problem. J ACM 55(5):21MathSciNetCrossRef

Chitnis R, Cygan M, Hajiaghayi M, Marx D (2015) Directed subset feedback vertex set is fixed-parameter tractable. ACM Trans Algorithms 11(4):28MathSciNetCrossRef

Cygan M, Fomin FV, Łukasz K, Marx DLD, Pilipczuk M, Pilipczuk M, Saurabh S (2015) Parametr Algorithms. Springer International Publishing, BerlinCrossRef

Diestel R (2016) Graph theory. Graduate texts in mathematics, vol 173, 5th edn. Springer, Belrin

Dom M, Guo J, Hüffner F, Niedermeier R, Truß A (2010) Fixed-parameter tractability results for feedback set problems in tournaments. J Discrete Algorithms 8(1):76–86MathSciNetCrossRef

Downey RG, Fellows MR (2013) Fundamentals of parameterized complexity. Texts in computer science. Springer, BerlinCrossRef

Feige U (1998) A threshold of \(\ln n\) for approximating set cover. J ACM 45(4):634–652MathSciNetCrossRef

Fortune S, Hopcroft J, Wyllie J (1980) The directed subgraph homeomorphism problem. Theor Comput Sci 10(2):111–121MathSciNetCrossRef

Ganian R, Hlinený P, Kneis J, Langer A, Obdrzálek J, Rossmanith P (2014) Digraph width measures in parameterized algorithmics. Discrete Appl Math 168:88–107MathSciNetCrossRef

Ganian R, Hlinený P, Kneis J, Meister D, Obdrzálek J, Rossmanith P, Sikdar S (2016) Are there any good digraph width measures? J Combin Theory Ser B 116:250–286MathSciNetCrossRef

Guo J, Hüffner F, Niedermeier R (2004) A structural view on parameterizing problems: distance from triviality. In: Proceedings of the 1st international workshop on parameterized and exact computation (IWPEC ’04), pp 162–173. Springer, BerlinCrossRef

Impagliazzo R, Paturi R (2001) On the complexity of \(k\)-SAT. J Comput Syst Sci 62(2):367–375MathSciNetCrossRef

Impagliazzo R, Paturi R, Zane F (2001) Which problems have strongly exponential complexity? J Comput Syst Sci 63(4):512–530MathSciNetCrossRef

Johnson T, Robertson N, Seymour PD, Thomas R (2001) Directed tree-width. J Combin Theory Ser B 82(1):138–154MathSciNetCrossRef

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

Kunegis J (2013) KONECT—The Koblenz network collection. In: Proceedings of the 22nd international world wide web conference (WWW ’13), pp 1343–1350. ACM

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

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

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

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

Millani MG (2017) Parfunn—parameters for funnels. https://gitlab.tubit.tu-berlin.de/mgmillani1/parfunn

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

Mnich M, van Leeuwen EJ (2017) Polynomial kernels for deletion to classes of acyclic digraphs. Discrete Optim 25:48–76MathSciNetCrossRef

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

van Bevern R, Bredereck R, Chopin M, Hartung S, Hüffner F, Nichterlein A, Suchý O (2017) Fixed-parameter algorithms for DAG partitioning. Discrete Appl Math 220:134–160MathSciNetCrossRef

Title: Efficient algorithms for measuring the funnel-likeness of DAGs
Authors: Marcelo Garlet Millani
Hendrik Molter
Rolf Niedermeier
Manuel Sorge
Publication date: 07-11-2019
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 1/2020
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-019-00464-4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2020

Graphs with equal domination and covering numbers

Tree-coloring problems of bounded treewidth graphs

On the extremal graphs with respect to the total reciprocal edge-eccentricity

Neighbor sum distinguishing total colorings of IC-planar graphs with maximum degree 13

Approximation algorithms for two-stage flexible flow shop scheduling

Approximation algorithm for a generalized Roman domination problem in unit ball graphs

Premium Partner