Quotient Tree Partitioning of Undirected Graphs

Abstract

The partitioning of the vertices of an undirected graph, in a way that makes its quotient graph a tree, mirrors a way of permuting a square symmetric matrix to allow its factoring with little fil-in. We analyze the complexity of finding the best partitioning and show that it is NP-complete. We also give a new and simpler implementation of an algorithm that finds a maximal quotient tree.