Polynomial Time Algorithm for Min-Ranks of Graphs with Simple Tree Structures

摘要

The min-rank of a graph was introduced by Haemers (Algebr. Methods Graph Theory 25:267-272, 1978) to bound the Shannon capacity of a graph. This parameter of a graph has recently gained much more attention from the research community after the work of Bar-Yossef et al. (in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 197-206,2006). In their paper, it was shown that the min-rank of a graph (G) characterizes the optimal scalar linear solution of an instance of the Index Coding with Side Information (ICSI) problem described by the graph (G). It was shown by Peeters (Combinatorica 16(3):417-431, 1996) that computing the min-rank of a general graph is an NP-hard problem. There are very few known families of graphs whose min-ranks can be found in polynomial time. In this work, we introduce a new family of graphs with efficiently computed min-ranks. Specifically, we establish a polynomial time dynamic programming algorithm to compute the min-ranks of graphs having simple tree structures. Intuitively, such graphs are obtained by gluing together, in a tree-like structure, any set of graphs for which the min-ranks can be determined in polynomial time. A polynomial time algorithm to recognize such graphs is also proposed.