Top

Published in:

2020 | OriginalPaper | Chapter

Parameterized Algorithms for Directed Modular Width

Authors : Raphael Steiner, Sebastian Wiederrecht

Published in: Algorithms and Discrete Applied Mathematics

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

Many well-known \(\mathsf {NP}\)-hard algorithmic problems on directed graphs resist efficient parameterizations with most known width measures for directed graphs, such as directed treewidth, DAG-width, Kelly-width and many others. While these focus on measuring how close a digraph is to an oriented tree resp. a directed acyclic graph, in this paper, we investigate directed modular width as a parameter, which is closer to the concept of clique-width. We investigate applications of modular decompositions of directed graphs to a wide range of algorithmic problems and derive FPT algorithms for several well-known digraph-specific \(\mathsf {NP}\)-hard problems, namely minimum (weight) directed feedback vertex set, minimum (weight) directed dominating set, digraph colouring, directed Hamiltonian path/cycle, partitioning into paths, (capacitated) vertex-disjoint directed paths, and the directed subgraph homeomorphism problem. The latter yields a polynomial-time algorithm for detecting topological minors in digraphs of bounded directed modular width. Finally we illustrate that other structural digraph parameters, such as directed pathwidth and cycle-rank can be computed efficiently using directed modular width as a parameter.

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 "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

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

previous chapter Overlaying a Hypergraph with a Graph with Bounded Maximum Degree

next chapter On the Parameterized Complexity of Spanning Trees with Small Vertex Covers

https://arxiv.org/abs/1905.13203.

Reachability in directed graphs is a simple special case of the max-flow problem and can be solved using one of the well-known polynomial algorithms for this task (see for instance [12]).

Bang-Jensen, J., Gutin, G.: Classes of Directed Graphs. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-71840-8MATHCrossRef

Bang-Jensen, J., Havet, F., Trotignon, N.: Finding an induced subdivision of a digraph. Theor. Comput. Sci. 443, 10–24 (2012)MathSciNetMATHCrossRef

Berwanger, D., Dawar, A., Hunter, P., Kreutzer, S.: DAG-width and parity games. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 524–536. Springer, Heidelberg (2006). https://doi.org/10.1007/11672142_43CrossRef

Bodlaender, H.L.: Treewidth: algorithmic techniques and results. In: Prívara, I., Ružička, P. (eds.) MFCS 1997. LNCS, vol. 1295, pp. 19–36. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0029946CrossRef

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)MathSciNetMATHCrossRef

Courcelle, B.: The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Inf. Comput. 85(1), 12–75 (1990)MathSciNetMATHCrossRef

Courcelle, B.: The expression of graph properties and graph transformations in monadic second-order logic. In: Handbook of Graph Grammars and Computing By Graph Transformation: Volume 1: Foundations, pp. 313–400. World Scientific (1997)

Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach, vol. 138. Cambridge University Press, New York (2012)MATHCrossRef

Courcelle, B., Engelfriet, J., Rozenberg, G.: Handle-rewriting hypergraph grammars. J. Comput. Syst. Sci. 46(2), 218–270 (1993)MathSciNetMATHCrossRef

10.

Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125–150 (2000)MathSciNetMATHCrossRef

11.

Cygan, M., Marx, D., Pilipczuk, M.: The planar directed k-vertex-disjoint paths problem is fixed-parameter tractable. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 197–206 (2013)

12.

Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19, 248–264 (1972)MATHCrossRef

13.

Eggan, L.C., et al.: Transition graphs and the star-height of regular events. The Mich. Math. J. 10(4), 385–397 (1963)MathSciNetMATHCrossRef

14.

Espelage, W., Gurski, F., Wanke, E.: How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time. In: Brandstädt, A., Le, V.B. (eds.) WG 2001. LNCS, vol. 2204, pp. 117–128. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45477-2_12MATHCrossRef

15.

Fellows, M.R., Lokshtanov, D., Misra, N., Rosamond, F.A., Saurabh, S.: Graph layout problems parameterized by vertex cover. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol. 5369, pp. 294–305. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-92182-0_28CrossRef

16.

Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Intractability of clique-width parameterizations. SIAM J. Comput. 39(5), 1941–1956 (2010)MathSciNetMATHCrossRef

17.

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

18.

Frank, A.: Packing paths, circuits and cuts-a survey. In: Paths, Flows, and VLSI-Layout, pp. 47–100. Springer-Verlag, Berlin (1990)

19.

Gajarský, J., Lampis, M., Ordyniak, S.: Parameterized algorithms for modular-width. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 163–176. Springer, Cham (2013). https://doi.org/10.1007/978-3-319-03898-8_15MATHCrossRef

20.

Ganian, R., et al.: Are there any good digraph width measures? J. Comb. Theory Ser. B 116, 250–286 (2016)MathSciNetMATHCrossRef

21.

Ganian, R., Hliněný, P., Kneis, J., Langer, A., Obdržálek, J., Rossmanith, P.: Digraph width measures in parameterized algorithmics. Discrete Appl. Math. 168, 88–107 (2014)MathSciNetMATHCrossRef

22.

Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1990)MATH

23.

Giannopoulou, A.C., Hunter, P., Thilikos, D.M.: Lifo-search: a min-max theorem and a searching game for cycle-rank and tree-depth. Discrete Appl. Math. 160(15), 2089–2097 (2012)MathSciNetMATHCrossRef

24.

Grohe, M., Kawarabayashi, K.I., Marx, D., Wollan, P.: Finding topological subgraphs is fixed-parameter tractable. In: Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC 2011, New York, NY, USA, pp. 479–488 (2011)

25.

Gurski, F., Komander, D., Rehs, C.: Computing digraph width measures on directed co-graphs. In: Gąsieniec, L.A., Jansson, J., Levcopoulos, C. (eds.) FCT 2019. LNCS, vol. 11651, pp. 292–305. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-25027-0_20CrossRef

26.

Hunter, P., Kreutzer, S.: Digraph measures: kelly decompositions, games, and orderings. Theor. Comput. Sci. 399(3), 206–219 (2008)MathSciNetMATHCrossRef

27.

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

28.

McConnell, R.M., Spinrad, J.P.: Modular decomposition and transitive orientation. Discrete Math. 201(1–3), 189–241 (1999)MathSciNetMATHCrossRef

29.

McConnella, R.M., de Montgolfier, F.: Linear time modular decomposition of directed graphs. Discrete Appl. Math. 145, 198–209 (2005)MathSciNetMATHCrossRef

30.

Millani, M.G., Steiner, R., Wiederrecht, S.: Colouring non-even digraphs. Technical report (2019, submitted). arXiv Preprint, arXiv:1903.02872

31.

N. Robertson, P.D.S.: An outline of a disjoint paths algorithm. In: Paths, Flows, and VLSI-Layout, pp. 267–292. Springer-Verlag, Berlin (1990)

32.

Plesník, J.: The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two. Inform. Process. Lett. 8(4), 199–201 (1979)MathSciNetMATHCrossRef

33.

Robertson, N., Seymour, P.D.: Graph minors. ii. algorithmic aspects of tree-width. J. Algorithms 7(3), 309–322 (1986)MathSciNetMATHCrossRef

Title: Parameterized Algorithms for Directed Modular Width
Authors: Raphael Steiner
Sebastian Wiederrecht
Publisher: Springer International Publishing
Book: Algorithms and Discrete Applied Mathematics
Print ISBN: 978-3-030-39218-5

Electronic ISBN: 978-3-030-39219-2

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-39219-2_33

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 "Technik"

Springer Professional "Wirtschaft"

Premium Partner