The maximum independent set problem (or its equivalent formulation, which asks for maximum cliques) is a well-known difficult combinatorial optimization problem that is frequently encountered in computer vision and pattern recognition. Recently, motivated by a linear complementarity formulation, standard pivoting operations on matrices have proven to be effective in attacking this and related problems. An intriguing connection between the maximum independent set problem and pivoting has also been recently studied by Arratia, Bollobas and Sorkin who introduced the interlace polynomial, a graph polynomial defined in terms of a new pivoting operation on undirected, unweighted graphs. Specifically, they proved that the degree of this polynomial is an upper bound on the independence number of a graph. The first contribution of this paper is to interpret their work in terms of standard matrix pivoting. We show that Arratia et al.'s pivoting operation on a graph is equivalent to a principal pivoting transform on a corresponding adjacency matrix, provided that all calculations are performed in the Galois field IF_2. We then extend Arratia et al.'s pivoting operation to fields other than IF_2, thereby allowing us to apply their polynomial to the class of gain graphs, namely bidirected edge-weighted graphs whereby reversed edges carry weights that differ only by their sign. Finally, we introduce a new graph polynomial for undirected graphs. Its recursive calculation can be done such that all ends of the recursion correspond to independent sets and its degree equals the independence number. However, the new graph polynomial is different from the independence polynomial.
展开▼
