Matroid representation of clique complexes |
| |
Authors: | Kenji Kashiwabara Takeaki Uno |
| |
Affiliation: | a Department of Systems Science, Graduate School of Arts and Sciences, The University of Tokyo, 3-8-1, Komaba, Meguro, Tokyo 153-8902, Japan b Department of Information and Computer Sciences, Toyohashi University of Technology, Hibarigaoka 1-1, Tempaku, Toyohashi, Aichi 441-8580, Japan c National Institute of Informatics, 2-1-2, Hitotsubashi, Chiyoda, Tokyo 101-8430, Japan |
| |
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) which is also called a flag complex, 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. For any k>0, we characterize graphs whose clique complexes can be represented as the intersection of k matroids. As a consequence, we can see that the class of clique complexes is the same as the class of the intersections of partition matroids. Moreover, we determine how many matroids are necessary and sufficient for the representation of all graphs with n vertices. This number turns out to be n-1. Other related investigations are also given. |
| |
Keywords: | Abstract simplicial complex Clique complex Flag complex Independence system Matroid intersection Partition matroid |
本文献已被 ScienceDirect 等数据库收录! |
|