Efficient Constructions for the Győri-Lovász Theorem on Almost Chordal Graphs
share
In the 1970s, Győri and Lovász showed that for a k-connected n-vertex graph, a given set of terminal vertices t_1, …, t_k and natural numbers n_1, …, n_k satisfying ∑_i=1^k n_i = n, a connected vertex partition S_1, …, S_k satisfying t_i ∈ S_i and |S_i| = n_i exists. However, polynomial algorithms to actually compute such partitions are known so far only for k ≤ 4. This motivates us to take a new approach and constrain this problem to particular graph classes instead of restricting the values of k. More precisely, we consider k-connected chordal graphs and a broader class of graphs related to them. For the first, we give an algorithm with O(n^2) running time that solves the problem exactly, and for the second, an algorithm with O(n^4) running time that deviates on at most one vertex from the given required vertex partition sizes.
READ FULL TEXT