Optimization Problems: Expressibility, Approximation Properties and Expected Asymptotic Growth of Optimal Solutions

TitleOptimization Problems: Expressibility, Approximation Properties and Expected Asymptotic Growth of Optimal Solutions
Publication TypeTechnical Report
Year of Publication1993
AuthorsBehrendt, T., Compton K., & Grdel E.
Other Numbers790

We extend the recent approach of Papadimitrou and Yannakakis that relates the approximation properties of optimization problems to their logical representation.Our work builds on results by Kolaitis and Thakur who systematically studied the expressibility classes MS_n and MP_n of maximization problems and showed that they form a short hierarchy of four levels. The two lowest levels, MS_0 and MS_1 coincide with the classes Max Snp and Max Np of Papadimitriou and Yannakakis; they contain on ly problems that are approximable in polynomial time up to a constant factor and thus provide a logical criterion for approximability. However, there are computationally very easy maximization problems, such as Maximum Connected Component (MCC) that fail to satisfy this criterion.We modify these classes by allowing the formulae to contain predicates that are definable in least fixpoint logic. In addition, we maximize not only over relations but also over constants. We call the extended classes MSF_i and MPF_i. The proof of Papadimitriou and Yannakakis can be extended to MSF_1 to show that all problems in this class are approximable. Some problems, such as MCC, descend from the highest level in the original hierarchy to the lowest level MSF_0 in the new hierarchy. Thus our extended class MSF_1 provides a more powerful sufficient criterion for approximability than the original class MS_1.We separate the extended classes and prove that a number of important problems do not belong to MSF_1. These include Max Clique, Max Independent Set, V-C Dimension and Max Common Induced Subgraph.To do this we introduce a new method that characterizes rates of growth of aveage optimal solution sizes. For instance, it is known that the expected size of a maximal clique in a random graph grows logarithmically with respect to the cardinality of the graph. We show that no problem in MSF_1 can have this property, thus proving that Max Clique is not in MSF_1. This technique is related to limit laws for various logics and to the probabilistic method from combinatorics. We believe that this method may be of independent interest.In contrast to the recent results on the non-approximability of many maximization problems, among them Max Clique, our results do not depend on any unproved hypothesis from complexity theory, such as P does not equal NP.

Bibliographic Notes

ICSI Technical Report TR-93-002

Abbreviated Authors

T. Behrendt, K. Compton, and E. Graedel

ICSI Publication Type

Technical Report