research-article

On the use and effect of graph decomposition in qualitative spatial and temporal reasoning

Authors:

Michael Sioutis,

Jean-François CondottaAuthors Info & Claims

SAC '15: Proceedings of the 30th Annual ACM Symposium on Applied Computing

Pages 1874 - 1879

https://doi.org/10.1145/2695664.2695831

Published: 13 April 2015 Publication History

Abstract

We survey the use and effect of decomposition-based techniques in qualitative constraint-based reasoning, and clarify the notions of a tree decomposition, a chordal graph, and a partitioning graph, and their implication with a particular constraint property that has been extensively used in literature, namely, patchwork. As a consequence, we prove that a recently proposed decomposition-based approach that was presented in [AAAI, 2014 ] for checking the satisfiability of qualitative spatial constraint networks lacks soundness. Therefore, the approach becomes quite controversial as it does not seem to offer any technical advance at all, while experimental evaluation of it in a following paper presented in [ICTAI, 2014 ] becomes questionable.

References

[1]

Allen, J. F. An Interval-Based Representation of Temporal Knowledge. In IJCAI (1981).

Digital Library

[2]

Amaneddine, N., Condotta, J., and Sioutis, M. Efficient Approach to Solve the Minimal Labeling Problem of Temporal and Spatial Qualitative Constraints. In IJCAI (2013).

Digital Library

[3]

Bhatt, M., Guesgen, H., Wölfl, S., and Hazarika, S. Qualitative Spatial and Temporal Reasoning: Emerging Applications, Trends, and Directions. Spatial Cognition & Computation 11 (2011), 1--14.

[4]

Bliek, C., and Sam-Haroud, D. Path consistency on triangulated constraint graphs. In IJCAI (1999).

Digital Library

[5]

Bodirsky, M., and Wölfl, S. RCC8 is polynomial on networks of bounded treewidth. In IJCAI (2011).

Digital Library

[6]

Chmeiss, A., and Condotta, J.-F. Consistency of Triangulated Temporal Qualitative Constraint Networks. In ICTAI (2011).

Digital Library

[7]

Condotta, J., and D'Almeida, D. Consistency of Qualitative Constraint Networks from Tree Decompositions. In TIME (2011).

Digital Library

[8]

Diestel, R. Graph Theory, 4th Edition, vol. 173. Springer, 2012.

[9]

Garey, M. R., Johnson, D. S., and Stockmeyer, L. J. Some Simplified NP-Complete Graph Problems. Theor. Comput. Sci. 1 (1976), 237--267.

[10]

Huang, J. Compactness and its implications for qualitative spatial and temporal reasoning. In KR (2012).

Digital Library

[11]

Huang, J., Li, J. J., and Renz, J. Decomposition and tractability in qualitative spatial and temporal reasoning. AI 195 (2013), 140--164.

Digital Library

[12]

Ladkin, P. B., and Maddux, R. D. On binary constraint problems. JACM 41 (1994), 435--469.

Digital Library

[13]

Li, J. J., Huang, J., and Renz, J. A divide-and-conquer approach for solving interval algebra networks. In IJCAI (2009).

Digital Library

[14]

Lutz, C., and Milicic, M. A Tableau Algorithm for DLs with Concrete Domains and GCIs. JAR 38 (2007), 227--259.

Digital Library

[15]

Montanari, U. Networks of constraints: Fundamental properties and applications to picture processing. Inf. Sci. 7 (1974), 95--132.

[16]

Nebel, B. Solving Hard Qualitative Temporal Reasoning Problems: Evaluating the Efficiency of Using the ORD-Horn Class. Constraints 1 (1997), 175--190.

[17]

Nebel, B., and Bürckert, H. Reasoning about Temporal Relations: A Maximal Tractable Subclass of Allen's Interval Algebra. JACM 42 (1995), 43--66.

Digital Library

[18]

Nikolaou, C., and Koubarakis, M. Fast Consistency Checking of Very Large Real-World RCC-8 Constraint Networks Using Graph Partitioning. In AAAI (2014).

[19]

Randell, D. A., Cui, Z., and Cohn, A. A Spatial Logic Based on Regions and Connection. In KR (1992).

[20]

Renz, J., and Ligozat, G. Weak Composition for Qualitative Spatial and Temporal Reasoning. In CP (2005).

Digital Library

[21]

Renz, J., and Nebel, B. On the Complexity of Qualitative Spatial Reasoning: A Maximal Tractable Fragment of the Region Connection Calculus. AI 108 (1999), 69--123.

Digital Library

[22]

