2026-07-20T14:48:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9518 2024-03-06T10:43:57Z ddc:004 open_access

Efficient and Adaptive Parameterized Algorithms on Modular Decompositions Kratsch, Stefan Nelles, Florian efficient parameterized algorithms modular-width adaptive algorithms We study the influence of a graph parameter called modular-width on the time complexity for optimally solving well-known polynomial problems such as Maximum Matching, Triangle Counting, and Maximum s-t Vertex-Capacitated Flow. The modular-width of a graph depends on its (unique) modular decomposition tree, and can be computed in linear time O(n+m) for graphs with n vertices and m edges. Modular decompositions are an important tool for graph algorithms, e.g., for linear-time recognition of certain graph classes. Throughout, we obtain efficient parameterized algorithms of running times O(f(mw)n+m), O(n+f(mw)m) , or O(f(mw)+n+m) for low polynomial functions f and graphs of modular-width mw. Our algorithm for Maximum Matching, running in time O(mw^2 log mw n+m), is both faster and simpler than the recent O(mw^4n+m) time algorithm of Coudert et al. (SODA 2018). For several other problems, e.g., Triangle Counting and Maximum b-Matching, we give adaptive algorithms, meaning that their running times match the best unparameterized algorithms for worst-case modular-width of mw=Theta(n) and they outperform them already for mw=o(n), until reaching linear time for mw=O(1). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stefan Kratsch and Florian Nelles 2018 Is Part Of LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2018.55 urn:nbn:de:0030-drops-95187 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.55 eng https://creativecommons.org/licenses/by/3.0/legalcode