Redundancy checking is an important task in the research of knowledge representation and reasoning. In this paper, we consider redundant qualitative constraints. For a set ? of qualitative constraints, we say a constraint ( x R y ) in ? is redundant if it is entailed by the rest of ?. A prime subnetwork of ? is a subset of ? which contains no redundant constraints and has the same solution set as ?. It is natural to ask how to compute such a prime subnetwork, and when it is unique. We show that this problem is in general intractable, but becomes tractable if ? is over a tractable subalgebra S of a qualitative calculus. Furthermore, if S is a subalgebra of the Region Connection Calculus RCC8 in which weak composition distributes over nonempty intersections, then ? has a unique prime subnetwork, which can be obtained in cubic time by removing all redundant constraints simultaneously from ?. As a by-product, we show that any path-consistent network over such a distributive subalgebra is minimal and globally consistent in a qualitative sense. A thorough empirical analysis of the prime subnetwork upon real geographical data sets demonstrates the approach is able to identify significantly more redundant constraints than previously proposed algorithms, especially in constraint networks with larger proportions of partial overlap relations.
The property of distributivity was first used by van Beek @cite_52 for IA, but the notion of distributive subalgebra is new. It is not difficult to show that PA , IA, RCC5 and RCC8 all have two maximal distributive subalgebras (see for maximal distributive subalgebras of RCC5 8). Very interestingly, the two maximal distributive subalgebras of IA are exactly the subalgebras @math and @math discussed in @cite_16 , where Amaneddine and Condotta proved that @math and @math are the only maximal subalgebras of IA over which path-consistent networks are globally consistent. For RCC8, the maximal distributive subalgebra @math we identify in turns out to be the class of convex RCC8 relations found in @cite_18 , where Chandra and Pujari proved that path-consistent networks over @math are minimal. In we find another maximal distributive subalgebra for RCC8, which contains 64 relations. Furthermore, we also show that every path-consistent constraint network @math over a distributive subalgebra is weakly globally consistent and minimal. This has not been studied for RCC5 8 before.
@cite_18 @cite_16 @cite_52
2164745460 2146146025 2532977679 50869828
The research in qualitative reasoning and in spatial CSP is always investigated in the backdrop of its temporal counterpart - qualitative temporal reasoning and TCSP. Unlike the case of interval algebra (IA), the composition table of RCC, IA's so-called spatial counterpart, is in general neither complete nor extensional, the compositional consistency can be still a valid reasoning mechanism. Even in such a restricted situation, many of the known properties of IA have not been investigated for validity in the context of RCC. We address, in this paper two such properties-convexity and minimality. The importance of minimality cannot be underestimated as in a minimal network every label is feasible and hence determining all the consistent scenarios can be accomplished very efficiently. It is known that path consistency does not yield a minimal network for tractable classes of RCC-8. We represent RCC-8 relations as a partially ordered set and exploit the properties of partial ordering to derive very interesting theoretical results. We show here that there exists a convex class of relations of RCC-8 for which path consistency yields a minimal network. Our results are very important as it gives a sufficient condition for minimality and useful to generate all consistent scenarios whenever compositional consistency is a valid reasoning mechanism In the survivable network design problem (SNDP), given an undirected graph and values r sub ij for each pair of vertices i and j, we attempt to find a minimum-cost subgraph such that there are r sub ij disjoint paths between vertices i and j. In the edge connected version of this problem (EC-SNDP), these paths must be edge-disjoint. In the vertex connected version of the problem (VC-SNDP), the paths must be vertex disjoint. K. (1999) propose a version of the problem intermediate in difficulty to these two, called the element connectivity problem (ELC-SNDP, or ELC). These variants of SNDP are all known to be NP-hard. The best known approximation algorithm for the EC-SNDP has performance guarantee of 2 (K. Jain, 2001), and iteratively rounds solutions to a linear programming relaxation of the problem. ELC has a primal-dual O (log k) approximation algorithm, where k=max sub i,j r sub ij . VC-SNDP is not known to have a non-trivial approximation algorithm; however, recently L. Fleischer (2001) has shown how to extend the technique of K. Jain ( 2001) to give a 2-approximation algorithm in the case that r sub ij spl isin 0, 1, 2 . She also shows that the same techniques will not work for VC-SNDP for more general values of r sub ij . The authors show that these techniques can be extended to a 2-approximation algorithm for ELC. This gives the first constant approximation algorithm for a general survivable network design problem which allows node failures. Given a directed graph @math and a list @math of terminal pairs, the Directed Steiner Network problem asks for a minimum-cost subgraph of @math that contains a directed @math path for every @math . The special case Directed Steiner Tree (when we ask for paths from a root @math to terminals @math ) is known to be fixed-parameter tractable parameterized by the number of terminals, while the special case Strongly Connected Steiner Subgraph (when we ask for a path from every @math to every other @math ) is known to be W[1]-hard. We systematically explore the complexity landscape of directed Steiner problems to fully understand which other special cases are FPT or W[1]-hard. Formally, if @math is a class of directed graphs, then we look at the special case of Directed Steiner Network where the list @math of requests form a directed graph that is a member of @math . Our main result is a complete characterization of the classes @math resulting in fixed-parameter tractable special cases: we show that if every pattern in @math has the combinatorial property of being "transitively equivalent to a bounded-length caterpillar with a bounded number of extra edges," then the problem is FPT, and it is W[1]-hard for every recursively enumerable @math not having this property. This complete dichotomy unifies and generalizes the known results showing that Directed Steiner Tree is FPT [Dreyfus and Wagner, Networks 1971], @math -Root Steiner Tree is FPT for constant @math [Such 'y, WG 2016], Strongly Connected Steiner Subgraph is W[1]-hard [, SIAM J. Discrete Math. 2011], and Directed Steiner Network is solvable in polynomial-time for constant number of terminals [Feldman and Ruhl, SIAM J. Comput. 2006], and moreover reveals a large continent of tractable cases that were not known before. We study in this paper the problem of global consistency for qualitative constraints networks (QCNs) of the Point Algebra (PA) and the Interval Algebra (IA). In particular, we consider the subclass @math corresponding to the set of relations of PA except the relations ,= , and the subclass @math corresponding to pointizable relations of IA one can express by means of relations of @math . We prove that path-consistency implies global consistency for QCNs defined on these subclasses. Moreover, we show that with the subclasses corresponding to convex relations, there are unique greatest subclasses of PA and IA containing singleton relations satisfying this property.