An Efficient Algorithm to Compute the Toughness in Graphs with Bounded Treewidth
Gyula Y. Katona, Humara Khan · Graphs and Combinatorics · 2024
Abstract Let t be a positive real number. A graph is called t-tough if the removal of any vertex set S that disconnects the graph leaves at most |S|/t components. The toughness of a graph is the largest t for which the graph is t-tough. We prove that toughness is fixed-parameter tractable parameterized with the treewidth. More precisely, we give an algorithm to compute the toughness of a graph G with running time $${\mathcal {O}}(|V(G)|^3\cdot \textrm{tw}(G)^{2\textrm{tw}(G)})$$ O ( | V ( G ) | 3 · tw ( G ) 2 tw ( G ) ) where $$\textrm{tw}(G)$$ tw ( G ) is the treewidth. If the treewidth is bounded by a constant, then this is a polynomial algorithm.