Volume
LIPIcs, Volume 248
33rd International Symposium on Algorithms and Computation (ISAAC 2022)
-
Part of:
Series:
Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC)
Event
ISAAC 2022, December 19-21, 2022, Seoul, KoreaEditors
Publication Details
- published at: 2022-12-14
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-258-7
- DBLP: db/conf/isaac/isaac2022
Access Numbers
- Detailed Access Statistics available here
-
Total Document Accesses (updated on a weekly basis):
0PDF Downloads
Documents
No documents found matching your filter selection.
Document
Complete Volume
LIPIcs, Volume 248, ISAAC 2022, Complete Volume
Abstract
LIPIcs, Volume 248, ISAAC 2022, Complete Volume
Cite as
33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 1-1080, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@Proceedings{bae_et_al:LIPIcs.ISAAC.2022,
title = {{LIPIcs, Volume 248, ISAAC 2022, Complete Volume}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {1--1080},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022},
URN = {urn:nbn:de:0030-drops-172849},
doi = {10.4230/LIPIcs.ISAAC.2022},
annote = {Keywords: LIPIcs, Volume 248, ISAAC 2022, Complete Volume}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization
Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as
33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 0:i-0:xx, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{bae_et_al:LIPIcs.ISAAC.2022.0,
author = {Bae, Sang Won and Park, Heejin},
title = {{Front Matter, Table of Contents, Preface, Conference Organization}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {0:i--0:xx},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.0},
URN = {urn:nbn:de:0030-drops-172858},
doi = {10.4230/LIPIcs.ISAAC.2022.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
Succinct Representations of Graphs (Invited Talk)
Abstract
We consider the problem of finding succinct representations of graphs, that is, encodings using asymptotically the minimum number of bits which support queries on the graphs efficiently. For a special class of graphs, there exist many theoretical results and practical implementations on ordered trees. On the other hand, for wider classes of graphs, though there are many results on counting the number of non-isomorphic graphs belonging to a graph class, there were few number of results on their succinct representations until recently.
In this talk, we review some recent results on succinct representations of graphs such as interval, permutation, circle, circular-arc, trapezoid, circle-trapezoid, k-polygon, circle-polygon, cograph, separable, ptolemaic, distance hereditary, clique width k, block, cactus, series-parallel, planar, tree width k, path, boxicity k, chordal bipartite, strongly chordal, chordal graphs, etc.
Cite as
Kunihiko Sadakane. Succinct Representations of Graphs (Invited Talk). In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{sadakane:LIPIcs.ISAAC.2022.1,
author = {Sadakane, Kunihiko},
title = {{Succinct Representations of Graphs}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {1:1--1:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.1},
URN = {urn:nbn:de:0030-drops-172865},
doi = {10.4230/LIPIcs.ISAAC.2022.1},
annote = {Keywords: Graph Enumeration, Succinct Data Structure, Compression}
}
Document
Invited Talk
The Tragedy of Being Almost but Not Quite Planar (Invited Talk)
Abstract
Planar graphs have been fertile grounds for algorithms research for decades, both because they model several types of real-world networks, and because they admit simpler and and faster algorithms than arbitrary graphs. Many important structural properties of planar graphs extend naturally to graphs that embed on more complex surfaces. As a result, efficient algorithms for planar graphs often extend naturally to higher-genus surface graphs with little or no modification.
I will describe a few of my favorite exceptions to this rule - classical problems that admit simple, efficient, and practical algorithms for planar graphs, but where algorithms for graphs on other surfaces are significantly slower and/or more complex.
Cite as
Jeff Erickson. The Tragedy of Being Almost but Not Quite Planar (Invited Talk). In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{erickson:LIPIcs.ISAAC.2022.2,
author = {Erickson, Jeff},
title = {{The Tragedy of Being Almost but Not Quite Planar}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {2:1--2:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.2},
URN = {urn:nbn:de:0030-drops-172875},
doi = {10.4230/LIPIcs.ISAAC.2022.2},
annote = {Keywords: planar graphs, surface graphs, algorithms, open problems}
}
Document
A Local Search Algorithm for the Min-Sum Submodular Cover Problem
Abstract
We consider the problem of solving the Min-Sum Submodular Cover problem using local search. The Min-Sum Submodular Cover problem generalizes the NP-complete Min-Sum Set Cover problem, replacing the input set cover instance with a monotone submodular set function. A simple greedy algorithm achieves an approximation factor of 4, which is tight unless P=NP [Streeter and Golovin, NeurIPS, 2008]. We complement the greedy algorithm with analysis of a local search algorithm. Building on work of Munagala et al. [ICDT, 2005], we show that, using simple initialization, a straightforward local search algorithm achieves a (4+ε)-approximate solution in time O(n³log(n/ε)), provided that the monotone submodular set function is also second-order supermodular. Second-order supermodularity has been shown to hold for a number of submodular functions of practical interest, including functions associated with set cover, matching, and facility location. We present experiments on two special cases of Min-Sum Submodular Cover and find that the local search algorithm can outperform the greedy algorithm on small data sets.
Cite as
Lisa Hellerstein, Thomas Lidbetter, and R. Teal Witter. A Local Search Algorithm for the Min-Sum Submodular Cover Problem. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 3:1-3:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{hellerstein_et_al:LIPIcs.ISAAC.2022.3,
author = {Hellerstein, Lisa and Lidbetter, Thomas and Witter, R. Teal},
title = {{A Local Search Algorithm for the Min-Sum Submodular Cover Problem}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {3:1--3:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.3},
URN = {urn:nbn:de:0030-drops-172880},
doi = {10.4230/LIPIcs.ISAAC.2022.3},
annote = {Keywords: Local search, submodularity, second-order supermodularity, min-sum set cover}
}
Document
Algorithms for Coloring Reconfiguration Under Recolorability Digraphs
Abstract
In the k-Recoloring problem, we are given two (vertex-)colorings of a graph using k colors, and asked to transform one into the other by recoloring only one vertex at a time, while at all times maintaining a proper k-coloring. This problem is known to be solvable in polynomial time if k ≤ 3, and is PSPACE-complete if k ≥ 4. In this paper, we consider a (directed) recolorability constraint on the k colors, which forbids some pairs of colors to be recolored directly. The recolorability constraint is given in terms of a digraph R, whose vertices correspond to the colors and whose arcs represent the pairs of colors that can be recolored directly. We provide algorithms for the problem based on the structure of recolorability constraints R, showing that the problem is solvable in linear time when R is a directed cycle or is in a class of multitrees.
Cite as
Soichiro Fujii, Yuni Iwamasa, Kei Kimura, and Akira Suzuki. Algorithms for Coloring Reconfiguration Under Recolorability Digraphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{fujii_et_al:LIPIcs.ISAAC.2022.4,
author = {Fujii, Soichiro and Iwamasa, Yuni and Kimura, Kei and Suzuki, Akira},
title = {{Algorithms for Coloring Reconfiguration Under Recolorability Digraphs}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {4:1--4:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.4},
URN = {urn:nbn:de:0030-drops-172896},
doi = {10.4230/LIPIcs.ISAAC.2022.4},
annote = {Keywords: combinatorial reconfiguration, graph coloring, recolorability, recoloring}
}
Document
Algorithms for Landmark Hub Labeling
Abstract
Landmark-based routing and Hub Labeling (HL) are shortest path planning techniques, both of which rely on storing shortest path distances between selected pairs of nodes in a preprocessing phase to accelerate query answering. In Landmark-based routing, stored distances to landmark nodes are used to obtain distance lower bounds that guide A* search from node s to node t. With HL, tight upper bounds for shortest path distances between any s-t-pair can be interfered from their stored node labels, making HL an efficient distance oracle. However, for shortest path retrieval, the oracle has to be called once per edge in said path. Furthermore, HL often suffers from a large space consumption as many node pair distances have to be stored in the labels to allow for correct query answering. In this paper, we propose a novel technique, called Landmark Hub Labeling (LHL), which integrates the landmark concept into HL. We prove better worst-case path retrieval times for LHL in case it is path-consistent (a new labeling property we introduce). Moreover, we design efficient (approximation) algorithms that produce path-consistent LHL with small label size and provide parametrized upper bounds, depending on the highway dimension h or the geodesic transversal number gt of the graph. Finally, we show that the space consumption of LHL is smaller than that of (hierarchical) HL, both in theory and in experiments on real-world road networks.
Cite as
Sabine Storandt. Algorithms for Landmark Hub Labeling. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{storandt:LIPIcs.ISAAC.2022.5,
author = {Storandt, Sabine},
title = {{Algorithms for Landmark Hub Labeling}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {5:1--5:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.5},
URN = {urn:nbn:de:0030-drops-172901},
doi = {10.4230/LIPIcs.ISAAC.2022.5},
annote = {Keywords: Hub Labeling, Landmark, Geodesic, Hitting Set, Highway Dimension}
}
Document
An Optimal Oracle Separation of Classical and Quantum Hybrid Schemes
Abstract
Recently, Chia, Chung and Lai (STOC 2020) and Coudron and Menda (STOC 2020) have shown that there exists an oracle 𝒪 such that BQP^𝒪 ≠ (BPP^BQNC)^𝒪 ∪ (BQNC^BPP)^𝒪. In fact, Chia et al. proved a stronger statement: for any depth parameter d, there exists an oracle that separates quantum depth d and 2d+1, when polynomial-time classical computation is allowed. This implies that relative to an oracle, doubling quantum depth gives classical and quantum hybrid schemes more computational power.
In this paper, we show that for any depth parameter d, there exists an oracle that separates quantum depth d and d+1, when polynomial-time classical computation is allowed. This gives an optimal oracle separation of classical and quantum hybrid schemes. To prove our result, we consider d-Bijective Shuffling Simon’s Problem (which is a variant of d-Shuffling Simon’s Problem considered by Chia et al.) and an oracle inspired by an "in-place" permutation oracle.
Cite as
Atsuya Hasegawa and François Le Gall. An Optimal Oracle Separation of Classical and Quantum Hybrid Schemes. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{hasegawa_et_al:LIPIcs.ISAAC.2022.6,
author = {Hasegawa, Atsuya and Le Gall, Fran\c{c}ois},
title = {{An Optimal Oracle Separation of Classical and Quantum Hybrid Schemes}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {6:1--6:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.6},
URN = {urn:nbn:de:0030-drops-172918},
doi = {10.4230/LIPIcs.ISAAC.2022.6},
annote = {Keywords: small-depth quantum circuit, hybrid quantum computer, oracle separation}
}
Document
Approximating the Minimum Logarithmic Arrangement Problem
Abstract
We study a graph reordering problem motivated by compressing massive graphs such as social networks and inverted indexes. Given a graph, G = (V, E), the Minimum Logarithmic Arrangement problem is to find a permutation, π, of the vertices that minimizes ∑_{(u, v) ∈ E} (1 + ⌊ lg |π(u) - π(v)| ⌋).
This objective has been shown to be a good measure of how many bits are needed to encode the graph if the adjacency list of each vertex is encoded using relative positions of two consecutive neighbors under the π order in the list rather than using absolute indices or node identifiers, which requires at least lg n bits per edge.
We show the first non-trivial approximation factor for this problem by giving a polynomial time 𝒪(log k)-approximation algorithm for graphs with treewidth k.
Cite as
Julián Mestre and Sergey Pupyrev. Approximating the Minimum Logarithmic Arrangement Problem. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{mestre_et_al:LIPIcs.ISAAC.2022.7,
author = {Mestre, Juli\'{a}n and Pupyrev, Sergey},
title = {{Approximating the Minimum Logarithmic Arrangement Problem}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {7:1--7:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.7},
URN = {urn:nbn:de:0030-drops-172924},
doi = {10.4230/LIPIcs.ISAAC.2022.7},
annote = {Keywords: approximation algorithms, graph compression}
}
Document
Bi-Criteria Approximation Algorithms for Bounded-Degree Subset TSP
Abstract
We initiate the study of the Bounded-Degree Subset Traveling Salesman problem (BDSTSP) in which we are given a graph G = (V,E) with edge cost c_e ≥ 0 on each edge e, degree bounds b_v ≥ 0 on each vertex v ∈ V and a subset of terminals X ⊆ V. The goal is to find a minimum-cost closed walk that spans all terminals and visits each vertex v ∈ V at most b_v/2 times. In this paper, we study bi-criteria approximations that find tours whose cost is within a constant-factor of the optimum tour length while violating the bounds b_v at each vertex by additive quantities.
If X = V, an adaptation of the Christofides-Serdyukov algorithm yields a (3/2, +4)-approximation, that is the tour passes through each vertex at most b_v/2+2 times (the degree of v in the multiset of edges on the tour being at most b_v + 4). This is enabled through known results in bounded-degree Steiner trees and integrality of the bounded-degree Y-join polytope. The general case X ≠ V is more challenging since we cannot pass to the metric completion on X. However, it is at least simple to get a (5/3, +4)-bicriteria approximation by using ideas similar to Hoogeveen’s TSP-Path algorithm.
Our main result is an improved approximation with marginally worse violations of the vertex bounds: a (13/8, +6)-approximation. We obtain this primarily through adapting the bounded-degree Steiner tree approximation to ensure certain "dangerous" nodes always have even degree in the resulting tree which allows us to bound the cost of the resulting degree-bounded Y-join. We also recover a (3/2, +8)-approximation for this general case.
Cite as
Zachary Friggstad and Ramin Mousavi. Bi-Criteria Approximation Algorithms for Bounded-Degree Subset TSP. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{friggstad_et_al:LIPIcs.ISAAC.2022.8,
author = {Friggstad, Zachary and Mousavi, Ramin},
title = {{Bi-Criteria Approximation Algorithms for Bounded-Degree Subset TSP}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {8:1--8:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.8},
URN = {urn:nbn:de:0030-drops-172932},
doi = {10.4230/LIPIcs.ISAAC.2022.8},
annote = {Keywords: Linear programming, approximation algorithms, combinatorial optimization}
}
Document
Budgeted Out-Tree Maximization with Submodular Prizes
Abstract
We consider a variant of the prize collecting Steiner tree problem in which we are given a directed graph D = (V,A), a monotone submodular prize function p:2^V → ℝ^+ ∪ {0}, a cost function c:V → ℤ^+, a root vertex r ∈ V, and a budget B. The aim is to find an out-subtree T of D rooted at r that costs at most B and maximizes the prize function. We call this problem Directed Rooted Submodular Tree (DRST).
For the case of undirected graphs and additive prize functions, Moss and Rabani [SIAM J. Comput. 2007] gave an algorithm that guarantees an O(log|V|)-approximation factor if a violation by a factor 2 of the budget constraint is allowed. Bateni et al. [SIAM J. Comput. 2018] improved the budget violation factor to 1+ε at the cost of an additional approximation factor of O(1/ε²), for any ε ∈ (0,1]. For directed graphs, Ghuge and Nagarajan [SODA 2020] gave an optimal quasi-polynomial time O({log n'}/{log log n'})-approximation algorithm, where n' is the number of vertices in an optimal solution, for the case in which the costs are associated to the edges.
In this paper, we give a polynomial time algorithm for DRST that guarantees an approximation factor of O(√B/ε³) at the cost of a budget violation of a factor 1+ε, for any ε ∈ (0,1]. The same result holds for the edge-cost case, to the best of our knowledge this is the first polynomial time approximation algorithm for this case. We further show that the unrooted version of DRST can be approximated to a factor of O(√B) without budget violation, which is an improvement over the factor O(Δ √B) given in [Kuo et al. IEEE/ACM Trans. Netw. 2015] for the undirected and unrooted case, where Δ is the maximum degree of the graph. Finally, we provide some new/improved approximation bounds for several related problems, including the additive-prize version of DRST, the maximum budgeted connected set cover problem, and the budgeted sensor cover problem.
Cite as
Gianlorenzo D'Angelo, Esmaeil Delfaraz, and Hugo Gilbert. Budgeted Out-Tree Maximization with Submodular Prizes. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{dangelo_et_al:LIPIcs.ISAAC.2022.9,
author = {D'Angelo, Gianlorenzo and Delfaraz, Esmaeil and Gilbert, Hugo},
title = {{Budgeted Out-Tree Maximization with Submodular Prizes}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {9:1--9:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.9},
URN = {urn:nbn:de:0030-drops-172945},
doi = {10.4230/LIPIcs.ISAAC.2022.9},
annote = {Keywords: Prize Collecting Steiner Tree, Directed graphs, Approximation Algorithms, Budgeted Problem}
}
Document
Clustering with Faulty Centers
Abstract
In this paper we introduce and formally study the problem of k-clustering with faulty centers. Specifically, we study the faulty versions of k-center, k-median, and k-means clustering, where centers have some probability of not existing, as opposed to prior work where clients had some probability of not existing. For all three problems we provide fixed parameter tractable algorithms, in the parameters k, d, and ε, that (1+ε)-approximate the minimum expected cost solutions for points in d dimensional Euclidean space. For Faulty k-center we additionally provide a 5-approximation for general metrics. Significantly, all of our algorithms have a small dependence on n. Specifically, our Faulty k-center algorithms have only linear dependence on n, while for our algorithms for Faulty k-median and Faulty k-means the dependence is still only n^(1 + o(1)).
Cite as
Kyle Fox, Hongyao Huang, and Benjamin Raichel. Clustering with Faulty Centers. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{fox_et_al:LIPIcs.ISAAC.2022.10,
author = {Fox, Kyle and Huang, Hongyao and Raichel, Benjamin},
title = {{Clustering with Faulty Centers}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {10:1--10:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.10},
URN = {urn:nbn:de:0030-drops-172950},
doi = {10.4230/LIPIcs.ISAAC.2022.10},
annote = {Keywords: clustering, approximation, probabilistic input, uncertain input}
}
Document
Combinatorial and Algorithmic Aspects of Monadic Stability
Abstract
Nowhere dense classes of graphs are classes of sparse graphs with rich structural and algorithmic properties, however, they fail to capture even simple classes of dense graphs. Monadically stable classes, originating from model theory, generalize nowhere dense classes and close them under transductions, i.e. transformations defined by colorings and simple first-order interpretations. In this work we aim to extend some combinatorial and algorithmic properties of nowhere dense classes to monadically stable classes of finite graphs. We prove the following results.
- For every monadically stable class C and fixed integer s ≥ 3, the Ramsey numbers R_C(s,t) are bounded from above by 𝒪(t^{s-1-δ}) for some δ > 0, improving the bound R(s,t) ∈ 𝒪(t^{s-1}/(log t)^{s-1}) known for the class of all graphs and the bounds known for k-stable graphs when s ≤ k.
- For every monadically stable class C and every integer r, there exists δ > 0 such that every graph G ∈ C that contains an r-subdivision of the biclique K_{t,t} as a subgraph also contains K_{t^δ,t^δ} as a subgraph. This generalizes earlier results for nowhere dense graph classes.
- We obtain a stronger regularity lemma for monadically stable classes of graphs.
- Finally, we show that we can compute polynomial kernels for the independent set and dominating set problems in powers of nowhere dense classes. Formerly, only fixed-parameter tractable algorithms were known for these problems on powers of nowhere dense classes.
Cite as
Jan Dreier, Nikolas Mählmann, Amer E. Mouawad, Sebastian Siebertz, and Alexandre Vigny. Combinatorial and Algorithmic Aspects of Monadic Stability. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{dreier_et_al:LIPIcs.ISAAC.2022.11,
author = {Dreier, Jan and M\"{a}hlmann, Nikolas and Mouawad, Amer E. and Siebertz, Sebastian and Vigny, Alexandre},
title = {{Combinatorial and Algorithmic Aspects of Monadic Stability}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {11:1--11:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.11},
URN = {urn:nbn:de:0030-drops-172961},
doi = {10.4230/LIPIcs.ISAAC.2022.11},
annote = {Keywords: Monadic Stability, Structural Graph Theory, Ramsey Numbers, Regularity, Kernels}
}
Document
Complexity and Algorithms for ISOMETRIC PATH COVER on Chordal Graphs and Beyond
Abstract
A path is isometric if it is a shortest path between its endpoints. In this article, we consider the graph covering problem Isometric Path Cover, where we want to cover all the vertices of the graph using a minimum-size set of isometric paths. Although this problem has been considered from a structural point of view (in particular, regarding applications to pursuit-evasion games), it is little studied from the algorithmic perspective. We consider Isometric Path Cover on chordal graphs, and show that the problem is NP-hard for this class. On the positive side, for chordal graphs, we design a 4-approximation algorithm and an FPT algorithm for the parameter solution size. The approximation algorithm is based on a reduction to the classic path covering problem on a suitable directed acyclic graph obtained from a breadth first search traversal of the graph. The approximation ratio of our algorithm is 3 for interval graphs and 2 for proper interval graphs. Moreover, we extend the analysis of our approximation algorithm to k-chordal graphs (graphs whose induced cycles have length at most k) by showing that it has an approximation ratio of k+7 for such graphs, and to graphs of treelength at most 𝓁, where the approximation ratio is at most 6𝓁+2.
Cite as
Dibyayan Chakraborty, Antoine Dailly, Sandip Das, Florent Foucaud, Harmender Gahlawat, and Subir Kumar Ghosh. Complexity and Algorithms for ISOMETRIC PATH COVER on Chordal Graphs and Beyond. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{chakraborty_et_al:LIPIcs.ISAAC.2022.12,
author = {Chakraborty, Dibyayan and Dailly, Antoine and Das, Sandip and Foucaud, Florent and Gahlawat, Harmender and Ghosh, Subir Kumar},
title = {{Complexity and Algorithms for ISOMETRIC PATH COVER on Chordal Graphs and Beyond}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {12:1--12:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.12},
URN = {urn:nbn:de:0030-drops-172974},
doi = {10.4230/LIPIcs.ISAAC.2022.12},
annote = {Keywords: Shortest paths, Isometric path cover, Chordal graph, Interval graph, AT-free graph, Approximation algorithm, FPT algorithm, Treewidth, Chordality, Treelength}
}
Document
Computation of Cycle Bases in Surface Embedded Graphs
Abstract
We present an O(n³ g²log g + m) + Õ(n^{ω + 1}) time deterministic algorithm to find the minimum cycle basis of a directed graph embedded on an orientable surface of genus g. This result improves upon the previous fastest known running time of O(m³n + m²n² log n) applicable to general directed graphs.
While an O(n^ω + 2^{2g}n² + m) time deterministic algorithm was known for undirected graphs, the use of the underlying field ℚ in the directed case (as opposed to ℤ₂ for the undirected case) presents extra challenges. It turns out that some of our new observations are useful for both variants of the problem, so we present an O(n^ω + n² g² log g + m) time deterministic algorithm for undirected graphs as well.
Cite as
Kyle Fox and Thomas Stanley. Computation of Cycle Bases in Surface Embedded Graphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{fox_et_al:LIPIcs.ISAAC.2022.13,
author = {Fox, Kyle and Stanley, Thomas},
title = {{Computation of Cycle Bases in Surface Embedded Graphs}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {13:1--13:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.13},
URN = {urn:nbn:de:0030-drops-172982},
doi = {10.4230/LIPIcs.ISAAC.2022.13},
annote = {Keywords: cycle basis, surface embedded graphs, homology}
}
Document
Computing Homomorphisms in Hereditary Graph Classes: The Peculiar Case of the 5-Wheel and Graphs with No Long Claws
Abstract
For graphs G and H, an H-coloring of G is an edge-preserving mapping from V(G) to V(H). In the H-Coloring problem the graph H is fixed and we ask whether an instance graph G admits an H-coloring. A generalization of this problem is H-ColoringExt, where some vertices of G are already mapped to vertices of H and we ask if this partial mapping can be extended to an H-coloring.
We study the complexity of variants of H-Coloring in F-free graphs, i.e., graphs excluding a fixed graph F as an induced subgraph. For integers a,b,c ⩾ 1, by S_{a,b,c} we denote the graph obtained by identifying one endvertex of three paths on a+1, b+1, and c+1 vertices, respectively. For odd k ⩾ 5, by W_k we denote the graph obtained from the k-cycle by adding a universal vertex.
As our main algorithmic result we show that W_5-ColoringExt is polynomial-time solvable in S_{2,1,1}-free graphs. This result exhibits an interesting non-monotonicity of H-ColoringExt with respect to taking induced subgraphs of H. Indeed, W_5 contains a triangle, and K_3-Coloring, i.e., classical 3-coloring, is NP-hard already in claw-free (i.e., S_{1,1,1}-free) graphs. Our algorithm is based on two main observations:
1) W_5-ColoringExt in S_{2,1,1}-free graphs can be in polynomial time reduced to a variant of the problem of finding an independent set intersecting all triangles, and
2) the latter problem can be solved in polynomial time in S_{2,1,1}-free graphs.
We complement this algorithmic result with several negative ones. In particular, we show that W_5-Coloring is NP-hard in P_t-free graphs for some constant t and W_5-ColoringExt is NP-hard in S_{3,3,3}-free graphs of bounded degree. This is again uncommon, as usually problems that are NP-hard in S_{a,b,c}-free graphs for some constant a,b,c are already hard in claw-free graphs
Cite as
Michał Dębski, Zbigniew Lonc, Karolina Okrasa, Marta Piecyk, and Paweł Rzążewski. Computing Homomorphisms in Hereditary Graph Classes: The Peculiar Case of the 5-Wheel and Graphs with No Long Claws. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{debski_et_al:LIPIcs.ISAAC.2022.14,
author = {D\k{e}bski, Micha{\l} and Lonc, Zbigniew and Okrasa, Karolina and Piecyk, Marta and Rz\k{a}\.{z}ewski, Pawe{\l}},
title = {{Computing Homomorphisms in Hereditary Graph Classes: The Peculiar Case of the 5-Wheel and Graphs with No Long Claws}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {14:1--14:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.14},
URN = {urn:nbn:de:0030-drops-172996},
doi = {10.4230/LIPIcs.ISAAC.2022.14},
annote = {Keywords: graph homomorphism, forbidden induced subgraphs, precoloring extension}
}
Document
Computing Palindromes on a Trie in Linear Time
Abstract
A trie 𝒯 is a rooted tree such that each edge is labeled by a single character from the alphabet, and the labels of out-going edges from the same node are mutually distinct. Given a trie 𝒯 with n edges, we show how to compute all distinct palindromes and all maximal palindromes on 𝒯 in O(n) time, in the case of integer alphabets of size polynomial in n. This improves the state-of-the-art O(n log h)-time algorithms by Funakoshi et al. [PSC 2019], where h is the height of 𝒯. Using our new algorithms, the eertree with suffix links for a given trie 𝒯 can readily be obtained in O(n) time. Further, our trie-based O(n)-space data structure allows us to report all distinct palindromes and maximal palindromes in a query string represented in the trie 𝒯, in output optimal time. This is an improvement over an existing (naïve) solution that precomputes and stores all distinct palindromes and maximal palindromes for each and every string in the trie 𝒯 separately, using a total O(n²) preprocessing time and space, and reports them in output optimal time upon query.
Cite as
Takuya Mieno, Mitsuru Funakoshi, and Shunsuke Inenaga. Computing Palindromes on a Trie in Linear Time. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{mieno_et_al:LIPIcs.ISAAC.2022.15,
author = {Mieno, Takuya and Funakoshi, Mitsuru and Inenaga, Shunsuke},
title = {{Computing Palindromes on a Trie in Linear Time}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {15:1--15:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.15},
URN = {urn:nbn:de:0030-drops-173006},
doi = {10.4230/LIPIcs.ISAAC.2022.15},
annote = {Keywords: palindromes, suffix trees, tries, labeled trees, eertrees}
}
Document
Distortion-Oblivious Algorithms for Scheduling on Multiple Machines
Abstract
We consider the classic online problem of scheduling on multiple machines to minimize total flow time and total stretch where the input consists of estimates on the processing time provided for each job once released. The performance of such algorithms should depend on μ, the error in the estimates of the processing time for that instance (such an algorithm is called a distortion oblivious algorithm). Previously, a distortion oblivious algorithm to minimize flow time was provided only for a single machine. In this paper we extend the work to multiple machines and also consider the total stretch objective. In particular, we design a non-migrative distortion oblivious algorithm to minimize total flow time with a competitive ratio of O(μ log P), where P is the ratio between the maximum to minimum processing time. We show that with immediate-dispatching one cannot achieve a competitive ratio which is a function of μ and P; moreover, a competitive ratio which is sub-polynomial in the number of jobs is also impossible. We also present the first distortion-oblivious algorithm for minimizing the stretch time, both on a single and on multiple machines. The competitive ratio of these algorithms are O(μ²) which is optimal as we also prove a matching Ω(μ²) lower bound.
Cite as
Yossi Azar, Eldad Peretz, and Noam Touitou. Distortion-Oblivious Algorithms for Scheduling on Multiple Machines. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{azar_et_al:LIPIcs.ISAAC.2022.16,
author = {Azar, Yossi and Peretz, Eldad and Touitou, Noam},
title = {{Distortion-Oblivious Algorithms for Scheduling on Multiple Machines}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {16:1--16:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.16},
URN = {urn:nbn:de:0030-drops-173010},
doi = {10.4230/LIPIcs.ISAAC.2022.16},
annote = {Keywords: Online, Scheduling, Predictions, Stretch, Flow Time}
}
Document
Efficiently Reconfiguring a Connected Swarm of Labeled Robots
Abstract
When considering motion planning for a swarm of n labeled robots, we need to rearrange a given start configuration into a desired target configuration via a sequence of parallel, continuous, collision-free robot motions. The objective is to reach the new configuration in a minimum amount of time; an important constraint is to keep the swarm connected at all times. Problems of this type have been considered before, with recent notable results achieving constant stretch for not necessarily connected reconfiguration: If mapping the start configuration to the target configuration requires a maximum Manhattan distance of d, the total duration of an overall schedule can be bounded to 𝒪(d), which is optimal up to constant factors. However, constant stretch could only be achieved if disconnected reconfiguration is allowed, or for scaled configurations (which arise by increasing all dimensions of a given object by the same multiplicative factor) of unlabeled robots.
We resolve these major open problems by (1) establishing a lower bound of Ω(√n) for connected, labeled reconfiguration and, most importantly, by (2) proving that for scaled arrangements, constant stretch for connected reconfiguration can be achieved. In addition, we show that (3) it is NP-hard to decide whether a makespan of 2 can be achieved, while it is possible to check in polynomial time whether a makespan of 1 can be achieved.
Cite as
Sándor P. Fekete, Peter Kramer, Christian Rieck, Christian Scheffer, and Arne Schmidt. Efficiently Reconfiguring a Connected Swarm of Labeled Robots. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{fekete_et_al:LIPIcs.ISAAC.2022.17,
author = {Fekete, S\'{a}ndor P. and Kramer, Peter and Rieck, Christian and Scheffer, Christian and Schmidt, Arne},
title = {{Efficiently Reconfiguring a Connected Swarm of Labeled Robots}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {17:1--17:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.17},
URN = {urn:nbn:de:0030-drops-173028},
doi = {10.4230/LIPIcs.ISAAC.2022.17},
annote = {Keywords: Motion planning, parallel motion, bounded stretch, makespan, connectivity, swarm robotics}
}
Document
Entropy Matters: Understanding Performance of Sparse Random Embeddings
Abstract
This work shows how the performance of sparse random embeddings depends on the Renyi entropy-like property of data, improving upon recent works from NIPS'18 and NIPS'19.
While the prior works relied on involved combinatorics, the novel approach is simpler and modular. As the building blocks, it develops the following probabilistic facts of general interest:
b) a comparison inequality between the linear and quadratic chaos
c) a comparison inequality between heterogenic and homogenic linear chaos
d) a simpler proof of Latala’s strong result on estimating distributions of IID sums
e) sharp bounds for binomial moments in all parameter regimes.
Cite as
Maciej Skorski. Entropy Matters: Understanding Performance of Sparse Random Embeddings. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{skorski:LIPIcs.ISAAC.2022.18,
author = {Skorski, Maciej},
title = {{Entropy Matters: Understanding Performance of Sparse Random Embeddings}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {18:1--18:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.18},
URN = {urn:nbn:de:0030-drops-173037},
doi = {10.4230/LIPIcs.ISAAC.2022.18},
annote = {Keywords: Random Embeddings, Sparse Projections, Renyi Entropy}
}
Document
Evacuation from a Disk for Robots with Asymmetric Communication
Abstract
We consider evacuation of two robots from an Exit placed at an unknown location on the perimeter of a unit (radius) disk. The robots can move with max speed 1 and start at the center of the disk at the same time. We consider a new communication model, known as the SR model, in which the robots have communication faults as follows: one of the robots is a Sender and can only send wirelessly at any distance, while the other is a Receiver in that it can only receive wirelessly from any distance. The communication status of each robot is known to the other robot. In addition, both robots can exchange messages when they are co-located, which is known as Face-to-Face (F2F) model.
There have been several studies in the literature concerning the evacuation time when both robots may employ either F2F or Wireless (WiFi) communication. The SR communication model diverges from these two in that the two robots themselves have differing communication capabilities. We study the evacuation time, namely the time it takes until the last robot reaches the Exit, and show that the evacuation time in the SR model is strictly between the F2F and the WiFi models. The main part of our technical contribution is also an evacuation algorithm in which two cooperating robots accomplish the task in worst-case time at most π+2. Interesting features of the proposed algorithm are the asymmetry inherent in the resulting trajectories, as well as that the robots do not move at full speed for the entire duration of their trajectories.
Cite as
Konstantinos Georgiou, Nikos Giachoudis, and Evangelos Kranakis. Evacuation from a Disk for Robots with Asymmetric Communication. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{georgiou_et_al:LIPIcs.ISAAC.2022.19,
author = {Georgiou, Konstantinos and Giachoudis, Nikos and Kranakis, Evangelos},
title = {{Evacuation from a Disk for Robots with Asymmetric Communication}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {19:1--19:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.19},
URN = {urn:nbn:de:0030-drops-173047},
doi = {10.4230/LIPIcs.ISAAC.2022.19},
annote = {Keywords: Communication, Cycle, Evacuation, Receiver, Sender, Mobile Agents}
}
Document
Extended MSO Model Checking via Small Vertex Integrity
Abstract
We study the model checking problem of an extended MSO with local and global cardinality constraints, called MSO^GL_Lin, introduced recently by Knop, Koutecký, Masařík, and Toufar [Log. Methods Comput. Sci., 15(4), 2019]. We show that the problem is fixed-parameter tractable parameterized by vertex integrity, where vertex integrity is a graph parameter standing between vertex cover number and treedepth. Our result thus narrows the gap between the fixed-parameter tractability parameterized by vertex cover number and the W[1]-hardness parameterized by treedepth.
Cite as
Tatsuya Gima and Yota Otachi. Extended MSO Model Checking via Small Vertex Integrity. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 20:1-20:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{gima_et_al:LIPIcs.ISAAC.2022.20,
author = {Gima, Tatsuya and Otachi, Yota},
title = {{Extended MSO Model Checking via Small Vertex Integrity}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {20:1--20:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.20},
URN = {urn:nbn:de:0030-drops-173056},
doi = {10.4230/LIPIcs.ISAAC.2022.20},
annote = {Keywords: vertex integrity, monadic second-order logic, cardinality constraint, fixed-parameter tractability}
}
Document
External-Memory Dictionaries with Worst-Case Update Cost
Abstract
The B^ε-tree [Brodal and Fagerberg 2003] is a simple I/O-efficient external-memory-model data structure that supports updates orders of magnitude faster than B-tree with a query performance comparable to the B-tree: for any positive constant ε < 1 insertions and deletions take O(1/B^(1-ε) log_B N) time (rather than O(log_BN) time for the classic B-tree), queries take O(log_B N) time and range queries returning k items take O(log_B N + k/B) time. Although the B^ε-tree has an optimal update/query tradeoff, the runtimes are amortized. Another structure, the write-optimized skip list, introduced by Bender et al. [PODS 2017], has the same performance as the B^ε-tree but with runtimes that are randomized rather than amortized. In this paper, we present a variant of the B^ε-tree with deterministic worst-case running times that are identical to the original’s amortized running times.
Cite as
Rathish Das, John Iacono, and Yakov Nekrich. External-Memory Dictionaries with Worst-Case Update Cost. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{das_et_al:LIPIcs.ISAAC.2022.21,
author = {Das, Rathish and Iacono, John and Nekrich, Yakov},
title = {{External-Memory Dictionaries with Worst-Case Update Cost}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {21:1--21:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.21},
URN = {urn:nbn:de:0030-drops-173060},
doi = {10.4230/LIPIcs.ISAAC.2022.21},
annote = {Keywords: Data Structures, External Memory, Buffer Tree}
}
Document
Finding Matching Cuts in H-Free Graphs
Abstract
The well-known NP-complete problem Matching Cut is to decide if a graph has a matching that is also an edge cut of the graph. We prove new complexity results for Matching Cut restricted to H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. We also prove new complexity results for two recently studied variants of Matching Cut, on H-free graphs. The first variant requires that the matching cut must be extendable to a perfect matching of the graph. The second variant requires the matching cut to be a perfect matching. In particular, we prove that there exists a small constant r > 0 such that the first variant is NP-complete for P_r-free graphs. This addresses a question of Bouquet and Picouleau (arXiv, 2020). For all three problems, we give state-of-the-art summaries of their computational complexity for H-free graphs.
Cite as
Felicia Lucke, Daniël Paulusma, and Bernard Ries. Finding Matching Cuts in H-Free Graphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{lucke_et_al:LIPIcs.ISAAC.2022.22,
author = {Lucke, Felicia and Paulusma, Dani\"{e}l and Ries, Bernard},
title = {{Finding Matching Cuts in H-Free Graphs}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {22:1--22:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.22},
URN = {urn:nbn:de:0030-drops-173076},
doi = {10.4230/LIPIcs.ISAAC.2022.22},
annote = {Keywords: matching cut, perfect matching, H-free graph, computational complexity}
}
Document
Graph Product Structure for h-Framed Graphs
Abstract
Graph product structure theory expresses certain graphs as subgraphs of the strong product of much simpler graphs. In particular, an elegant formulation for the corresponding structural theorems involves the strong product of a path and of a bounded treewidth graph, and allows to lift combinatorial results for bounded treewidth graphs to graph classes for which the product structure holds, such as to planar graphs [Dujmović et al., J. ACM, 67(4), 22:1-38, 2020].
In this paper, we join the search for extensions of this powerful tool beyond planarity by considering the h-framed graphs, a graph class that includes 1-planar, optimal 2-planar, and k-map graphs (for appropriate values of h). We establish a graph product structure theorem for h-framed graphs stating that the graphs in this class are subgraphs of the strong product of a path, of a planar graph of treewidth at most 3, and of a clique of size 3⌊ h/2 ⌋+⌊ h/3 ⌋-1. This allows us to improve over the previous structural theorems for 1-planar and k-map graphs. Our results constitute significant progress over the previous bounds on the queue number, non-repetitive chromatic number, and p-centered chromatic number of these graph classes, e.g., we lower the currently best upper bound on the queue number of 1-planar graphs and k-map graphs from 115 to 82 and from ⌊ 33/2(k+3 ⌊ k/2⌋ -3)⌋ to ⌊ 33/2 (3⌊ k/2 ⌋+⌊ k/3 ⌋-1) ⌋, respectively. We also employ the product structure machinery to improve the current upper bounds on the twin-width of 1-planar graphs from O(1) to 80. All our structural results are constructive and yield efficient algorithms to obtain the corresponding decompositions.
Cite as
Michael A. Bekos, Giordano Da Lozzo, Petr Hliněný, and Michael Kaufmann. Graph Product Structure for h-Framed Graphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{bekos_et_al:LIPIcs.ISAAC.2022.23,
author = {Bekos, Michael A. and Da Lozzo, Giordano and Hlin\v{e}n\'{y}, Petr and Kaufmann, Michael},
title = {{Graph Product Structure for h-Framed Graphs}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {23:1--23:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.23},
URN = {urn:nbn:de:0030-drops-173086},
doi = {10.4230/LIPIcs.ISAAC.2022.23},
annote = {Keywords: Graph product structure theory, h-framed graphs, k-map graphs, queue number, twin-width}
}
Document
Hardness of Approximation for H-Free Edge Modification Problems: Towards a Dichotomy
Abstract
For a fixed graph H, the H-free Edge Deletion/Completion/Editing problem asks to delete/add/edit the minimum possible number of edges in G to get a graph that does not contain an induced subgraph isomorphic to the graph H. In this work, we investigate H-free Edge Deletion/Completion/Editing problems in terms of the hardness of their approximation. We formulate a conjecture according to which all the graphs with at least five vertices can be classified into several groups of graphs with specific structural properties depending on the hardness of approximation for the corresponding H-free Edge Deletion/Completion/Editing problems. Also, we make significant progress in proving that conjecture by showing that it is sufficient to resolve it only for a finite set of graphs.
Cite as
Tatiana Belova and Ivan Bliznets. Hardness of Approximation for H-Free Edge Modification Problems: Towards a Dichotomy. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{belova_et_al:LIPIcs.ISAAC.2022.24,
author = {Belova, Tatiana and Bliznets, Ivan},
title = {{Hardness of Approximation for H-Free Edge Modification Problems: Towards a Dichotomy}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {24:1--24:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.24},
URN = {urn:nbn:de:0030-drops-173097},
doi = {10.4230/LIPIcs.ISAAC.2022.24},
annote = {Keywords: Parameterized complexity, Hardness of approximation, Edge modification problems}
}
Document
Hierarchical Categories in Colored Searching
Abstract
In colored range counting (CRC), the input is a set of points where each point is assigned a "color" (or a "category") and the goal is to store them in a data structure such that the number of distinct categories inside a given query range can be counted efficiently. CRC has strong motivations as it allows data structure to deal with categorical data.
However, colors (i.e., the categories) in the CRC problem do not have any internal structure, whereas this is not the case for many datasets in practice where hierarchical categories exists or where a single input belongs to multiple categories. Motivated by these, we consider variants of the problem where such structures can be represented. We define two variants of the problem called hierarchical range counting (HCC) and sub-category colored range counting (SCRC) and consider hierarchical structures that can either be a DAG or a tree. We show that the two problems on some special trees are in fact equivalent to other well-known problems in the literature. Based on these, we also give efficient data structures when the underlying hierarchy can be represented as a tree. We show a conditional lower bound for the general case when the existing hierarchy can be any DAG, through reductions from the orthogonal vectors problem.
Cite as
Peyman Afshani, Rasmus Killmann, and Kasper Green Larsen. Hierarchical Categories in Colored Searching. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{afshani_et_al:LIPIcs.ISAAC.2022.25,
author = {Afshani, Peyman and Killmann, Rasmus and Larsen, Kasper Green},
title = {{Hierarchical Categories in Colored Searching}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {25:1--25:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.25},
URN = {urn:nbn:de:0030-drops-173100},
doi = {10.4230/LIPIcs.ISAAC.2022.25},
annote = {Keywords: Categorical Data, Computational Geometry}
}
Document
How to Base Security on the Perfect/Statistical Binding Property of Quantum Bit Commitment?
Abstract
The concept of quantum bit commitment was introduced in the early 1980s for the purpose of basing bit commitments solely on principles of quantum theory. Unfortunately, such unconditional quantum bit commitments still turn out to be impossible. As a compromise like in classical cryptography, Dumais et al. [Paul Dumais et al., 2000] introduce the conditional quantum bit commitments that additionally rely on complexity assumptions. However, in contrast to classical bit commitments which are widely used in classical cryptography, up until now there is relatively little work towards studying the application of quantum bit commitments in quantum cryptography. This may be partly due to the well-known weakness of the general quantum binding that comes from the possible superposition attack of the sender of quantum commitments, making it unclear whether quantum commitments could be useful in quantum cryptography.
In this work, following Yan et al. [Jun Yan et al., 2015] we continue studying using (canonical non-interactive) perfectly/statistically-binding quantum bit commitments as the drop-in replacement of classical bit commitments in some well-known constructions. Specifically, we show that the (quantum) security can still be established for zero-knowledge proof, oblivious transfer, and proof-of-knowledge. In spite of this, we stress that the corresponding security analyses are by no means trivial extensions of their classical analyses; new techniques are needed to handle possible superposition attacks by the cheating sender of quantum bit commitments.
Since (canonical non-interactive) statistically-binding quantum bit commitments can be constructed from quantum-secure one-way functions, we hope using them (as opposed to classical commitments) in cryptographic constructions can reduce the round complexity and weaken the complexity assumption simultaneously.
Cite as
Junbin Fang, Dominique Unruh, Jun Yan, and Dehua Zhou. How to Base Security on the Perfect/Statistical Binding Property of Quantum Bit Commitment?. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 26:1-26:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{fang_et_al:LIPIcs.ISAAC.2022.26,
author = {Fang, Junbin and Unruh, Dominique and Yan, Jun and Zhou, Dehua},
title = {{How to Base Security on the Perfect/Statistical Binding Property of Quantum Bit Commitment?}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {26:1--26:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.26},
URN = {urn:nbn:de:0030-drops-173112},
doi = {10.4230/LIPIcs.ISAAC.2022.26},
annote = {Keywords: Quantum bit commitment, quantum zero-knowledge, quantum proof-of-knowledge, quantum oblivious transfer}
}
Document
Improved Compression of the Okamura-Seymour Metric
Abstract
Let G = (V,E) be an undirected unweighted planar graph. Let S = {s_1,…,s_k} be the vertices of some face in G and let T ⊆ V be an arbitrary set of vertices. The Okamura-Seymour metric compression problem asks to compactly encode the S-to-T distances.
Consider a vector storing the distances from an arbitrary vertex v to all vertices S = {s_1,…,s_k} in their cyclic order. The pattern of v is obtained by taking the difference between every pair of consecutive values of this vector. In STOC'19, Li and Parter used a VC-dimension argument to show that in planar graphs, the number of distinct patterns, denoted p_#, is only O(k³). This resulted in a simple Õ(min{k⁴+|T|, k⋅|T|}) space compression of the Okamura-Seymour metric.
We give an alternative proof of the p_# = O(k³) bound that exploits planarity beyond the VC-dimension argument. Namely, our proof relies on cut-cycle duality, as well as on the fact that distances among vertices of S are bounded by k. Our method implies the following:
(1) An Õ(p_#+k+|T|) space compression of the Okamura-Seymour metric, thus improving the compression of Li and Parter to Õ(min{k³+|T|, k⋅|T|}).
(2) An optimal Õ(k+|T|) space compression of the Okamura-Seymour metric, in the case where the vertices of T induce a connected component in G.
(3) A tight bound of p_# = Θ(k²) for the family of Halin graphs, whereas the VC-dimension argument is limited to showing p_# = O(k³).
Cite as
Shay Mozes, Nathan Wallheimer, and Oren Weimann. Improved Compression of the Okamura-Seymour Metric. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 27:1-27:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{mozes_et_al:LIPIcs.ISAAC.2022.27,
author = {Mozes, Shay and Wallheimer, Nathan and Weimann, Oren},
title = {{Improved Compression of the Okamura-Seymour Metric}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {27:1--27:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.27},
URN = {urn:nbn:de:0030-drops-173123},
doi = {10.4230/LIPIcs.ISAAC.2022.27},
annote = {Keywords: Shortest paths, planar graphs, metric compression, distance oracles}
}
Document
Improving the Bounds of the Online Dynamic Power Management Problem
Abstract
We investigate the power-down mechanism which decides when a machine transitions between states such that the total energy consumption, characterized by execution cost, idle cost and switching cost, is minimized. In contrast to most of the previous studies on the offline model, we focus on the online model in which a sequence of jobs with their release time, execution time and deadline, arrive in an online fashion. More precisely, we exploit a different switching on and off strategy and present an upper bound of 3, and further show a lower bound of 2.1, in a dual-machine model, introduced by Chen et al. in 2014 [STACS 2014: 226-238], both of which beat the currently best result.
Cite as
Ya-Chun Liang, Kazuo Iwama, and Chung-Shou Liao. Improving the Bounds of the Online Dynamic Power Management Problem. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{liang_et_al:LIPIcs.ISAAC.2022.28,
author = {Liang, Ya-Chun and Iwama, Kazuo and Liao, Chung-Shou},
title = {{Improving the Bounds of the Online Dynamic Power Management Problem}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {28:1--28:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.28},
URN = {urn:nbn:de:0030-drops-173138},
doi = {10.4230/LIPIcs.ISAAC.2022.28},
annote = {Keywords: Online algorithm, Energy scheduling, Dynamic power management}
}
Document
Integer Complexity and Mixed Binary-Ternary Representation
Abstract
The integer complexity of a natural number n, denoted by ‖n‖, is the smallest number of 1’s needed to express n using an arbitrary combination of addition and multiplication (and parentheses). For example, ‖6‖ = 5 since the expression 6 = (1+1)⋅ (1+1+1) contains five 1’s and there are no such expressions containing at most four 1’s. The investigation of this cute complexity measure was originated by Mahler and Popken in the 1950s. It is easy to see that ‖n‖/(log₃ n) ∈ [3, 3 log₂ 3] (∼ [3,4.755]) for every n, but the distribution of ‖n‖ is largely unknown.
In this work, we focus on the restricted expressions obtained by applying Horner’s schema to a mixed binary-ternary representation of a given number in which we can arrange base-two and base-three digits in an arbitrary order. Let f(n) denote the minimum number of 1’s needed to express n in this way. Apparently, f(n) ≥ ‖n‖ for every n. We extensively investigate on f(n) via the combination of computer experiments and theoretical analysis and obtain the following set of results: (i) Computer experiments supporting the hypothesis that f(n)/log₃ n < 3.483 on average and f(n)/log₃ n < 4.212 for all n, (ii) For almost all natural numbers n, 3.120 < f(n)/log₃ n < 3.587, and (iii) There are infinitely many n’s such that f(n)/log₃ n > 3.934. Several new bounds on the original integer complexity are also presented in the paper.
Cite as
Kazuyuki Amano. Integer Complexity and Mixed Binary-Ternary Representation. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{amano:LIPIcs.ISAAC.2022.29,
author = {Amano, Kazuyuki},
title = {{Integer Complexity and Mixed Binary-Ternary Representation}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {29:1--29:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.29},
URN = {urn:nbn:de:0030-drops-173146},
doi = {10.4230/LIPIcs.ISAAC.2022.29},
annote = {Keywords: Integer complexity, Lower bounds, Upper bounds, Horner’s schema, Computer assisted proof}
}
Document
List Locally Surjective Homomorphisms in Hereditary Graph Classes
Abstract
A locally surjective homomorphism from a graph G to a graph H is an edge-preserving mapping from V(G) to V(H) that is surjective in the neighborhood of each vertex in G. In the list locally surjective homomorphism problem, denoted by LLSHom(H), the graph H is fixed and the instance consists of a graph G whose every vertex is equipped with a subset of V(H), called list. We ask for the existence of a locally surjective homomorphism from G to H, where every vertex of G is mapped to a vertex from its list. In this paper, we study the complexity of the LLSHom(H) problem in F-free graphs, i.e., graphs that exclude a fixed graph F as an induced subgraph. We aim to understand for which pairs (H,F) the problem can be solved in subexponential time.
We show that for all graphs H, for which the problem is NP-hard in general graphs, it cannot be solved in subexponential time in F-free graphs for F being a bounded-degree forest, unless the ETH fails. The initial study reveals that a natural subfamily of bounded-degree forests F, that might lead to some tractability results, is the family 𝒮 consisting of forests whose every component has at most three leaves. In this case, we exhibit the following dichotomy theorem: besides the cases that are polynomial-time solvable in general graphs, the graphs H ∈ {P₃,C₄} are the only connected ones that allow for a subexponential-time algorithm in F-free graphs for every F ∈ 𝒮 (unless the ETH fails).
Cite as
Pavel Dvořák, Tomáš Masařík, Jana Novotná, Monika Krawczyk, Paweł Rzążewski, and Aneta Żuk. List Locally Surjective Homomorphisms in Hereditary Graph Classes. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{dvorak_et_al:LIPIcs.ISAAC.2022.30,
author = {Dvo\v{r}\'{a}k, Pavel and Masa\v{r}{\'\i}k, Tom\'{a}\v{s} and Novotn\'{a}, Jana and Krawczyk, Monika and Rz\k{a}\.{z}ewski, Pawe{\l} and \.{Z}uk, Aneta},
title = {{List Locally Surjective Homomorphisms in Hereditary Graph Classes}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {30:1--30:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.30},
URN = {urn:nbn:de:0030-drops-173154},
doi = {10.4230/LIPIcs.ISAAC.2022.30},
annote = {Keywords: Homomorphism, Hereditary graphs, Subexponential-time algorithms}
}
Document
Locally Checkable Problems Parameterized by Clique-Width
Abstract
We continue the study initiated by Bonomo-Braberman and Gonzalez in 2020 on r-locally checkable problems. We propose a dynamic programming algorithm that takes as input a graph with an associated clique-width expression and solves a 1-locally checkable problem under certain restrictions. We show that it runs in polynomial time in graphs of bounded clique-width, when the number of colors of the locally checkable problem is fixed. Furthermore, we present a first extension of our framework to global properties by taking into account the sizes of the color classes, and consequently enlarge the set of problems solvable in polynomial time with our approach in graphs of bounded clique-width. As examples, we apply this setting to show that, when parameterized by clique-width, the [k]-Roman domination problem is FPT, and the k-community problem, Max PDS and other variants are XP.
Cite as
Narmina Baghirova, Carolina Lucía Gonzalez, Bernard Ries, and David Schindl. Locally Checkable Problems Parameterized by Clique-Width. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 31:1-31:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{baghirova_et_al:LIPIcs.ISAAC.2022.31,
author = {Baghirova, Narmina and Gonzalez, Carolina Luc{\'\i}a and Ries, Bernard and Schindl, David},
title = {{Locally Checkable Problems Parameterized by Clique-Width}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {31:1--31:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.31},
URN = {urn:nbn:de:0030-drops-173167},
doi = {10.4230/LIPIcs.ISAAC.2022.31},
annote = {Keywords: locally checkable problem, clique-width, dynamic programming, coloring}
}
Document
Lower Bounds on Retroactive Data Structures
Abstract
We prove essentially optimal fine-grained lower bounds on the gap between a data structure and a partially retroactive version of the same data structure. Precisely, assuming any one of three standard conjectures, we describe a problem that has a data structure where operations run in O(T(n,m)) time per operation, but any partially retroactive version of that data structure requires T(n,m)⋅m^{1-o(1)} worst-case time per operation, where n is the size of the data structure at any time and m is the number of operations. Any data structure with operations running in O(T(n,m)) time per operation can be converted (via the "rollback method") into a partially retroactive data structure running in O(T(n,m)⋅m) time per operation, so our lower bound is tight up to an m^o(1) factor common in fine-grained complexity.
Cite as
Lily Chung, Erik D. Demaine, Dylan Hendrickson, and Jayson Lynch. Lower Bounds on Retroactive Data Structures. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 32:1-32:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{chung_et_al:LIPIcs.ISAAC.2022.32,
author = {Chung, Lily and Demaine, Erik D. and Hendrickson, Dylan and Lynch, Jayson},
title = {{Lower Bounds on Retroactive Data Structures}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {32:1--32:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.32},
URN = {urn:nbn:de:0030-drops-173171},
doi = {10.4230/LIPIcs.ISAAC.2022.32},
annote = {Keywords: Retroactivity, time travel, rollback, fine-grained complexity}
}
Document
Minimizing the Maximum Flow Time in the Online Food Delivery Problem
Abstract
We study a common delivery problem encountered in nowadays online food-ordering platforms: Customers order dishes online, and the restaurant delivers the food after receiving the order. Specifically, we study a problem where k vehicles of capacity c are serving a set of requests ordering food from one restaurant. After a request arrives, it can be served by a vehicle moving from the restaurant to its delivery location. We are interested in serving all requests while minimizing the maximum flow-time, i.e., the maximum time length a customer waits to receive his/her food after submitting the order.
We show that the problem is hard in both offline and online settings even when k = 1 and c = ∞: There is a hardness of approximation of Ω(n) for the offline problem, and a lower bound of Ω(n) on the competitive ratio of any online algorithm, where n is number of points in the metric.
We circumvent the strong negative results in two directions. Our main result is an O(1)-competitive online algorithm for the uncapacitated (i.e, c = ∞) food delivery problem on tree metrics; we also have negative result showing that the condition c = ∞ is needed. Then we explore the speed-augmentation model where our online algorithm is allowed to use vehicles with faster speed. We show that a moderate speeding factor leads to a constant competitive ratio, and we prove a tight trade-off between the speeding factor and the competitive ratio.
Cite as
Xiangyu Guo, Kelin Luo, Shi Li, and Yuhao Zhang. Minimizing the Maximum Flow Time in the Online Food Delivery Problem. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 33:1-33:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{guo_et_al:LIPIcs.ISAAC.2022.33,
author = {Guo, Xiangyu and Luo, Kelin and Li, Shi and Zhang, Yuhao},
title = {{Minimizing the Maximum Flow Time in the Online Food Delivery Problem}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {33:1--33:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.33},
URN = {urn:nbn:de:0030-drops-173181},
doi = {10.4230/LIPIcs.ISAAC.2022.33},
annote = {Keywords: Online algorithm, Capacitated Vehicle Routing, Flow Time Optimization}
}
Document
Minimum Link Fencing
Abstract
We study a variant of the geometric multicut problem, where we are given a set 𝒫 of colored and pairwise interior-disjoint polygons in the plane. The objective is to compute a set of simple closed polygon boundaries (fences) that separate the polygons in such a way that any two polygons that are enclosed by the same fence have the same color, and the total number of links of all fences is minimized. We call this the minimum link fencing (MLF) problem and consider the natural case of bounded minimum link fencing (BMLF), where 𝒫 contains a polygon Q that is unbounded in all directions and can be seen as an outer polygon. We show that BMLF is NP-hard in general and that it is XP-time solvable when each fence contains at most two polygons and the number of segments per fence is the parameter. Finally, we present an O(n log n)-time algorithm for the case that the convex hull of 𝒫⧵{Q} does not intersect Q.
Cite as
Sujoy Bhore, Fabian Klute, Maarten Löffler, Martin Nöllenburg, Soeren Terziadis, and Anaïs Villedieu. Minimum Link Fencing. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{bhore_et_al:LIPIcs.ISAAC.2022.34,
author = {Bhore, Sujoy and Klute, Fabian and L\"{o}ffler, Maarten and N\"{o}llenburg, Martin and Terziadis, Soeren and Villedieu, Ana\"{i}s},
title = {{Minimum Link Fencing}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {34:1--34:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.34},
URN = {urn:nbn:de:0030-drops-173191},
doi = {10.4230/LIPIcs.ISAAC.2022.34},
annote = {Keywords: computational geometry, polygon nesting, polygon separation}
}
Document
Multi-Robot Motion Planning for Unit Discs with Revolving Areas
Abstract
We study the problem of motion planning for a collection of n labeled unit disc robots in a polygonal environment. We assume that the robots have revolving areas around their start and final positions: that each start and each final is contained in a radius 2 disc lying in the free space, not necessarily concentric with the start or final position, which is free from other start or final positions. This assumption allows a weakly-monotone motion plan, in which robots move according to an ordering as follows: during the turn of a robot R in the ordering, it moves fully from its start to final position, while other robots do not leave their revolving areas. As R passes through a revolving area, a robot R' that is inside this area may move within the revolving area to avoid a collision. Notwithstanding the existence of a motion plan, we show that minimizing the total traveled distance in this setting, specifically even when the motion plan is restricted to be weakly-monotone, is APX-hard, ruling out any polynomial-time (1+ε)-approximation algorithm.
On the positive side, we present the first constant-factor approximation algorithm for computing a feasible weakly-monotone motion plan. The total distance traveled by the robots is within an O(1) factor of that of the optimal motion plan, which need not be weakly monotone. Our algorithm extends to an online setting in which the polygonal environment is fixed but the initial and final positions of robots are specified in an online manner. Finally, we observe that the overhead in the overall cost that we add while editing the paths to avoid robot-robot collision can vary significantly depending on the ordering we chose. Finding the best ordering in this respect is known to be NP-hard, and we provide a polynomial time O(log n log log n)-approximation algorithm for this problem.
Cite as
Pankaj K. Agarwal, Tzvika Geft, Dan Halperin, and Erin Taylor. Multi-Robot Motion Planning for Unit Discs with Revolving Areas. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{agarwal_et_al:LIPIcs.ISAAC.2022.35,
author = {Agarwal, Pankaj K. and Geft, Tzvika and Halperin, Dan and Taylor, Erin},
title = {{Multi-Robot Motion Planning for Unit Discs with Revolving Areas}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {35:1--35:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.35},
URN = {urn:nbn:de:0030-drops-173204},
doi = {10.4230/LIPIcs.ISAAC.2022.35},
annote = {Keywords: motion planning, optimal motion planning, approximation, complexity, NP-hardness}
}
Document
Nested Active-Time Scheduling
Abstract
The active-time scheduling problem considers the problem of scheduling preemptible jobs with windows (release times and deadlines) on a parallel machine that can schedule up to g jobs during each timestep. The goal in the active-time problem is to minimize the number of active steps, i.e., timesteps in which at least one job is scheduled. In this way, the active time models parallel scheduling when there is a fixed cost for turning the machine on at each discrete step.
This paper presents a 9/5-approximation algorithm for a special case of the active-time scheduling problem in which job windows are laminar (nested). This result improves on the previous best 2-approximation for the general case.
Cite as
Nairen Cao, Jeremy T. Fineman, Shi Li, Julián Mestre, Katina Russell, and Seeun William Umboh. Nested Active-Time Scheduling. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{cao_et_al:LIPIcs.ISAAC.2022.36,
author = {Cao, Nairen and Fineman, Jeremy T. and Li, Shi and Mestre, Juli\'{a}n and Russell, Katina and Umboh, Seeun William},
title = {{Nested Active-Time Scheduling}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {36:1--36:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.36},
URN = {urn:nbn:de:0030-drops-173214},
doi = {10.4230/LIPIcs.ISAAC.2022.36},
annote = {Keywords: Scheduling algorithms, Active time, Approximation algorithm}
}
Document
On Algorithmic Self-Assembly of Squares by Co-Transcriptional Folding
Abstract
Algorithms play a primary role in programming an orchestrated self-assembly of shapes into molecules. In this paper, we study the algorithmic self-assembly of squares by RNA co-transcriptional folding in its oritatami model. We formalize the square self-assembly problem in oritatami and propose a universal oritatami transcript made of 939 types of abstract molecules (beads) and of period 1294 that folds deterministically and co-transcriptionally at delay 3 and maximum arity into the n × n square modulo horizontal and vertical scaling factors for all sufficiently large n’s after building a Θ(log n) width "ruler" that measures n upon the seed of size Θ(log n) on which n is encoded in binary.
Cite as
Szilárd Zsolt Fazekas, Hwee Kim, Ryuichi Matsuoka, Shinnosuke Seki, and Hinano Takeuchi. On Algorithmic Self-Assembly of Squares by Co-Transcriptional Folding. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{fazekas_et_al:LIPIcs.ISAAC.2022.37,
author = {Fazekas, Szil\'{a}rd Zsolt and Kim, Hwee and Matsuoka, Ryuichi and Seki, Shinnosuke and Takeuchi, Hinano},
title = {{On Algorithmic Self-Assembly of Squares by Co-Transcriptional Folding}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {37:1--37:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.37},
URN = {urn:nbn:de:0030-drops-173228},
doi = {10.4230/LIPIcs.ISAAC.2022.37},
annote = {Keywords: Algorithmic molecular self-assembly, Co-transcriptional folding, Oritatami system, Self-assembly of squares}
}
Document
On Constrained Intersection Representations of Graphs and Digraphs
Abstract
We study the problem of determining minimal directed intersection representations of DAGs in a model introduced by [Kostochka, Liu, Machado, and Milenkovic, ISIT2019]: vertices are assigned color sets, two vertices are connected by an arc if and only if they share at least one color and the tail vertex has a strictly smaller color set than the head, and the goal is to minimize the total number of colors. We show that the problem is polynomially solvable in the class of triangle-free and Hamiltonian DAGs and also disclose the relationship of this problem with several other models of intersection representations of graphs and digraphs.
Cite as
Ferdinando Cicalese, Clément Dallard, and Martin Milanič. On Constrained Intersection Representations of Graphs and Digraphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 38:1-38:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{cicalese_et_al:LIPIcs.ISAAC.2022.38,
author = {Cicalese, Ferdinando and Dallard, Cl\'{e}ment and Milani\v{c}, Martin},
title = {{On Constrained Intersection Representations of Graphs and Digraphs}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {38:1--38:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.38},
URN = {urn:nbn:de:0030-drops-173239},
doi = {10.4230/LIPIcs.ISAAC.2022.38},
annote = {Keywords: Directed intersection representation, intersection number}
}
Document
On Finding Short Reconfiguration Sequences Between Independent Sets
Abstract
Assume we are given a graph G, two independent sets S and T in G of size k ≥ 1, and a positive integer 𝓁 ≥ 1. The goal is to decide whether there exists a sequence ⟨ I₀, I₁, ..., I_𝓁 ⟩ of independent sets such that for all j ∈ {0,…,𝓁-1} the set I_j is an independent set of size k, I₀ = S, I_𝓁 = T, and I_{j+1} is obtained from I_j by a predetermined reconfiguration rule. We consider two reconfiguration rules, namely token sliding and token jumping. Intuitively, we view each independent set as a collection of tokens placed on the vertices of the graph. Then, the Token Sliding Optimization (TSO) problem asks whether there exists a sequence of at most 𝓁 steps that transforms S into T, where at each step we are allowed to slide one token from a vertex to an unoccupied neighboring vertex (while maintaining independence). In the Token Jumping Optimization (TJO) problem, at each step, we are allowed to jump one token from a vertex to any other unoccupied vertex of the graph (as long as we maintain independence). Both TSO and TJO are known to be fixed-parameter tractable when parameterized by 𝓁 on nowhere dense classes of graphs. In this work, we investigate the boundary of tractability for sparse classes of graphs. We show that both problems are fixed-parameter tractable for parameter k + 𝓁 + d on d-degenerate graphs as well as for parameter |M| + 𝓁 + Δ on graphs having a modulator M whose deletion leaves a graph of maximum degree Δ. We complement these result by showing that for parameter 𝓁 alone both problems become W[1]-hard already on 2-degenerate graphs. Our positive result makes use of the notion of independence covering families introduced by Lokshtanov et al. [Daniel Lokshtanov et al., 2020]. Finally, we show as a side result that using such families we can obtain a simpler and unified algorithm for the standard Token Jumping Reachability problem (a.k.a. Token Jumping) parameterized by k on both degenerate and nowhere dense classes of graphs.
Cite as
Akanksha Agrawal, Soumita Hait, and Amer E. Mouawad. On Finding Short Reconfiguration Sequences Between Independent Sets. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 39:1-39:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{agrawal_et_al:LIPIcs.ISAAC.2022.39,
author = {Agrawal, Akanksha and Hait, Soumita and Mouawad, Amer E.},
title = {{On Finding Short Reconfiguration Sequences Between Independent Sets}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {39:1--39:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.39},
URN = {urn:nbn:de:0030-drops-173244},
doi = {10.4230/LIPIcs.ISAAC.2022.39},
annote = {Keywords: Token sliding, token jumping, fixed-parameter tractability, combinatorial reconfiguration, shortest reconfiguration sequence}
}
Document
On Graphs Coverable by k Shortest Paths
Abstract
We show that if the edges or vertices of an undirected graph G can be covered by k shortest paths, then the pathwidth of G is upper-bounded by a function of k. As a corollary, we prove that the problem Isometric Path Cover with Terminals (which, given a graph G and a set of k pairs of vertices called terminals, asks whether G can be covered by k shortest paths, each joining a pair of terminals) is FPT with respect to the number of terminals. The same holds for the similar problem Strong Geodetic Set with Terminals (which, given a graph G and a set of k terminals, asks whether there exist binom(k,2) shortest paths, each joining a distinct pair of terminals such that these paths cover G). Moreover, this implies that the related problems Isometric Path Cover and Strong Geodetic Set (defined similarly but where the set of terminals is not part of the input) are in XP with respect to parameter k.
Cite as
Maël Dumas, Florent Foucaud, Anthony Perez, and Ioan Todinca. On Graphs Coverable by k Shortest Paths. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 40:1-40:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{dumas_et_al:LIPIcs.ISAAC.2022.40,
author = {Dumas, Ma\"{e}l and Foucaud, Florent and Perez, Anthony and Todinca, Ioan},
title = {{On Graphs Coverable by k Shortest Paths}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {40:1--40:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.40},
URN = {urn:nbn:de:0030-drops-173251},
doi = {10.4230/LIPIcs.ISAAC.2022.40},
annote = {Keywords: Shortest paths, covering problems, parameterized complexity}
}
Document
On Maximizing Sums of Non-Monotone Submodular and Linear Functions
Abstract
We study the problem of Regularized Unconstrained Submodular Maximization (RegularizedUSM) as defined by [Bodek and Feldman '22]. In this problem, we are given query access to a non-negative submodular function f: 2^N → ℝ_{≥ 0} and a linear function 𝓁: 2^N → ℝ over the same ground set N, and the objective is to output a set T ⊆ N approximately maximizing the sum f(T)+𝓁(T). Specifically, an algorithm is said to provide an (α,β)-approximation for RegularizedUSM if it outputs a set T such that E[f(T)+𝓁(T)] ≥ max_{S ⊆ N}[α ⋅ f(S)+β⋅ 𝓁(S)]. We also study the setting where S and T are constrained to be independent in a given matroid, which we refer to as Regularized Constrained Submodular Maximization (RegularizedCSM).
The special case of RegularizedCSM with monotone f has been extensively studied [Sviridenko et al. '17, Feldman '18, Harshaw et al. '19]. On the other hand, we are aware of only one prior work that studies RegularizedCSM with non-monotone f [Lu et al. '21], and that work constrains 𝓁 to be non-positive. In this work, we provide improved (α,β)-approximation algorithms for both {RegularizedUSM} and {RegularizedCSM} with non-monotone f. In particular, we are the first to provide nontrivial (α,β)-approximations for RegularizedCSM where the sign of 𝓁 is unconstrained, and the α we obtain for RegularizedUSM improves over [Bodek and Feldman '22] for all β ∈ (0,1).
In addition to approximation algorithms, we provide improved inapproximability results for all of the aforementioned cases. In particular, we show that the α our algorithm obtains for {RegularizedCSM} with unconstrained 𝓁 is essentially tight for β ≥ e/(e+1). Using similar ideas, we are also able to show 0.478-inapproximability for maximizing a submodular function where S and T are subject to a cardinality constraint, improving a 0.491-inapproximability result due to [Oveis Gharan and Vondrak '10].
Cite as
Benjamin Qi. On Maximizing Sums of Non-Monotone Submodular and Linear Functions. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{qi:LIPIcs.ISAAC.2022.41,
author = {Qi, Benjamin},
title = {{On Maximizing Sums of Non-Monotone Submodular and Linear Functions}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {41:1--41:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.41},
URN = {urn:nbn:de:0030-drops-173263},
doi = {10.4230/LIPIcs.ISAAC.2022.41},
annote = {Keywords: submodular maximization, regularization, continuous greedy, inapproximability}
}
Document
On Reverse Shortest Paths in Geometric Proximity Graphs
Abstract
Let S be a set of n geometric objects of constant complexity (e.g., points, line segments, disks, ellipses) in ℝ², and let ϱ: S× S → ℝ_{≥ 0} be a distance function on S. For a parameter r ≥ 0, we define the proximity graph G(r) = (S,E) where E = {(e₁,e₂) ∈ S×S ∣ e₁≠e₂, ϱ(e₁,e₂) ≤ r}. Given S, s,t ∈ S, and an integer k ≥ 1, the reverse-shortest-path (RSP) problem asks for computing the smallest value r^* ≥ 0 such that G(r^*) contains a path from s to t of length at most k.
In this paper we present a general randomized technique that solves the RSP problem efficiently for a large family of geometric objects and distance functions. Using standard, and sometimes more involved, semi-algebraic range-searching techniques, we first give an efficient algorithm for the decision problem, namely, given a value r ≥ 0, determine whether G(r) contains a path from s to t of length at most k. Next, we adapt our decision algorithm and combine it with a random-sampling method to compute r^*, by efficiently performing a binary search over an implicit set of O(n²) candidate values that contains r^*.
We illustrate the versatility of our general technique by applying it to a variety of geometric proximity graphs. For example, we obtain (i) an O^*(n^{4/3}) expected-time randomized algorithm (where O^*(⋅) hides polylog(n) factors) for the case where S is a set of pairwise-disjoint line segments in ℝ² and ϱ(e₁,e₂) = min_{x ∈ e₁, y ∈ e₂} ‖x-y‖ (where ‖⋅‖ is the Euclidean distance), and (ii) an O^*(n+m^{4/3}) expected-time randomized algorithm for the case where S is a set of m points lying on an x-monotone polygonal chain T with n vertices, and ϱ(p,q), for p,q ∈ S, is the smallest value h such that the points p' := p+(0,h) and q' := q+(0,h) are visible to each other, i.e., all points on the segment p'q' lie above or on the polygonal chain T.
Cite as
Pankaj K. Agarwal, Matthew J. Katz, and Micha Sharir. On Reverse Shortest Paths in Geometric Proximity Graphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 42:1-42:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{agarwal_et_al:LIPIcs.ISAAC.2022.42,
author = {Agarwal, Pankaj K. and Katz, Matthew J. and Sharir, Micha},
title = {{On Reverse Shortest Paths in Geometric Proximity Graphs}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {42:1--42:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.42},
URN = {urn:nbn:de:0030-drops-173277},
doi = {10.4230/LIPIcs.ISAAC.2022.42},
annote = {Keywords: Geometric optimization, proximity graphs, semi-algebraic range searching, reverse shortest path}
}
Document
On the Complexity of Rainbow Vertex Colouring Diametral Path Graphs
Abstract
Given a graph and a colouring of its vertices, a rainbow vertex path is a path between two vertices such that all the internal nodes of the path are coloured distinctly. A graph is rainbow vertex-connected if between every pair of vertices in the graph there exists a rainbow vertex path. We study the problem of deciding whether a given graph can be coloured using k or less colours such that it is rainbow vertex-connected. Note that every graph G needs at least diam(G)-1 colours to be rainbow vertex connected.
Heggernes et al. [MFCS, 2018] conjectured that if G is a graph in which every induced subgraph has a dominating diametral path, then G can always be rainbow vertex coloured with diam(G)-1 many colours. In this work, we confirm their conjecture for chordal, bipartite and claw-free diametral path graphs. We complement these results by showing the conjecture does not hold if the condition on every induced subgraph is dropped. In fact we show that, in this case, even though diam(G) many colours are always enough, it is NP-complete to determine whether a graph with a dominating diametral path of length three can be rainbow vertex coloured with two colours.
Cite as
Jakob Dyrseth and Paloma T. Lima. On the Complexity of Rainbow Vertex Colouring Diametral Path Graphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 43:1-43:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{dyrseth_et_al:LIPIcs.ISAAC.2022.43,
author = {Dyrseth, Jakob and Lima, Paloma T.},
title = {{On the Complexity of Rainbow Vertex Colouring Diametral Path Graphs}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {43:1--43:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.43},
URN = {urn:nbn:de:0030-drops-173286},
doi = {10.4230/LIPIcs.ISAAC.2022.43},
annote = {Keywords: rainbow vertex colouring, diametral path graphs, interval graphs}
}
Document
On the Complexity of Tree Edit Distance with Variables
Abstract
In this paper, we propose tree edit distance with variables, which is an extension of the tree edit distance to handle trees with variables and has a potential application to measuring the similarity between mathematical formulas. We analyze the computational complexity of several variants of this model. In particular, we show that the problem is NP-complete for ordered trees. We also show for unordered trees that the problem of deciding whether or not the distance is 0 is graph isomorphism complete but can be solved in polynomial time if the maximum outdegree of input trees is bounded by a constant. We also present parameterized and exponential-time algorithms for ordered and unordered cases, respectively.
Cite as
Tatsuya Akutsu, Tomoya Mori, Naotoshi Nakamura, Satoshi Kozawa, Yuhei Ueno, and Thomas N. Sato. On the Complexity of Tree Edit Distance with Variables. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{akutsu_et_al:LIPIcs.ISAAC.2022.44,
author = {Akutsu, Tatsuya and Mori, Tomoya and Nakamura, Naotoshi and Kozawa, Satoshi and Ueno, Yuhei and Sato, Thomas N.},
title = {{On the Complexity of Tree Edit Distance with Variables}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {44:1--44:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.44},
URN = {urn:nbn:de:0030-drops-173295},
doi = {10.4230/LIPIcs.ISAAC.2022.44},
annote = {Keywords: Tree edit distance, unification, parameterized algorithms}
}
Document
On the Cop Number of String Graphs
Abstract
Cops and Robber is a well-studied two-player pursuit-evasion game played on a graph, where a group of cops tries to capture the robber. The cop number of a graph is the minimum number of cops required to capture the robber. We show that the cop number of a string graph is at most 13, improving upon a result of Gavenčiak et al. [Eur. J. of Comb. 72, 45-69 (2018)]. Using similar techniques, we also show that four cops have a winning strategy for a variant of Cops and Robber, named Fully Active Cops and Robber, on planar graphs, addressing an open question of Gromovikov et al. [Austr. J. Comb. 76(2), 248-265 (2020)].
Cite as
Sandip Das and Harmender Gahlawat. On the Cop Number of String Graphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 45:1-45:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{das_et_al:LIPIcs.ISAAC.2022.45,
author = {Das, Sandip and Gahlawat, Harmender},
title = {{On the Cop Number of String Graphs}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {45:1--45:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.45},
URN = {urn:nbn:de:0030-drops-173308},
doi = {10.4230/LIPIcs.ISAAC.2022.45},
annote = {Keywords: Cop number, string graphs, intersection graphs, planar graphs, pursuit-evasion games}
}
Document
On the Parameterized Intractability of Determinant Maximization
Abstract
In the Determinant Maximization problem, given an n × n positive semi-definite matrix A in ℚ^{n × n} and an integer k, we are required to find a k × k principal submatrix of A having the maximum determinant. This problem is known to be NP-hard and further proven to be W[1]-hard with respect to k by Koutis (2006); i.e., a f(k)n^𝒪(1)-time algorithm is unlikely to exist for any computable function f. However, there is still room to explore its parameterized complexity in the restricted case, in the hope of overcoming the general-case parameterized intractability. In this study, we rule out the fixed-parameter tractability of Determinant Maximization even if an input matrix is extremely sparse or low rank, or an approximate solution is acceptable. We first prove that Determinant Maximization is NP-hard and W[1]-hard even if an input matrix is an arrowhead matrix; i.e., the underlying graph formed by nonzero entries is a star, implying that the structural sparsity is not helpful. By contrast, we show that Determinant Maximization is solvable in polynomial time on tridiagonal matrices. Thereafter, we demonstrate the W[1]-hardness with respect to the rank r of an input matrix. Our result is stronger than Koutis' result in the sense that any k × k principal submatrix is singular whenever k > r. We finally give evidence that it is W[1]-hard to approximate Determinant Maximization parameterized by k within a factor of 2^{-c√k} for some universal constant c > 0. Our hardness result is conditional on the Parameterized Inapproximability Hypothesis posed by Lokshtanov, Ramanujan, Saurab, and Zehavi (2020), which asserts that a gap version of Binary Constraint Satisfaction Problem is W[1]-hard. To complement this result, we develop an ε-additive approximation algorithm that runs in ε^{-r²}⋅r^𝒪(r³)⋅n^𝒪(1) time for the rank r of an input matrix, provided that the diagonal entries are bounded.
Cite as
Naoto Ohsaka. On the Parameterized Intractability of Determinant Maximization. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 46:1-46:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{ohsaka:LIPIcs.ISAAC.2022.46,
author = {Ohsaka, Naoto},
title = {{On the Parameterized Intractability of Determinant Maximization}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {46:1--46:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.46},
URN = {urn:nbn:de:0030-drops-173316},
doi = {10.4230/LIPIcs.ISAAC.2022.46},
annote = {Keywords: Determinant maximization, Parameterized complexity, Approximability}
}
Document
One-Face Shortest Disjoint Paths with a Deviation Terminal
Abstract
For an undirected graph G and distinct vertices s₁, t₁, … , s_k, t_k called terminals, the shortest k-disjoint paths problem asks for k pairwise vertex-disjoint paths P₁, … , P_k such that P_i connects s_i and t_i for i = 1, … , k and the sum of their lengths is minimized. This problem is a natural optimization version of the well-known k-disjoint paths problem, and its polynomial solvability is widely open. One of the best results on the shortest k-disjoint paths problem is due to Datta et al. [Datta et al., 2018], who present a polynomial-time algorithm for the case when G is planar and all the terminals are on one face. In this paper, we extend this result by giving a polynomial-time randomized algorithm for the case when all the terminals except one are on some face of G. In our algorithm, we combine the arguments of Datta et al. with some results on the shortest disjoint (A + B)-paths problem shown by Hirai and Namba [Hirai and Namba, 2018]. To this end, we present a non-trivial bijection between k disjoint paths and disjoint (A + B)-paths, which is a key technical contribution of this paper.
Cite as
Yusuke Kobayashi and Tatsuya Terao. One-Face Shortest Disjoint Paths with a Deviation Terminal. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 47:1-47:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{kobayashi_et_al:LIPIcs.ISAAC.2022.47,
author = {Kobayashi, Yusuke and Terao, Tatsuya},
title = {{One-Face Shortest Disjoint Paths with a Deviation Terminal}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {47:1--47:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.47},
URN = {urn:nbn:de:0030-drops-173322},
doi = {10.4230/LIPIcs.ISAAC.2022.47},
annote = {Keywords: shortest disjoint paths, polynomial time algorithm, planar graph}
}
Document
Optimizing Quantum Circuit Parameters via SDP
Abstract
In recent years, parameterized quantum circuits have become a major tool to design quantum algorithms for optimization problems.
The challenge in fully taking advantage of a given family of parameterized circuits lies in finding a good set of parameters in a non-convex landscape that can grow exponentially to the number of parameters.
We introduce a new framework for optimizing parameterized quantum circuits: round SDP solutions to circuit parameters.
Within this framework, we propose an algorithm that produces approximate solutions for a quantum optimization problem called Quantum Max Cut.
The rounding algorithm runs in polynomial time to the number of parameters regardless of the underlying interaction graph.
The resulting 0.562-approximation algorithm for generic instances of Quantum Max Cut improves on the previously known best algorithms by Anshu, Gosset, and Morenz with a ratio 0.531 and by Parekh and Thompson with a ratio 0.533.
Cite as
Eunou Lee. Optimizing Quantum Circuit Parameters via SDP. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{lee:LIPIcs.ISAAC.2022.48,
author = {Lee, Eunou},
title = {{Optimizing Quantum Circuit Parameters via SDP}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {48:1--48:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.48},
URN = {urn:nbn:de:0030-drops-173330},
doi = {10.4230/LIPIcs.ISAAC.2022.48},
annote = {Keywords: Quantum algorithm, Optimization, Rounding algorithm, Quantum Circuit, Approximation}
}
Document
Package Delivery Using Drones with Restricted Movement Areas
Abstract
For the problem of delivering a package from a source node to a destination node in a graph using a set of drones, we study the setting where the movements of each drone are restricted to a certain subgraph of the given graph. We consider the objectives of minimizing the delivery time (problem DDT) and of minimizing the total energy consumption (problem DDC). For general graphs, we show a strong inapproximability result and a matching approximation algorithm for DDT as well as NP-hardness and a 2-approximation algorithm for DDC. For the special case of a path, we show that DDT is NP-hard if the drones have different speeds. For trees, we give optimal algorithms under the assumption that all drones have the same speed or the same energy consumption rate. The results for trees extend to arbitrary graphs if the subgraph of each drone is isometric.
Cite as
Thomas Erlebach, Kelin Luo, and Frits C.R. Spieksma. Package Delivery Using Drones with Restricted Movement Areas. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 49:1-49:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{erlebach_et_al:LIPIcs.ISAAC.2022.49,
author = {Erlebach, Thomas and Luo, Kelin and Spieksma, Frits C.R.},
title = {{Package Delivery Using Drones with Restricted Movement Areas}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {49:1--49:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.49},
URN = {urn:nbn:de:0030-drops-173343},
doi = {10.4230/LIPIcs.ISAAC.2022.49},
annote = {Keywords: Mobile agents, approximation algorithm, inapproximability}
}
Document
Parameterized Approximation Algorithms for TSP
Abstract
We study the Traveling Salesman problem (TSP), where given a complete undirected graph G = (V,E) with n vertices and an edge cost function c:E↦R_{⩾0}, the goal is to find a minimum-cost cycle visiting every vertex exactly once. It is well-known that unless P = NP, TSP cannot be approximated in polynomial time within a factor of ρ(n) for any computable function ρ, while the metric case of TSP, that the edge cost function satisfies the △-inequality, admits a polynomial-time 1.5-approximation. We investigate TSP on general graphs from the perspective of parameterized approximability. A parameterized ρ-approximation algorithm returns a ρ-approximation solution in f(k)⋅|I|^O(1) time, where f is a computable function and k is a parameter of the input I. We introduce two parameters, which measure the distance of a given TSP-instance from the metric case, and achieve the following two results:
- A 3-approximation algorithm for TSP in O((3k₁)! 8^k₁⋅ n²+n³) time, where k₁ is the number of triangles in which the edge costs violate the △-inequality.
- A 3-approximation algorithm for TSP in O(n^O(k₂)) time and a (6k₂+9)-approximation algorithm for TSP in O(k₂^O(k₂)⋅n³) time, where k₂ is the minimum number of vertices, whose removal results in a metric graph.
To our best knowledge, the above algorithms are the first non-trivial parameterized approximation algorithms for TSP on general graphs.
Cite as
Jianqi Zhou, Peihua Li, and Jiong Guo. Parameterized Approximation Algorithms for TSP. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 50:1-50:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{zhou_et_al:LIPIcs.ISAAC.2022.50,
author = {Zhou, Jianqi and Li, Peihua and Guo, Jiong},
title = {{Parameterized Approximation Algorithms for TSP}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {50:1--50:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.50},
URN = {urn:nbn:de:0030-drops-173358},
doi = {10.4230/LIPIcs.ISAAC.2022.50},
annote = {Keywords: FPT-approximation algorithms, the Traveling Salesman problem, the triangle inequality, fixed-parameter tractability, metric graphs}
}
Document
Partial and Simultaneous Transitive Orientations via Modular Decompositions
Abstract
A natural generalization of the recognition problem for a geometric graph class is the problem of extending a representation of a subgraph to a representation of the whole graph. A related problem is to find representations for multiple input graphs that coincide on subgraphs shared by the input graphs. A common restriction is the sunflower case where the shared graph is the same for each pair of input graphs. These problems translate to the setting of comparability graphs where the representations correspond to transitive orientations of their edges. We use modular decompositions to improve the runtime for the orientation extension problem and the sunflower orientation problem to linear time. We apply these results to improve the runtime for the partial representation problem and the sunflower case of the simultaneous representation problem for permutation graphs to linear time. We also give the first efficient algorithms for these problems on circular permutation graphs.
Cite as
Miriam Münch, Ignaz Rutter, and Peter Stumpf. Partial and Simultaneous Transitive Orientations via Modular Decompositions. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 51:1-51:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{munch_et_al:LIPIcs.ISAAC.2022.51,
author = {M\"{u}nch, Miriam and Rutter, Ignaz and Stumpf, Peter},
title = {{Partial and Simultaneous Transitive Orientations via Modular Decompositions}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {51:1--51:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.51},
URN = {urn:nbn:de:0030-drops-173369},
doi = {10.4230/LIPIcs.ISAAC.2022.51},
annote = {Keywords: representation extension, simultaneous representation, comparability graph, permutation graph, circular permutation graph, modular decomposition}
}
Document
Polynomial Threshold Functions for Decision Lists
Abstract
For S ⊆ {0,1}ⁿ a Boolean function f : S → {-1,1} is a polynomial threshold function (PTF) of degree d and weight W if there is a polynomial p with integer coefficients of degree d and with sum of absolute coefficients W such that f(x) = sign p(x) for all x ∈ S. We study a representation of decision lists as PTFs over Boolean cubes {0,1}ⁿ and over Hamming balls {0,1}ⁿ_{≤ k}.
As our first result, we show that for all d = O((n/(log n))^{1/3}) any decision list over {0,1}ⁿ can be represented by a PTF of degree d and weight 2^O(n/d²). This improves the result by Klivans and Servedio [Adam R. Klivans and Rocco A. Servedio, 2006] by a log² d factor in the exponent of the weight. Our bound is tight for all d = O((n/(log n))^{1/3}) due to the matching lower bound by Beigel [Richard Beigel, 1994].
For decision lists over a Hamming ball {0,1}ⁿ_{≤ k} we show that the upper bound on weight above can be drastically improved to n^O(√k) for d = Θ(√k). We also show that similar improvement is not possible for smaller degrees by proving the lower bound W = 2^Ω(n/d²) for all d = O(√k).
Cite as
Vladimir Podolskii and Nikolay V. Proskurin. Polynomial Threshold Functions for Decision Lists. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 52:1-52:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{podolskii_et_al:LIPIcs.ISAAC.2022.52,
author = {Podolskii, Vladimir and Proskurin, Nikolay V.},
title = {{Polynomial Threshold Functions for Decision Lists}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {52:1--52:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.52},
URN = {urn:nbn:de:0030-drops-173372},
doi = {10.4230/LIPIcs.ISAAC.2022.52},
annote = {Keywords: Threshold function, decision list, Hamming ball}
}
Document
Pop & Push: Ordered Tree Iteration in 𝒪(1)-Time
Abstract
The number of ordered trees (also known as plane trees) with n nodes is the (n-1)st Catalan number C_{n-1}. An ordered tree can be stored directly using nodes and pointers, or represented indirectly by a Dyck word. This paper presents a loopless algorithm for generating ordered trees with n nodes using pointer-based representations. In other words, we spend 𝒪(C_{n-1})-time to generate all of the trees, and moreover, the delay between consecutive trees is worst-case 𝒪(1)-time.
To achieve this run-time, each tree must differ from the previous by a constant amount. In other words, the algorithm must create a type of Gray code order. Our algorithm operates on the children of a node like a stack, by popping the first child off of one node’s stack and pushing the result onto another node’s stack. We refer to this pop-push operation as a pull, and consecutive trees in our order differ by one or two pulls. There is a simple two-case successor rule that determines the pulls to apply directly from the current tree. When converted to Dyck words, our rule corresponds to a left-shift, and these shift generate a cool-lex variant of lexicographic order.
Our results represent the first pull Gray code for ordered trees, and the first fully published loopless algorithm for ordered trees using pointer representations. More importantly, our algorithm is incredibly simple: A full implementation in C, including initialization and output, uses only three loops and three if-else blocks. Our work also establishes a simultaneous Gray code for Dyck words, ordered trees, and also binary trees, using cool-lex order.
Cite as
Paul Lapey and Aaron Williams. Pop & Push: Ordered Tree Iteration in 𝒪(1)-Time. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{lapey_et_al:LIPIcs.ISAAC.2022.53,
author = {Lapey, Paul and Williams, Aaron},
title = {{Pop \& Push: Ordered Tree Iteration in 𝒪(1)-Time}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {53:1--53:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.53},
URN = {urn:nbn:de:0030-drops-173380},
doi = {10.4230/LIPIcs.ISAAC.2022.53},
annote = {Keywords: combinatorial generation, Gray code, simultaneous Gray code, ordered trees, plane trees, Dyck words, binary trees, Catalan objects, loopless algorithm, cool-lex order}
}
Document
Popular Edges with Critical Nodes
Abstract
In the popular edge problem, the input is a bipartite graph G = (A ∪ B,E) where A and B denote a set of men and a set of women respectively, and each vertex in A∪ B has a strict preference ordering over its neighbours. A matching M in G is said to be popular if there is no other matching M' such that the number of vertices that prefer M' to M is more than the number of vertices that prefer M to M'. The goal is to determine, whether a given edge e belongs to some popular matching in G. A polynomial-time algorithm for this problem appears in [Cseh and Kavitha, 2018].
We consider the popular edge problem when some men or women are prioritized or critical. A matching that matches all the critical nodes is termed as a feasible matching. It follows from [Telikepalli Kavitha, 2014; Kavitha, 2021; Nasre et al., 2021; Meghana Nasre and Prajakta Nimbhorkar, 2017] that, when G admits a feasible matching, there always exists a matching that is popular among all feasible matchings.
We give a polynomial-time algorithm for the popular edge problem in the presence of critical men or women. We also show that an analogous result does not hold in the many-to-one setting, which is known as the Hospital-Residents Problem in literature, even when there are no critical nodes.
Cite as
Kushagra Chatterjee and Prajakta Nimbhorkar. Popular Edges with Critical Nodes. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{chatterjee_et_al:LIPIcs.ISAAC.2022.54,
author = {Chatterjee, Kushagra and Nimbhorkar, Prajakta},
title = {{Popular Edges with Critical Nodes}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {54:1--54:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.54},
URN = {urn:nbn:de:0030-drops-173399},
doi = {10.4230/LIPIcs.ISAAC.2022.54},
annote = {Keywords: Matching, Stable Matching, Popular feasible Matching}
}
Document
Proportional Allocation of Indivisible Goods up to the Least Valued Good on Average
Abstract
We study the problem of fairly allocating a set of indivisible goods to multiple agents and focus on the proportionality, which is one of the classical fairness notions. Since proportional allocations do not always exist when goods are indivisible, approximate notions of proportionality have been considered in the previous work. Among them, proportionality up to the maximin good (PROPm) has been the best approximate notion of proportionality that can be achieved for all instances. In this paper, we introduce the notion of proportionality up to the least valued good on average (PROPavg), which is a stronger notion than PROPm, and show that a PROPavg allocation always exists. Our results establish PROPavg as a notable non-trivial fairness notion that can be achieved for all instances. Our proof is constructive, and based on a new technique that generalizes the cut-and-choose protocol.
Cite as
Yusuke Kobayashi and Ryoga Mahara. Proportional Allocation of Indivisible Goods up to the Least Valued Good on Average. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 55:1-55:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{kobayashi_et_al:LIPIcs.ISAAC.2022.55,
author = {Kobayashi, Yusuke and Mahara, Ryoga},
title = {{Proportional Allocation of Indivisible Goods up to the Least Valued Good on Average}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {55:1--55:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.55},
URN = {urn:nbn:de:0030-drops-173402},
doi = {10.4230/LIPIcs.ISAAC.2022.55},
annote = {Keywords: Discrete Fair Division, Indivisible Goods, Proportionality}
}
Document
Pursuit-Evasion in Graphs: Zombies, Lazy Zombies and a Survivor
Abstract
We study zombies and survivor, a variant of the game of cops and robber on graphs. In this variant, the single survivor plays the role of the robber and attempts to escape from the zombies that play the role of the cops. The zombies are restricted, on their turn, to always follow an edge of a shortest path towards the survivor. Let z(G) be the smallest number of zombies required to catch the survivor on a graph G with n vertices. We show that there exist outerplanar graphs and visibility graphs of simple polygons such that z(G) = Θ(n). We also show that there exist maximum-degree-3 outerplanar graphs such that z(G) = Ω(n/log(n)).
Let z_L(G) be the smallest number of lazy zombies (zombies that can stay still on their turn) required to catch the survivor on a graph G. We show that lazy zombies are more powerful than normal zombies but less powerful than cops. We prove that z_L(G) ≤ 2 for connected outerplanar graphs and this bound is tight in the worst case. We show that z_L(G) ≤ k for connected graphs with treedepth k. This result implies that z_L(G) is at most (k+1)log n for connected graphs with treewidth k, O(√n) for connected planar graphs, O(√{gn}) for connected graphs with genus g and O(h√{hn}) for connected graphs with any excluded h-vertex minor. Our results on lazy zombies still hold when an adversary chooses the initial positions of the zombies.
Cite as
Prosenjit Bose, Jean-Lou De Carufel, and Thomas Shermer. Pursuit-Evasion in Graphs: Zombies, Lazy Zombies and a Survivor. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 56:1-56:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{bose_et_al:LIPIcs.ISAAC.2022.56,
author = {Bose, Prosenjit and De Carufel, Jean-Lou and Shermer, Thomas},
title = {{Pursuit-Evasion in Graphs: Zombies, Lazy Zombies and a Survivor}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {56:1--56:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.56},
URN = {urn:nbn:de:0030-drops-173418},
doi = {10.4230/LIPIcs.ISAAC.2022.56},
annote = {Keywords: Pursuit-evasion games, Outerplanar, Graphs, Treedepth, Treewidth}
}
Document
Range Updates and Range Sum Queries on Multidimensional Points with Monoid Weights
Abstract
Let P be a set of n points in ℝ^d where each point p ∈ P carries a weight drawn from a commutative monoid (ℳ, +, 0). Given a d-rectangle r_upd (i.e., an orthogonal rectangle in ℝ^d) and a value Δ ∈ ℳ, a range update adds Δ to the weight of every point p ∈ P∩ r_upd; given a d-rectangle r_qry, a range sum query returns the total weight of the points in P ∩ r_qry. The goal is to store P in a structure to support updates and queries with attractive performance guarantees. We describe a structure of Õ(n) space that handles an update in Õ(T_upd) time and a query in Õ(T_qry) time for arbitrary functions T_upd(n) and T_qry(n) satisfying T_upd ⋅ T_qry = n. The result holds for any fixed dimensionality d ≥ 2. Our query-update tradeoff is tight up to a polylog factor subject to the OMv-conjecture.
Cite as
Shangqi Lu and Yufei Tao. Range Updates and Range Sum Queries on Multidimensional Points with Monoid Weights. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 57:1-57:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{lu_et_al:LIPIcs.ISAAC.2022.57,
author = {Lu, Shangqi and Tao, Yufei},
title = {{Range Updates and Range Sum Queries on Multidimensional Points with Monoid Weights}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {57:1--57:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.57},
URN = {urn:nbn:de:0030-drops-173427},
doi = {10.4230/LIPIcs.ISAAC.2022.57},
annote = {Keywords: Range Updates, Range Sum Queries, Data Structures, Lower Bounds}
}
Document
Segment Visibility Counting Queries in Polygons
Abstract
Let P be a simple polygon with n vertices, and let A be a set of m points or line segments inside P. We develop data structures that can efficiently count the objects from A that are visible to a query point or a query segment. Our main aim is to obtain fast, O(polylog nm), query times, while using as little space as possible.
In case the query is a single point, a simple visibility-polygon-based solution achieves O(log nm) query time using O(nm²) space. In case A also contains only points, we present a smaller, O(n + m^{2+ε} log n)-space, data structure based on a hierarchical decomposition of the polygon.
Building on these results, we tackle the case where the query is a line segment and A contains only points. The main complication here is that the segment may intersect multiple regions of the polygon decomposition, and that a point may see multiple such pieces. Despite these issues, we show how to achieve O(log n log nm) query time using only O(nm^{2+ε} + n²) space. Finally, we show that we can even handle the case where the objects in A are segments with the same bounds.
Cite as
Kevin Buchin, Bram Custers, Ivor van der Hoog, Maarten Löffler, Aleksandr Popov, Marcel Roeloffzen, and Frank Staals. Segment Visibility Counting Queries in Polygons. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 58:1-58:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{buchin_et_al:LIPIcs.ISAAC.2022.58,
author = {Buchin, Kevin and Custers, Bram and van der Hoog, Ivor and L\"{o}ffler, Maarten and Popov, Aleksandr and Roeloffzen, Marcel and Staals, Frank},
title = {{Segment Visibility Counting Queries in Polygons}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {58:1--58:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.58},
URN = {urn:nbn:de:0030-drops-173431},
doi = {10.4230/LIPIcs.ISAAC.2022.58},
annote = {Keywords: Visibility, Data Structure, Polygons, Complexity}
}
Document
Shortest Beer Path Queries in Interval Graphs
Abstract
Our interest is in paths between pairs of vertices that go through at least one of a subset of the vertices known as beer vertices. Such a path is called a beer path, and the beer distance between two vertices is the length of the shortest beer path.
We show that we can represent unweighted interval graphs using 2n log n + O(n) + O(|B|log n) bits where |B| is the number of beer vertices. This data structure answers beer distance queries in O(log^ε n) time for any constant ε > 0 and shortest beer path queries in O(log^ε n + d) time, where d is the beer distance between the two nodes. We also show that proper interval graphs may be represented using 3n + o(n) bits to support beer distance queries in O(f(n)log n) time for any f(n) ∈ ω(1) and shortest beer path queries in O(d) time. All of these results also have time-space trade-offs.
Lastly we show that the information theoretic lower bound for beer proper interval graphs is very close to the space of our structure, namely log(4+2√3)n - o(n) (or about 2.9 n) bits.
Cite as
Rathish Das, Meng He, Eitan Kondratovsky, J. Ian Munro, Anurag Murty Naredla, and Kaiyu Wu. Shortest Beer Path Queries in Interval Graphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 59:1-59:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{das_et_al:LIPIcs.ISAAC.2022.59,
author = {Das, Rathish and He, Meng and Kondratovsky, Eitan and Munro, J. Ian and Naredla, Anurag Murty and Wu, Kaiyu},
title = {{Shortest Beer Path Queries in Interval Graphs}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {59:1--59:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.59},
URN = {urn:nbn:de:0030-drops-173442},
doi = {10.4230/LIPIcs.ISAAC.2022.59},
annote = {Keywords: Beer Path, Interval Graph}
}
Document
Simon’s Congruence Pattern Matching
Abstract
Testing Simon’s congruence asks whether two strings have the same set of subsequences of length no greater than a given integer. In the light of the recent discovery of an optimal linear algorithm for testing Simon’s congruence, we solve the Simon’s congruence pattern matching problem. The problem requires finding all substrings of a text that are congruent to a pattern under the Simon’s congruence. Our algorithm efficiently solves the problem in linear time in the length of the text by reusing results from previous computations with the help of new data structures called X-trees and Y-trees. Moreover, we define and solve variants of the Simon’s congruence pattern matching problem. They require finding the longest and shortest substring of the text as well as the shortest subsequence of the text which is congruent to the pattern under the Simon’s congruence. Two more variants which ask for the longest congruent subsequence of the text and optimizing the pattern matching problem are left as open problems.
Cite as
Sungmin Kim, Sang-Ki Ko, and Yo-Sub Han. Simon’s Congruence Pattern Matching. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 60:1-60:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{kim_et_al:LIPIcs.ISAAC.2022.60,
author = {Kim, Sungmin and Ko, Sang-Ki and Han, Yo-Sub},
title = {{Simon’s Congruence Pattern Matching}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {60:1--60:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.60},
URN = {urn:nbn:de:0030-drops-173456},
doi = {10.4230/LIPIcs.ISAAC.2022.60},
annote = {Keywords: pattern matching, Simon’s congruence, string algorithm, data structure}
}
Document
Simple Order-Isomorphic Matching Index with Expected Compact Space
Abstract
In this paper, we present a novel indexing method for the order-isomorphic pattern matching problem (also known as order-preserving pattern matching, or consecutive permutation matching), in which two equal-length strings are defined to match when X[i] < X[j] iff Y[i] < Y[j] for 0 ≤ i,j < |X|. We observe an interesting relation between the order-isomorphic matching and the insertion process of a binary search tree, based on which we propose a data structure which not only has a concise structure comprised of only two wavelet trees but also provides a surprisingly simple searching algorithm. In the average case analysis, the proposed method requires 𝒪(R(T)) bits, and it is capable of answering a count query in 𝒪(R(P)) time, and reporting an occurrence in 𝒪(lg |T|) time, where T and P are the text and the pattern string, respectively; for a string X, R(X) is the total time taken for the construction of the binary search tree by successively inserting the keys X[|X|-1],⋯,X[0] at the root, and its expected value is 𝒪(|X|lgσ) where σ is the alphabet size. Furthermore, the proposed method can be viewed as a generalization of some other methods including several heuristics and restricted versions described in previous studies in the literature.
Cite as
Sung-Hwan Kim and Hwan-Gue Cho. Simple Order-Isomorphic Matching Index with Expected Compact Space. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 61:1-61:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{kim_et_al:LIPIcs.ISAAC.2022.61,
author = {Kim, Sung-Hwan and Cho, Hwan-Gue},
title = {{Simple Order-Isomorphic Matching Index with Expected Compact Space}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {61:1--61:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.61},
URN = {urn:nbn:de:0030-drops-173466},
doi = {10.4230/LIPIcs.ISAAC.2022.61},
annote = {Keywords: Compact Data Structure, String Matching, Order-Preserving Matching, Suffix Array, FM-index, Binary Search Tree}
}
Document
Space-Efficient Graph Coarsening with Applications to Succinct Planar Encodings
Abstract
We present a novel space-efficient graph coarsening technique for n-vertex planar graphs G, called cloud partition, which partitions the vertices V(G) into disjoint sets C of size O(log n) such that each C induces a connected subgraph of G. Using this partition 𝒫 we construct a so-called structure-maintaining minor F of G via specific contractions within the disjoint sets such that F has O(n/log n) vertices. The combination of (F, 𝒫) is referred to as a cloud decomposition.
For planar graphs we show that a cloud decomposition can be constructed in O(n) time and using O(n) bits. Given a cloud decomposition (F, 𝒫) constructed for a planar graph G we are able to find a balanced separator of G in O(n/log n) time. Contrary to related publications, we do not make use of an embedding of the planar input graph. We generalize our cloud decomposition from planar graphs to H-minor-free graphs for any fixed graph H. This allows us to construct the succinct encoding scheme for H-minor-free graphs due to Blelloch and Farzan (CPM 2010) in O(n) time and O(n) bits improving both runtime and space by a factor of Θ(log n).
As an additional application of our cloud decomposition we show that, for H-minor-free graphs, a tree decomposition of width O(n^{1/2 + ε}) for any ε > 0 can be constructed in O(n) bits and a time linear in the size of the tree decomposition. A similar result by Izumi and Otachi (ICALP 2020) constructs a tree decomposition of width O(k √n log n) for graphs of treewidth k ≤ √n in sublinear space and polynomial time.
Cite as
Frank Kammer and Johannes Meintrup. Space-Efficient Graph Coarsening with Applications to Succinct Planar Encodings. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 62:1-62:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{kammer_et_al:LIPIcs.ISAAC.2022.62,
author = {Kammer, Frank and Meintrup, Johannes},
title = {{Space-Efficient Graph Coarsening with Applications to Succinct Planar Encodings}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {62:1--62:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.62},
URN = {urn:nbn:de:0030-drops-173478},
doi = {10.4230/LIPIcs.ISAAC.2022.62},
annote = {Keywords: planar graph, H-minor-free, space-efficient, separator, tree decomposition}
}
Document
Subquadratic Weighted Matroid Intersection Under Rank Oracles
Abstract
Given two matroids ℳ₁ = (V, ℐ₁) and ℳ₂ = (V, ℐ₂) over an n-element integer-weighted ground set V, the weighted matroid intersection problem aims to find a common independent set S^* ∈ ℐ₁ ∩ ℐ₂ maximizing the weight of S^*. In this paper, we present a simple deterministic algorithm for weighted matroid intersection using Õ(nr^{3/4} log{W}) rank queries, where r is the size of the largest intersection of ℳ₁ and ℳ₂ and W is the maximum weight. This improves upon the best previously known Õ(nr log{W}) algorithm given by Lee, Sidford, and Wong [FOCS'15], and is the first subquadratic algorithm for polynomially-bounded weights under the standard independence or rank oracle models. The main contribution of this paper is an efficient algorithm that computes shortest-path trees in weighted exchange graphs.
Cite as
Ta-Wei Tu. Subquadratic Weighted Matroid Intersection Under Rank Oracles. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 63:1-63:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{tu:LIPIcs.ISAAC.2022.63,
author = {Tu, Ta-Wei},
title = {{Subquadratic Weighted Matroid Intersection Under Rank Oracles}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {63:1--63:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.63},
URN = {urn:nbn:de:0030-drops-173485},
doi = {10.4230/LIPIcs.ISAAC.2022.63},
annote = {Keywords: Matroids, Weighted Matroid Intersection, Combinatorial Optimization}
}
Document
Subsequences with Gap Constraints: Complexity Bounds for Matching and Analysis Problems
Abstract
We consider subsequences with gap constraints, i. e., length-k subsequences p that can be embedded into a string w such that the induced gaps (i. e., the factors of w between the positions to which p is mapped to) satisfy given gap constraints gc = (C_1, C_2, …, C_{k-1}); we call p a gc-subsequence of w. In the case where the gap constraints gc are defined by lower and upper length bounds C_i = (L^-_i, L^+_i) ∈ ℕ² and/or regular languages C_i ∈ REG, we prove tight (conditional on the orthogonal vectors (OV) hypothesis) complexity bounds for checking whether a given p is a gc-subsequence of a string w. We also consider the whole set of all gc-subsequences of a string, and investigate the complexity of the universality, equivalence and containment problems for these sets of gc-subsequences.
Cite as
Joel D. Day, Maria Kosche, Florin Manea, and Markus L. Schmid. Subsequences with Gap Constraints: Complexity Bounds for Matching and Analysis Problems. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 64:1-64:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{day_et_al:LIPIcs.ISAAC.2022.64,
author = {Day, Joel D. and Kosche, Maria and Manea, Florin and Schmid, Markus L.},
title = {{Subsequences with Gap Constraints: Complexity Bounds for Matching and Analysis Problems}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {64:1--64:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.64},
URN = {urn:nbn:de:0030-drops-173493},
doi = {10.4230/LIPIcs.ISAAC.2022.64},
annote = {Keywords: String algorithms, subsequences with gap constraints, pattern matching, fine-grained complexity, conditional lower bounds, parameterised complexity}
}
Document
Succinct List Indexing in Optimal Time
Abstract
An indexed list supports (efficient) access to both the offsets and the items of an arbitrarily ordered set under the effect of insertions and deletions. Existing solutions are engaged in a space-time trade-off. On the one hand, time efficient solutions are composed as a package of data structures: a linked-list, a hash table and a tree-type structure to support indexing. This arrangement observes a memory commitment that is outside the information theoretic lower bound (for ordered sets) by a factor of 12. On the other hand, the memory lower bound can be satisfied, up to an additive lower order term, trivially with an array. However, operations incur time costs proportional to the length of the array.
We revisit the list indexing problem by attempting to balance the competing demands of space and time efficiency. We prepare the first succinct indexed list that supports efficient query and update operations. To implement an ordered set of size n, drawn from the universe {1, …, m}, the solution occupies n(log m + o(log n)) bits (with high probability) and admits all operations optimally in 𝒪(log n/log log n) time.
Cite as
William L. Holland. Succinct List Indexing in Optimal Time. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 65:1-65:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{holland:LIPIcs.ISAAC.2022.65,
author = {Holland, William L.},
title = {{Succinct List Indexing in Optimal Time}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {65:1--65:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.65},
URN = {urn:nbn:de:0030-drops-173506},
doi = {10.4230/LIPIcs.ISAAC.2022.65},
annote = {Keywords: Succinct Data Structures, Lists, Dynamic Data Structures}
}
Document
Super-Cubic Lower Bound for Generalized Karchmer-Wigderson Games
Abstract
In this paper, we prove a super-cubic lower bound on the size of a communication protocol for generalized Karchmer-Wigderson game for an explicit function f: {0,1}ⁿ → {0,1}^{log n}. Lower bounds for original Karchmer-Wigderson games correspond to De Morgan formula lower bounds, thus the best known size lower bound is cubic. The generalized Karchmer-Wigderson games are similar to the original ones, so we hope that our approach can provide an insight for proving better lower bounds on the original Karchmer-Wigderson games, and hence for proving new lower bounds on De Morgan formula size.
To achieve super-cubic lower bound we adapt several techniques used in formula complexity to communication protocols, prove communication complexity lower bound for a composition of several functions with a multiplexer relation, and use a technique from [Ivan Mihajlin and Alexander Smal, 2021] to extract the "hardest" function from it. As a result, in this setting we are able to show that there is a relatively small set of functions such that at least one of them does not have a small protocol. The resulting lower bound of Ω̃(n^3.156) is significantly better than the bound obtained from the counting argument.
Cite as
Artur Ignatiev, Ivan Mihajlin, and Alexander Smal. Super-Cubic Lower Bound for Generalized Karchmer-Wigderson Games. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 66:1-66:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{ignatiev_et_al:LIPIcs.ISAAC.2022.66,
author = {Ignatiev, Artur and Mihajlin, Ivan and Smal, Alexander},
title = {{Super-Cubic Lower Bound for Generalized Karchmer-Wigderson Games}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {66:1--66:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.66},
URN = {urn:nbn:de:0030-drops-173510},
doi = {10.4230/LIPIcs.ISAAC.2022.66},
annote = {Keywords: communication complexity, circuit complexity, Karchmer-Wigderson games}
}
Document
The Dispersive Art Gallery Problem
Abstract
We introduce a new variant of the art gallery problem that comes from safety issues. In this variant we are not interested in guard sets of smallest cardinality, but in guard sets with largest possible distances between these guards. To the best of our knowledge, this variant has not been considered before. We call it the Dispersive Art Gallery Problem. In particular, in the dispersive art gallery problem we are given a polygon 𝒫 and a real number 𝓁, and want to decide whether 𝒫 has a guard set such that every pair of guards in this set is at least a distance of 𝓁 apart.
In this paper, we study the vertex guard variant of this problem for the class of polyominoes. We consider rectangular visibility and distances as geodesics in the L₁-metric. Our results are as follows. We give a (simple) thin polyomino such that every guard set has minimum pairwise distances of at most 3. On the positive side, we describe an algorithm that computes guard sets for simple polyominoes that match this upper bound, i.e., the algorithm constructs worst-case optimal solutions. We also study the computational complexity of computing guard sets that maximize the smallest distance between all pairs of guards within the guard sets. We prove that deciding whether there exists a guard set realizing a minimum pairwise distance for all pairs of guards of at least 5 in a given polyomino is NP-complete.
We were also able to find an optimal dynamic programming approach that computes a guard set that maximizes the minimum pairwise distance between guards in tree-shaped polyominoes, i.e., computes optimal solutions; due to space constraints, details can be found in the full version of our paper [Christian Rieck and Christian Scheffer, 2022]. Because the shapes constructed in the NP-hardness reduction are thin as well (but have holes), this result completes the case for thin polyominoes.
Cite as
Christian Rieck and Christian Scheffer. The Dispersive Art Gallery Problem. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 67:1-67:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{rieck_et_al:LIPIcs.ISAAC.2022.67,
author = {Rieck, Christian and Scheffer, Christian},
title = {{The Dispersive Art Gallery Problem}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {67:1--67:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.67},
URN = {urn:nbn:de:0030-drops-173522},
doi = {10.4230/LIPIcs.ISAAC.2022.67},
annote = {Keywords: Art gallery, dispersion, polyominoes, NP-completeness, r-visibility, vertex guards, L₁-metric, worst-case optimal}
}