2018/04/26 by Stefan Kratsch, Kratsch, Stefan, Florian Nelles +1 · 1 citation
Computer Science · #Advanced Graph Theory Research #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1804.10173
openalex publication_date 2018/04/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the influence of a graph parameter called modular-width on the time\ncomplexity for optimally solving well-known polynomial problems such as Maximum\nMatching, Triangle Counting, and Maximum s-t Vertex-Capacitated Flow. The\nmodular-width of a graph depends on its (unique) modular decomposition tree,\nand can be computed in linear time O(n+m) for graphs with n vertices and\nm edges. Modular decompositions are an important tool for graph algorithms,≠.g., for linear-time recognition of certain graph classes. Throughout, we\nobtain efficient parameterized algorithms of running times O(f(mw)n+m),\nO(n+f(mw)m) , or O(f(mw)+n+m) for graphs of modular-width mw. Our\nalgorithm for Maximum Matching, running in time O(mw2\log mw \⋅ n+m), is\nboth faster and simpler than the recent O(mw4n+m) time algorithm of Coudert\net al. (SODA 2018). For several other problems, e.g., Triangle Counting and\nMaximum b-Matching, we give adaptive algorithms, meaning that their running\ntimes match the best unparameterized algorithms for worst-case modular-width of\nmw=\Θ(n) and they outperform them already for mw=o(n), until reaching\nlinear time for mw=O(1).\n