Complexity results for compressing optimal paths

Adi Botea, Ben Strasser, Daniel Harabor

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

In this work we give a first tractability analysis of Compressed Path Databases, space efficient oracles used to very quickly identify the first arc on a shortest path. We study the complexity of computing an optimal compressed path database for general directed and undirected graphs. We find that in both cases the problem is NP-complete. We also show that, for graphs which can be decomposed along articulation points, the problem can be decomposed into independent parts, with a corresponding reduction in its level of difficulty. In particular, this leads to simple and tractable algorithms which yield optimal compression results for trees.

Original languageEnglish
Title of host publicationProceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence and the Twenty-Seventh Innovative Applications of Artificial Intelligence Conference
Subtitle of host publication25-30 January 2015 Austin, Texas USA
EditorsBlai Bonet, Sven Koenig
Place of PublicationPalo Alto California USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages1100-1106
Number of pages7
Volume2
ISBN (Print)9781577357001
Publication statusPublished - 2015
Externally publishedYes
EventAAAI Conference on Artificial Intelligence 2015 - Hyatt Regency, Austin, United States
Duration: 25 Jan 201530 Jan 2015
Conference number: 29th
http://www.aaai.org/Conferences/AAAI/aaai14.php

Conference

ConferenceAAAI Conference on Artificial Intelligence 2015
Abbreviated titleAAAI 2015
CountryUnited States
CityAustin
Period25/01/1530/01/15
OtherCo-located with the 27th Innovative Applications of Artificial Intelligence Conference. Papers at the AAAI 2015 conference will be related here. Any papers presented at the IAAI 2015 part of the conference will be related to that event. The two conferences should have a "relation" to each other put in place to recognise that the conferences were combined into one proceedings.
Internet address

Cite this

Botea, A., Strasser, B., & Harabor, D. (2015). Complexity results for compressing optimal paths. In B. Bonet, & S. Koenig (Eds.), Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence and the Twenty-Seventh Innovative Applications of Artificial Intelligence Conference: 25-30 January 2015 Austin, Texas USA (Vol. 2, pp. 1100-1106). Palo Alto California USA: Association for the Advancement of Artificial Intelligence (AAAI).
Botea, Adi ; Strasser, Ben ; Harabor, Daniel. / Complexity results for compressing optimal paths. Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence and the Twenty-Seventh Innovative Applications of Artificial Intelligence Conference: 25-30 January 2015 Austin, Texas USA. editor / Blai Bonet ; Sven Koenig. Vol. 2 Palo Alto California USA : Association for the Advancement of Artificial Intelligence (AAAI), 2015. pp. 1100-1106
@inproceedings{c175a3a6ba6c49778a173d190cd1aa69,
title = "Complexity results for compressing optimal paths",
abstract = "In this work we give a first tractability analysis of Compressed Path Databases, space efficient oracles used to very quickly identify the first arc on a shortest path. We study the complexity of computing an optimal compressed path database for general directed and undirected graphs. We find that in both cases the problem is NP-complete. We also show that, for graphs which can be decomposed along articulation points, the problem can be decomposed into independent parts, with a corresponding reduction in its level of difficulty. In particular, this leads to simple and tractable algorithms which yield optimal compression results for trees.",
author = "Adi Botea and Ben Strasser and Daniel Harabor",
year = "2015",
language = "English",
isbn = "9781577357001",
volume = "2",
pages = "1100--1106",
editor = "Bonet, {Blai } and Koenig, {Sven }",
booktitle = "Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence and the Twenty-Seventh Innovative Applications of Artificial Intelligence Conference",
publisher = "Association for the Advancement of Artificial Intelligence (AAAI)",
address = "United States",

}

Botea, A, Strasser, B & Harabor, D 2015, Complexity results for compressing optimal paths. in B Bonet & S Koenig (eds), Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence and the Twenty-Seventh Innovative Applications of Artificial Intelligence Conference: 25-30 January 2015 Austin, Texas USA. vol. 2, Association for the Advancement of Artificial Intelligence (AAAI), Palo Alto California USA, pp. 1100-1106, AAAI Conference on Artificial Intelligence 2015, Austin, United States, 25/01/15.

Complexity results for compressing optimal paths. / Botea, Adi; Strasser, Ben; Harabor, Daniel.

Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence and the Twenty-Seventh Innovative Applications of Artificial Intelligence Conference: 25-30 January 2015 Austin, Texas USA. ed. / Blai Bonet; Sven Koenig. Vol. 2 Palo Alto California USA : Association for the Advancement of Artificial Intelligence (AAAI), 2015. p. 1100-1106.

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

TY - GEN

T1 - Complexity results for compressing optimal paths

AU - Botea, Adi

AU - Strasser, Ben

AU - Harabor, Daniel

PY - 2015

Y1 - 2015

N2 - In this work we give a first tractability analysis of Compressed Path Databases, space efficient oracles used to very quickly identify the first arc on a shortest path. We study the complexity of computing an optimal compressed path database for general directed and undirected graphs. We find that in both cases the problem is NP-complete. We also show that, for graphs which can be decomposed along articulation points, the problem can be decomposed into independent parts, with a corresponding reduction in its level of difficulty. In particular, this leads to simple and tractable algorithms which yield optimal compression results for trees.

AB - In this work we give a first tractability analysis of Compressed Path Databases, space efficient oracles used to very quickly identify the first arc on a shortest path. We study the complexity of computing an optimal compressed path database for general directed and undirected graphs. We find that in both cases the problem is NP-complete. We also show that, for graphs which can be decomposed along articulation points, the problem can be decomposed into independent parts, with a corresponding reduction in its level of difficulty. In particular, this leads to simple and tractable algorithms which yield optimal compression results for trees.

UR - http://www.scopus.com/inward/record.url?scp=84959908827&partnerID=8YFLogxK

M3 - Conference Paper

SN - 9781577357001

VL - 2

SP - 1100

EP - 1106

BT - Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence and the Twenty-Seventh Innovative Applications of Artificial Intelligence Conference

A2 - Bonet, Blai

A2 - Koenig, Sven

PB - Association for the Advancement of Artificial Intelligence (AAAI)

CY - Palo Alto California USA

ER -

Botea A, Strasser B, Harabor D. Complexity results for compressing optimal paths. In Bonet B, Koenig S, editors, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence and the Twenty-Seventh Innovative Applications of Artificial Intelligence Conference: 25-30 January 2015 Austin, Texas USA. Vol. 2. Palo Alto California USA: Association for the Advancement of Artificial Intelligence (AAAI). 2015. p. 1100-1106