Renz, J., and Nebel, B. Efficient Methods for Qualitative Spatial Reasoning. JAIR 15 (2001), 289--318.

Digital Library

[23]

Sioutis, M. Triangulation versus Graph Partitioning for Tackling Large Real World Qualitative Spatial Networks. In ICTAI (2014).

Digital Library

[24]

Sioutis, M., and Condotta, J.-F. Tackling Large Qualitative Spatial Networks of Scale-Free-Like Structure. In SETN (2014).

[25]

Sioutis, M., and Koubarakis, M. Consistency of Chordal RCC-8 Networks. In ICTAI (2012).

Digital Library

[26]

Sioutis, M., Salhi, Y., and Condotta, J. A Simple Decomposition Scheme For Large Real World Qualitative Constraint Networks. Université d'Artois, CRIL/CNRS, Nov. 2014.

[27]

Tarjan, R. E., and Yannakakis, M. Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs. SIAM J. Comput. 13 (1984), 566--579.

Digital Library

[28]

Westphal, M., and Hué, J. A Concise Horn Theory for RCC8. In ECAI (2014).

[29]

Westphal, M., Hué, J., and Wölfl, S. On thePropagation Strength of SAT Encodings for Qualitative Temporal Reasoning. In ICTAI (2013).

Digital Library

[30]

Yannakakis, M. Computing the Minimum Fill-In is NP-Complete. SIAM J. on Algebraic Discrete Methods 2 (1981), 77--79.

Cited By

Boukontar ACondotta JSalhi Y(2022)Knowledge Discovery from Qualitative Spatial and Temporal Data2022 IEEE 34th International Conference on Tools with Artificial Intelligence (ICTAI)10.1109/ICTAI56018.2022.00073(451-458)Online publication date: Oct-2022
https://doi.org/10.1109/ICTAI56018.2022.00073
Sioutis MSalhi YCondotta J(2016)Studying the use and effect of graph decomposition in qualitative spatial and temporal reasoningThe Knowledge Engineering Review10.1017/S026988891600014X32Online publication date: 12-Oct-2016
https://doi.org/10.1017/S026988891600014X

Index Terms

On the use and effect of graph decomposition in qualitative spatial and temporal reasoning
1. Theory of computation
  1. Logic
  2. Models of computation
    1. Computability

Recommendations

Finding a maximum-weight induced k-partite subgraph of an i-triangulated graph

An i-triangulated graph is a graph in which every odd cycle has two non-crossing chords; i-triangulated graphs form a subfamily of perfect graphs. A slightly more general family of perfect graphs are clique-separable graphs. A graph is clique-separable ...
The clique-separator graph for chordal graphs

We present a new representation of a chordal graph called the clique-separator graph, whose nodes are the maximal cliques and minimal vertex separators of the graph. We present structural properties of the clique-separator graph and additional ...
Extending assumption-based TMS for qualitative reasoning
CAIA '95: Proceedings of the 11th Conference on Artificial Intelligence for Applications

We present an extension of the HEART system developed by Joubel and Raiman (1990). This extension makes it possible to perform qualitative reasoning. HEART includes an assumption-based truth maintenance system (ATMS) and a temporal constraint propagator ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SAC '15: Proceedings of the 30th Annual ACM Symposium on Applied Computing

April 2015

2418 pages

ISBN:9781450331968

DOI:10.1145/2695664

Conference Chairs:
Roger L. Wainwright
University of Tulsa
,
Juan Manuel Corchado
University of Salamanca, Spain
,
Program Chairs:
Alessio Bechini
University of Pisa, Italy
,
Jiman Hong
Soongsil University, South Korea

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGAPP: ACM Special Interest Group on Applied Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 April 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Centre de Recherche en Informatique de Lens

Conference

SAC 2015

Sponsor:

SIGAPP

SAC 2015: Symposium on Applied Computing

April 13 - 17, 2015

Salamanca, Spain

Acceptance Rates

SAC '15 Paper Acceptance Rate 291 of 1,211 submissions, 24%;

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
70
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Boukontar ACondotta JSalhi Y(2022)Knowledge Discovery from Qualitative Spatial and Temporal Data2022 IEEE 34th International Conference on Tools with Artificial Intelligence (ICTAI)10.1109/ICTAI56018.2022.00073(451-458)Online publication date: Oct-2022
https://doi.org/10.1109/ICTAI56018.2022.00073
Sioutis MSalhi YCondotta J(2016)Studying the use and effect of graph decomposition in qualitative spatial and temporal reasoningThe Knowledge Engineering Review10.1017/S026988891600014X32Online publication date: 12-Oct-2016
https://doi.org/10.1017/S026988891600014X

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents