Summary
We show that every graph on n nodes can be partitioned by a number of complete bipartite graphs with O(n 2/log n) nodes with no edge belonging to two of them. Since each partition corresponds directly to a monotone formula for the associated quadratic function we obtain an upper bound for the monotone formula size of quadratic functions. Our method extends to uniform hypergraphs with fixed range and thus to homogeneous functions with fixed length of prime implicants. Finally we give an example of a quadratic function where each monotone formula built from arbitrary partitions of the graph (double edges allowed) is not optimal. That means we disprove the single-level-conjecture for formulae.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bloniarz, P.A.: The Complexity of Monotone Boolean Functions and an Algorithm for Finding Shortest Paths in a Graph. MIT LCS TR-238 (1979)
Bollobás, B.: Extremal Graph Theory. London: Academic Press 1978
Bublitz, S.: Die monotone Formelgröße homogener Funktionen. Diplomarbeit, Universität Bielefeld, 1982
Savage, J.E.: An Algorithm for the Computation of Linear Forms. SIAM J. Comput. 3, 150–158 (1974)
Savage, J.E.: The Complexity of Computing. New York: John Wiley 1976
Vogell, T.: Das Problem von Zarankiewicz für mehrdimensionale Matrizen und Anwendung des Zarenkiewicz — Problems in der Komplexitätstheorie. Diplomarbeit, Universität Bielefeld, 1983
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Bublitz, S. Decomposition of graphs and monotone formula size of homogeneous functions. Acta Informatica 23, 689–696 (1986). https://doi.org/10.1007/BF00264314
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF00264314