Complexity aspects of generalized Helly hypergraphs

In [V.I. Voloshin, On the upper chromatic number of a hypergraph, Australas. J. Combin. 11 (1995) 25-45], Voloshin proposed the following generalization of the Helly property. Let p?1, q?0 and s?0. A hypergraph H is (p,q)-intersecting when every partial hypergraph H^′⊆H formed by p or less hyperedges has intersection of cardinality at least q. A hypergraph H is (p,q,s)-Helly when every partial (p,q)-intersecting hypergraph H^′⊆H has intersection of cardinality at least s. In this work, we study the complexity of determining whether H is (p,q,s)-Helly.     

关联规则剪枝的运用

该文重点介绍了最新的一种关联规则后处理的方法,并且我们提出了这种方法的优化算法,能够有效去除关联规则集合中的无趣模式,并且为模式的可视化提供了良好的工具。相关实验表明该方法具有更好的模式后处理能力。     

Extracting a largest redundancy-free XML storage structure from an acyclic hypergraph in polynomial time

Given a hypergraph and a set of embedded functional dependencies, we investigate the problem of determining the conditions under which we can efficiently generate redundancy-free XML storage structures with as few scheme trees as possible. Redundancy-free XML structures guarantee both economy in storage space and the absence of update anomalies, and having the least number of scheme trees requires the fewest number of joins to navigate among the data elements. We know that the general problem is intractable. The problem may still be intractable even when the hypergraph is acyclic and each hyperedge is in Boyce–Codd normal form (BCNF). As we show here, however, given an acyclic hypergraph with each hyperedge in BCNF, a polynomial-time algorithm exists that generates a largest possible redundancy-free XML storage structure. Successively generating largest possible scheme trees from among hyperedges not already included in generated scheme trees constitutes a reasonable heuristic for finding the fewest possible scheme trees. For many practical cases, this heuristic finds the set of redundancy-free XML storage structures with the fewest number of scheme trees. In addition to a correctness proof and a complexity analysis showing that the algorithm is polynomial, we also give experimental results over randomly generated but appropriately constrained hypergraphs showing empirically that the algorithm is indeed polynomial.     

GENERAL GAME-PLAYING AND REINFORCEMENT LEARNING

This paper provides a blueprint for the development of a fully domain-independent single-agent and multiagent heuristic search system. It gives a graph-theoretic representation of search problems based on conceptual graphs and outlines two different learning systems. One, an "informed learner", makes use of the graph-theoretic definition of a search problem or game in playing and adapting to a game in the given environment. The other, a "blind learner", is not given access to the rules of a domain but must discover and then exploit the underlying mathematical structure of a given domain. Relevant work of others is referenced within the context of the blueprint.
To illustrate further how one might go about creating general game-playing agents, we show how we can generalize the understanding obtained with the Morph chess system to all games involving the interactions of abstract mathematical relations. A monitor for such domains has been developed, along with an implementation of a blind and informed learning system known as Morphll. Performance results with MorphK are preliminary but encouraging and provide a few more data points with which to understand and evaluate the blueprint.     

A graphical interpretation of dependency structures in relational data bases

The designer of a relational data base must use dependency structures of data to model semantic situations that arise in data. He must further ensure that these dependencies are not violated during operations on the data base. In this paper we study a subclass of dependencies, namely, root-dependencies and introduce a common graphical picture (S-diagram) for all of them. This effort offers a possible application of graph theory to the study of relational data bases. The S-diagram offers a pictorial insight to all the root-dependencies. We also discuss, briefly, other possible uses of our work such as automatic constraint checking and recovery of data in a damaged data base.     

An exponential lower bound on the size of algebraic decision trees for Max

We prove an exponential lower bound on the size of any fixed degree algebraic decision tree for solving MAX, the problem of finding the maximum of n real numbers. This complements the n— 1 lower bound of [Rabin (1972)] on the depth of algebraic decision trees for this problem. The proof in fact gives an exponential lower bound on the size of the polyhedral decision problem MAX= for testing whether the j-th number is the maximum among a list of n real numbers. Previously, except for linear decision trees, no nontrivial lower bounds on the size of algebraic decision trees for any familiar problems are known. We also establish an interesting connection between our lower bound and the maximum number of minimal cutsets for any rank-d hypergraph on n vertices. Received: 15 April 1996     

Improved algorithms for recognizing p-Helly and hereditary p-Helly hypergraphs

A hypergraph H is set of vertices V together with a collection of nonempty subsets of it, called the hyperedges of H. A partial hypergraph of H is a hypergraph whose hyperedges are all hyperedges of H, whereas for V^′⊆V the subhypergraph (induced by V^′) is a hypergraph with vertices V^′ and having as hyperedges the subsets obtained as nonempty intersections of V^′ and each of the hyperedges of H. For p?1 say that H is p-intersecting when every subset formed by p hyperedges of H contain a common vertex. Say that H is p-Helly when every p-intersecting partial hypergraph H^′ of H contains a vertex belonging to all the hyperedges of H^′. A hypergraph is hereditary p-Helly when every (induced) subhypergraph of it is p-Helly. In this paper we describe new characterizations for hereditary p-Helly hypergraphs and discuss the recognition problems for both p-Helly and hereditary p-Helly hypergraphs. The proposed algorithms improve the complexity of the existing recognition algorithms.     

Generating the fewest redundancy-free scheme trees from acyclic conceptual-model hypergraphs in polynomial time

Generating the fewest redundancy-free scheme trees from conceptual-model hypergraphs is NP-hard [17]. We show, however, that the problem has a polynomial-time solution if the conceptual-model hypergraph is acyclic. We define conceptual-model hypergraphs, cycles, and scheme trees, and then present a polynomial-time algorithm and show that it generates the fewest redundancy-free scheme trees. As a practical application for the algorithm, we comment on its use for the design of “good” XML schemas for data storage.     

Computing simple-path convex hulls in hypergraphs

In a connected hypergraph a vertex set X is simple-path convex (sp-convex, for short) if either |X|?1 or X contains every vertex on every simple path between two vertices in X (Faber and Jamison, 1986 [7]), and the sp-convex hull of a vertex set X is the minimal superset of X that is sp-convex. In this paper, we give a polynomial algorithm to compute sp-convex hulls in an arbitrary hypergraph.     

Easy Cases of Probabilistic Satisfiability

The Probabilistic Satisfiability problem (PSAT) can be considered as a probabilistic counterpart of the classical SAT problem. In a PSAT instance, each clause in a CNF formula is assigned a probability of being true; the problem consists in checking the consistency of the assigned probabilities. Actually, PSAT turns out to be computationally much harder than SAT, e.g., it remains difficult for some classes of formulas where SAT can be solved in polynomial time. A column generation approach has been proposed in the literature, where the pricing sub-problem reduces to a Weighted Max-SAT problem on the original formula. Here we consider some easy cases of PSAT, where it is possible to give a compact representation of the set of consistent probability assignments. We follow two different approaches, based on two different representations of CNF formulas. First we consider a representation based on directed hypergraphs. By extending a well-known integer programming formulation of SAT and Max-SAT, we solve the case in which the hypergraph does not contain cycles; a linear time algorithm is provided for this case. Then we consider the co-occurrence graph associated with a formula. We provide a solution method for the case in which the co-occurrence graph is a partial 2-tree, and we show how to extend this result to partial k-trees with k>2.