News

Aalto computer scientists in ICALP 2024

Published: 1.7.2024

Five papers from the Department of Computer Science were accepted to International Colloquium on Automata, Languages, and Programming (ICALP).

Artistic illustration: Algorithms over a computer chip

The 51st EATCS International Colloquium on Automata, Languages, and Programming (ICALP) is held in Tallinn on 8-12 July, 2024. ICALP is the main conference and annual meeting of the European Association for Theoretical Computer Science (EATCS).

ICALP 2024

Accepted papers

In alphabetical order. Click the title to see the authors and the abstract.

Authors

Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak, Akash Pareek, Sorrachai Yingchareonthawornchai

Abstract

The access lemma (Sleator and Tarjan, JACM 1985) is a property of binary search trees that implies interesting consequences such as static optimality, static finger, and working set property. However, there are known corollaries of the dynamic optimality that cannot be derived via the access lemma, such as the dynamic finger, and any o(logn)-competitive ratio to the optimal BST where n is the number of keys.
In this paper, we introduce the group access bound that can be defined with respect to a reference group access tree. Group access bounds generalize the access lemma and imply properties that are far stronger than those implied by the access lemma. For each of the following results, there is a group access tree whose group access bound
Is O(logn‾‾‾‾‾√)-competitive to the optimal BST.
Achieves the k-finger bound with an additive term of O(mlogkloglogn) (randomized) when the reference tree is an almost complete binary tree.
Satisfies the unified bound with an additive term of O(mloglogn).
Matches the unified bound with a time window k with an additive term of O(mlogkloglogn) (randomized).
Furthermore, we prove simulation theorem: For every group access tree, there is an online BST algorithm that is O(1)-competitive with its group access bound. In particular, any new group access bound will automatically imply a new BST algorithm achieving the same bound. Thereby, we obtain an improved k-finger bound (reference tree is an almost complete binary tree), an improved unified bound with a time window k, and matching the best-known bound for Unified bound in the BST model. Since any dynamically optimal BST must achieve the group access bounds, we believe our results provide a new direction towards proving o(logn)-competitiveness of Splay tree and Greedy.

Link to the paper

Authors

Andreas Björklund, Petteri Kaski, Jesper Nederlof

Abstract

Finding a Hamiltonian cycle in a given graph is computationally challenging, and in general remains so even when one is further given one Hamiltonian cycle in the graph and asked to find another. In fact, no significantly faster algorithms are known for finding another Hamiltonian cycle than for finding a first one even in the setting where another Hamiltonian cycle is structurally guaranteed to exist, such as for odd-degree graphs. We identify a graph class -- the bipartite Pfaffian graphs of minimum degree three -- where it is NP-complete to decide whether a given graph in the class is Hamiltonian, but when presented with a Hamiltonian cycle as part of the input, another Hamiltonian cycle can be found efficiently.
We prove that Thomason's lollipop method~[Ann.~Discrete Math.,~1978], a well-known algorithm for finding another Hamiltonian cycle, runs in a linear number of steps in cubic bipartite Pfaffian graphs. This was conjectured for cubic bipartite planar graphs by Haddadan [MSc~thesis,~Waterloo,~2015]; in contrast, examples are known of both cubic bipartite graphs and cubic planar graphs where the lollipop method takes exponential time.
Beyond the lollipop method, we address a slightly more general graph class and present two algorithms, one running in linear-time and one operating in logarithmic space, that take as input (i) a bipartite Pfaffian graph G of minimum degree three, (ii) a Hamiltonian cycle H in G, and (iii) an edge e in H, and output at least three other Hamiltonian cycles through the edge e in G.
We also present further improved algorithms for finding optimal traveling salesperson tours and counting Hamiltonian cycles in bipartite planar graphs with running times that are not known to hold in general planar graphs.

Link to the paper

Authors

Fateme Abbasi, Sandip Banerjee, Jarosław Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, Joachim Spoerhase

Abstract

