Matroid representation of clique complexes

Abstract

In this paper, we approach the quality of a greedy algorithm for the maximum weighted clique problem from the viewpoint of matroid theory. More precisely, we consider the clique complex of a graph (the collection of all cliques of the graph) and investigate the minimum number k such that the clique complex of a given graph can be represented as the intersection of k matroids. This number k can be regarded as a measure of “how complex a graph is with respect to the maximum weighted clique problem” since a greedy algorithm is a k-approximation algorithm for this problem. We characterize graphs whose clique complexes can be represented as the intersection of k matroids for any k > 0. Moreover, we determine the necessary and sufficient number of matroids for the representation of all graphs with n vertices. This number turns out to be n − 1. Other related investigations are also given.