✦ LIBER ✦

On the Query Complexity of Clique Size and Maximum Satisfiability

✍ Scribed by Richard Chang

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 682 KB
Volume: 53
Category: Article
ISSN: 0022-0000
DOI: 10.1006/jcss.1996.0070

No coin nor oath required. For personal study only.

✦ Synopsis

This paper explores the bounded query complexity of approximating the size of the maximum clique in a graph (Clique Size) and the number of simultaneously satisfiable clauses in a 3CNF formula (MaxSat). The results in the paper show that for certain approximation factors, approximating Clique Size and MaxSat are complete for corresponding bounded query classes under metric reductions. The completeness result is important because it shows that queries and approximation are interchangeable: NP queries can be used to solve NP-approximation problems and solutions to NP-approximation problems answer queries to NP oracles. Completeness also shows the existence of approximation preserving reductions from many NP-approximation problems to approximating Clique Size and MaxSat (e.g., from approximating Chromatic Number to approximating Clique Size). Since query complexity is a quantitative complexity measure, these results also provide a framework for comparing the complexities of approximating Clique Size and approximating MaxSat. In addition, this paper examines the query complexity of the minimization version of the satisfiability problem, MinUnsat, and shows that the complexity of approximating MinUnsat is very similar to the complexity of approximating Clique Size. Since MaxSat and MinUnsat share the same solution space, the ``approximability'' of MaxSat is not due to the intrinsic complexity of satisfiability, but is an artifact of viewing the approximation version of satisfiability as a maximization problem.

📜 SIMILAR VOLUMES

An upper bound on the size of a largest

An upper bound on the size of a largest clique in a graph

✍ Dennis P. Geoffroy; David P. Sumner 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 308 KB 👁 1 views

## Abstract A graph is point determining if distinct vertices have distinct neighborhoods. The nucleus of a point‐determining graph is the set __G__^O^ of all vertices, __v__, such that __G__–__v__ is point determining. In this paper we show that the size, ω(__G__), of a maximum clique in __G__ sat

Forbidden subgraphs and bounds on the si

Forbidden subgraphs and bounds on the size of a maximum matching

✍ Michael D. Plummer; Akira Saito 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB 👁 1 views

## Abstract Let __K__~1,__n__~ denote the star on __n__ + 1 vertices; that is, __K__~1,__n__~ is the complete bipartite graph having one vertex in the first vertex class of its bipartition and __n__ in the second. The special graph __K__~1,3~, called the __claw__, has received much attention in the

An algorithm for a maximum clique of the

An algorithm for a maximum clique of the intersection graph of isooriented rectangles on a cylinder

✍ Takashi Kizu; Toshiro Araki; Toshinobu Kashiwabara 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 624 KB

Effects of maximum void size and aggrega

Effects of maximum void size and aggregate characteristics on the strength of mortar

✍ L.I. Knab; J.R. Clifton; J.B. Ings 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 523 KB

The effects of the maximum void size ann aggregate shape and roughness on the flexural strength of high strength mortar were investigated. Substantial reductions in the maximum void size and air content of quartz aggregate mortars resulted in flexural strength increases. These increases in flexural

Further results on the maximum size of a

Further results on the maximum size of a hole in an incomplete t-wise balanced design with specified minimum block size

✍ I. Adamczak; D. L. Kreher; A. C. H. Ling; R. S. Rees 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 192 KB 👁 1 views

## Abstract Kreher and Rees 3 proved that if __h__ is the size of a hole in an incomplete balanced design of order υ and index λ having minimum block size $k \ge t+1$, then, They showed that when __t__ = 2 or 3, this bound is sharp infinitely often in that for each __h__ ≥ __t__ and each __k__ ≥ _

The effect of training data set size and

The effect of training data set size and the complexity of the separation function on neural network classification capability: The two-group case

✍ Moshe Leshno; Yishay Spector 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 136 KB 👁 3 views

Classification among groups is a crucial problem in managerial decision making. Classification techniques are used in: identifying stressed firms, classifying among consumer types, and rating of firms' bonds, etc. Neural networks are recognized as important and emerging methodologies in the area of