Fully Polynomial-time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication

Matthias Bentert, Klaus Heeger, Tomohiro Koana

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 i…