Min, Max and PTIME Anti-Monotonic Overlap Graph Measures

The main contributions of this paper are: (1) We extend the anti-monotonicity results of Vanetik, Gudes and Shimony to all 24 combinations of iso-, homo-, or homeomorphism, on labeled or unlabeled, directed or undirected graphs, with edge- or vertex-overlap. (2) We show that (under reasonable assumptions) the maximum independent set measure (MIS) of Vanetik, Gudes and Shimony (2006) is the smallest anti-monotonic measure in the class of overlap-graph based frequency measures. We also introduce the new minimum clique partition measure (MCP) which represents the largest possible one. (3) In general, both theMIS and theMCP measure are NP-hard in the size of the overlap graph. We introduce the polynomial time computable Lovasz measure, which is is sandwiched between the former two, and show that is anti-monotonic.