New results on monotone dualization and generating hypergraph transversals

ABSTRACT

This paper considers the problem of dualizing a monotone CNF (equivalently, computing all minimal transversals of a hypergraph), whose associated decision problem is a prominent open problem in NP-completeness. We present a number of new polynomial time resp. output-polynomial time results for significant cases, which largely advance the tractability frontier and improve on previous results. Furthermore, we show that duality of two monotone CNFs can be disproved with limited nondeterminism (more precisely, in polynomial time with $O(\log^2 n)$ suitably guessed bits). This result sheds new light on the complexity of this important problem.

REFERENCES

• 1: R. Beigel and B. Fu. Molecular computing, bounded nondeterminism, and efficient recursion. Algorithmica, 25: 222--238, 1999.
• 2: Jan C. Bioch , Toshihide Ibaraki, Complexity of identification and dualization of positive Boolean functions, Information and Computation, v.123 n.1, p.50-63, Nov. 15, 1995 [doi>10.1006/inco.1995.1157]
• 3: Endre Boros , Khaled M. Elbassioni , Vladimir Gurvich , Leonid Khachiyan , Kazuhisa Makino, On Generating All Minimal Integer Solutions for a Monotone System of Linear Inequalities, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.92-103, July 08-12, 2001
• 4: Endre Boros , Vladimir Gurvich , Leonid Khachiyan, Dual-Bounded Generating Problems: Partial and Multiple Transversals of a Hypergraph, SIAM Journal on Computing, v.30 n.6, p.2036-2050, 2001 [doi>10.1137/S0097539700370072]
• 5: Endre Boros , Vladimir Gurvich , Leonid Khachiyan , Kazuhisa Makino, On the Complexity of Generating Maximal Frequent and Minimal Infrequent Sets, Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, p.133-141, March 14-16, 2002
• 6: E. Boros, V. Gurvich, and P. L. Hammer. Dual subimplicants of positive Boolean functions. Optimization Methods and Software, 10: 147--156, 1998.
• 7: Endre Boros , Peter L. Hammer , Toshihide Ibaraki , Kazuhiko Kawakami, Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle, SIAM Journal on Computing, v.26 n.1, p.93-109, Feb. 1997 [doi>10.1137/S0097539793269089]
• 8: Y. Crama, Dualization of regular Boolean functions, Discrete Applied Mathematics, v.16 n.1, p.79-85, Jan. 1987 [doi>10.1016/0166-218X(87)90056-4]
• 9: C. Domingo. Private communication.
• 10: Carlos Domingo , Nina Mishra , Leonard Pitt, Efficient Read-Restricted Monotone CNF/DNF Dualization by Learning with Membership Queries, Machine Learning, v.37 n.1, p.89-110, Oct. 1999 [doi>10.1023/A:1007627028578]
• 11: Chandra Chekuri , Anand Rajaraman, Conjunctive Query Containment Revisited, Proceedings of the 6th International Conference on Database Theory, p.56-70, January 08-10, 1997
• 12: Thomas Eiter, Exact transversal hypergraphs and application to Boolean &mgr;-functions, Journal of Symbolic Computation, v.17 n.3, p.215-225, March 1994 [doi>10.1006/jsco.1994.1013]
• 13: Thomas Eiter , Georg Gottlob, Identifying the Minimal Transversals of a Hypergraph and Related Problems, SIAM Journal on Computing, v.24 n.6, p.1278-1304, Dec. 1995 [doi>10.1137/S0097539793250299]
• 14: Ronald Fagin, Degrees of acyclicity for hypergraphs and relational database schemes, Journal of the ACM (JACM), v.30 n.3, p.514-550, July 1983 [doi>10.1145/2402.322390]
• 15: Michael L. Fredman , Leonid Khachiyan, On the complexity of dualization of monotone disjunctive normal forms, Journal of Algorithms, v.21 n.3, p.618-628, Nov. 1996 [doi>10.1006/jagm.1996.0062]
• 16: Hector Garcia-Molina , Daniel Barbara, How to assign votes in a distributed system, Journal of the ACM (JACM), v.32 n.4, p.841-860, Oct. 1985 [doi>10.1145/4221.4223]
• 17: G. Gogic, C. Papadimitriou, and M. Sideri. Incremental recompilation of knowledge. Journal of Artificial Intelligence Research, 8:23--37, 1998.
• 18: Dimitrios Gunopulos , Heikki Mannila , Roni Khardon , Hannu Toivonen, Data mining, hypergraph transversals, and machine learning (extended abstract), Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.209-216, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263684]
• 19: Judy Goldsmith , Matthew A. Levy , Martin Mundhenk, Limited nondeterminism, ACM SIGACT News, v.27 n.2, p.20-29, June 1996 [doi>10.1145/235767.235769]
• 20: Georg Gottlob , Nicola Leone , Francesco Scarcello, Hypertree decompositions and tractable queries, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.21-32, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303979]
• 21: M. Graham. On the universal relation. Technical Report, University of Toronto, Canada, September 1979.
• 22: V. Gurvich. Nash-solvability of games in pure strategies. USSR Comput. (MATH) and (MATH). Phys., 15(2):357--371, 1975.
• 23: T. Ibaraki , T. Kameda, A Theory of Coteries: Mutual Exclusion in Distributed Systems, IEEE Transactions on Parallel and Distributed Systems, v.4 n.7, p.779-794, July 1993 [doi>10.1109/71.238300]
• 24: Dimitris Kavvadias , Christos H. Papadimitriou , Martha Sideri, On Horn Envelopes and Hypergraph Transversals, Proceedings of the 4th International Symposium on Algorithms and Computation, p.399-405, December 15-17, 1993
• 25: R. Khardon. Translating between Horn representations and their characteristic models. Journal of AI Research, 3:349-372, 1995.
• 26: D. S. Johnson. Open and closed problems in NP-completeness. Lecture given at the International School of (MATH)ematics "G. Stampacchia": Summer School "NP-Completeness: The First 20 Years", Erice, Italy, June 20-27, 1991.
• 27: David S. Johnson , Christos H. Papadimitriou, On generating all maximal independent sets, Information Processing Letters, v.27 n.3, p.119-123, March 25, 1988 [doi>10.1016/0020-0190(88)90065-8]
• 28: C.M.R. Kintala and P. Fischer. Refining nondeterminism in relativized polynomial-time bounded computations. SIAM J. Comput., 9:46--53, 1980.
• 29: E. Lawler, J. Lenstra, and A. Rinnooy Kan. Generating all maximal independent sets: NP-hardness and polynomial-time algorithms. SIAM J. Comput., 9:558--565, 1980.
• 30: L. Lovász. Combinatorial optimization: Some problems and trends. DIMACS Technical Report 92-53, RUTCOR, Rutgers University, 1992.
• 31: Kazuhisa Makino , Toshihide Ibaraki, The Maximum Latency and Identification of Positive Boolean Functions, SIAM Journal on Computing, v.26 n.5, p.1363-1383, Oct. 1997 [doi>10.1137/S0097539794276324]
• 32: Kazuhisa Makino , Toshihide Ibaraki, A fast and simple algorithm for identifying 2-monotonic positive Boolean functions, Journal of Algorithms, v.26 n.2, p.291-305, feb. 1998 [doi>10.1006/jagm.1997.0896]
• 33: K. Makino. Efficient dualization of O(logn)-term monotone disjunctive normal forms. Technical Report 00-07, Discrete (MATH)ematics and Systems Science, Osaka University, 2000. To appear in Discrete Applied (MATH)ematics.
• 34: Heikki Mannila , Kari-Jouko Räihä, Design by exmple: An application of Armstrong relations, Journal of Computer and System Sciences, v.33 n.2, p.126-141, Oct. 1986 [doi>10.1016/0022-0000(86)90015-2]
• 35: Nina Mishra , Leonard Pitt, Generating all maximal independent sets of bounded-degree hypergraphs, Proceedings of the tenth annual conference on Computational learning theory, p.211-217, July 06-09, 1997, Nashville, Tennessee, United States [doi>10.1145/267460.267500]
• 36: Christos H. Papadimitriou, NP-Completeness: A Retrospective, Proceedings of the 24th International Colloquium on Automata, Languages and Programming, p.2-6, July 07-11, 1997
• 37: Uri N. Peled , Bruno Simeone, An O(nm)-time algorithm for computing the dual of a regular Boolean function, Discrete Applied Mathematics, v.49 n.1-3, p.309-323, March 30, 1994 [doi>10.1016/0166-218X(94)90215-1]
• 38: K. G. Ramamurthy. Coherent Structures and Simple Games. Kluwer Academic Publishers, 1990.
• 39: R. C. Read. Every one a winner, or how to avoid isomorphism when cataloging combinatorial configurations. Annals of Discrete (MATH)ematics, 2:107--120, 1978.
• 40: R Reiter, A theory of diagnosis from first principles, Artificial Intelligence, v.32 n.1, p.57-95, April 1987 [doi>10.1016/0004-3702(87)90062-2]
• 41: N. Robertson and P. Seymour. Graph minors II: Algorithmic aspects of tree-width. J. Algorithms, 7:309--322, 1986.
• 42: Robert E. Tarjan , Mihalis Yannakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM Journal on Computing, v.13 n.3, p.566-579, August 1984 [doi>10.1137/0213035]
• 43: V D Thi, The minimal keys and antikeys, Acta Cybernetica, v.7 n.4, p.361-371, August 1986
• 44: Bjarne Toft, Colouring, stable sets and perfect graphs, Handbook of combinatorics (vol. 1), MIT Press, Cambridge, MA, 1996
• 45: R. Beigel and B. Fu. Molecular computing, bounded nondeterminism, and efficient recursion. Algorithmica, 25: 222--238, 1999.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory
          Subjects: Hypergraphs; Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
combinatorial enumeration, dualization, hypergraph acyclicity, limited nondeterminism, output-polynomial algorithms, transversal computation, treewidth