2024/03/04 by Matthias Bentert, Klaus Heeger, Bentert, Matthias +3
Computer Science · #Numerical Methods and Algorithms #Parallel Computing and Optimization Techniques #Digital Filter Design and Implementation
paper · pdf · doi:10.48550/arxiv.2403.01839
We study the computational complexity of several polynomial-time-solvable graph problems parameterized by vertex integrity, a measure of a graph's vulnerability to vertex removal in terms of connectivity. Vertex integrity is the smallest number ι such that there is a set S of ι' ≤ ι vertices such that every connected component of G-S contains at most ι-ι' vertices. It is known that the vertex integrity lies between the well-studied parameters vertex cover number and tree-depth. Alon and Yuster [ESA 2007] designed algorithms for graphs with small vertex cover number using fast matrix multiplications. We demonstrate that fast matrix multiplication can also be effectively used when parameterizing by vertex integrity ι by developing efficient algorithms for problems including an O(ιω-1n)-time algorithm for computing the girth of a graph, randomized O(ιω- 1n)-time algorithms for Maximum Matching and for finding any induced four-vertex subgraph except for a clique or an independent set, and an O(ι(ω-1)/2n2) ⊆ O(ι0.687 n2)-time algorithm for All-Pairs Shortest Paths. These algorithms can be faster than previous algorithms parameterized by tree-depth, for which fast matrix multiplication is not known to be effective.