We consider the well-studied Robust (k,z)-Clustering problem, which generalizes the classic k-Median, k-Means, and k-Center problems. Given a constant z≥1, the input to Robust (k,z)-Clustering is a set P of n weighted points in a metric space (M,δ) and a positive integer k. Further, each point belongs to one (or more) of the m many different groups S1,S2,…,Sm. Our goal is to find a set X of k centers such that maxi∈[m]∑p∈Siw(p)δ(p,X)z is minimized.
This problem arises in the domains of robust optimization [Anthony, Goyal, Gupta, Nagarajan, Math. Oper. Res. 2010] and in algorithmic fairness. For polynomial time computation, an approximation factor of O(logm/loglogm) is known [Makarychev, Vakilian, COLT 2021], which is tight under a plausible complexity assumption even in the line metrics. For FPT time, there is a (3z+ϵ)-approximation algorithm, which is tight under GAP-ETH [Goyal, Jaiswal, Inf. Proc. Letters, 2023].
Motivated by the tight lower bounds for general discrete metrics, we focus on \emph{geometric} spaces such as the (discrete) high-dimensional Euclidean setting and metrics of low doubling dimension, which play an important role in data analysis applications. First, for a universal constant η0>0.0006, we devise a 3z(1−η0)-factor FPT approximation algorithm for discrete high-dimensional Euclidean spaces thereby bypassing the lower bound for general metrics. We complement this result by showing that even the special case of k-Center in dimension Θ(logn) is (3/2‾‾‾√−o(1))-hard to approximate for FPT algorithms. Finally, we complete the FPT approximation landscape by designing an FPT (1+ϵ)-approximation scheme (EPAS) for the metric of sub-logarithmic doubling dimension.

Link to the paper

Authors

Esther Galby, Sandor Kisfaludi-Bak, Daniel Marx, Roohani Sharma

Abstract

In the Directed Steiner Network problem, the input is a directed graph G, a subset T of k vertices of G called the terminals, and a demand graph D on T. The task is to find a subgraph H of G with the minimum number of edges such that for every edge (s,t) in D, the solution H contains a directed s to t path. In this paper we investigate how the complexity of the problem depends on the demand pattern when G is planar. Formally, if \mathcal{D} is a class of directed graphs closed under identification of vertices, then the \mathcal{D}-Steiner Network (\mathcal{D}-SN) problem is the special case where the demand graph D is restricted to be from \mathcal{D}. For general graphs, Feldmann and Marx [ICALP 2016] characterized those families of demand graphs where the problem is fixed-parameter tractable (FPT) parameterized by the number k of terminals. They showed that if \mathcal{D} is a superset of one of the five hard families, then \mathcal{D}-SN is W[1]-hard parameterized by k, otherwise it can be solved in time f(k)n^{O(1)}.
For planar graphs an interesting question is whether the W[1]-hard cases can be solved by subexponential parameterized algorithms. Chitnis et al. [SICOMP 2020] showed that, assuming the ETH, there is no f(k)n^{o(k)} time algorithm for the general \mathcal{D}-SN problem on planar graphs, but the special case called Strongly Connected Steiner Subgraph can be solved in time f(k) n^{O(\sqrt{k})} on planar graphs. We present a far-reaching generalization and unification of these two results: we give a complete characterization of the behavior of every -SN problem on planar graphs. We show that assuming ETH, either the problem is (1) solvable in time 2^{O(k)}n^{O(1)}, and not in time 2^{o(k)}n^{O(1)}, or (2) solvable in time f(k)n^{O(\sqrt{k})}, but not in time f(k)n^{o(\sqrt{k})}, or (3) solvable in time f(k)n^{O(k)}, but not in time f(k)n^{o({k})}.

Link to the paper

Authors

Augusto Modanese, Yuichi Yoshida

Abstract

Inspired by the works of Goldreich and Ron (J. ACM, 2017) and Nakar and Ron (ICALP, 2021), we initiate the study of property testing in dynamic environments with arbitrary topologies. Our focus is on the simplest non-trivial rule that can be tested, which corresponds to the 1-BP rule of bootstrap percolation and models a simple spreading behavior: Every "infected" node stays infected forever, and each "healthy" node becomes infected if and only if it has at least one infected neighbor. We show various results for both the case where we test a single time step of evolution and where the evolution spans several time steps. In the first, we show that the worst-case query complexity is O(Δ/ε) or Õ (n‾√/ε) (whichever is smaller), where Δ and n are the maximum degree of a node and number of vertices, respectively, in the underlying graph, and we also show lower bounds for both one- and two-sided error testers that match our upper bounds up to Δ=o(n‾√) and Δ=O(n1/3), respectively. In the second setting of testing the environment over T time steps, we show upper bounds of O(ΔT−1/εT) and Õ (|E|/εT), where E is the set of edges of the underlying graph. All of our algorithms are one-sided error, and all of them are also time-conforming and non-adaptive, with the single exception of the more complex Õ (n‾√/ε)-query tester for the case T=2.