ARCO

Welcome to the 32nd ARCO workshop on 22 November in Malmö.

The event will take place in Auditorium AS:306, "Allmänna sjukhuset", Jan Waldenströms gata 25, 214 28 Malmö.
To get there, get off the commuter train at station "Triangeln", the second stop on the Swedish side if you come from Denmark. Then walk south for about 10 minutes until you reach Jan Waldenströms gata 25.

Programme

09.00 - 10.00 Coffee and mingle

Chair: Thore Husfeldt
10.00 - 10.20 Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More, Tuukka Korhonen
10.20 - 10.40 Revisiting Local Computation of PageRank: Simple and Optimal, Hanzhi Wang
10.40-11.00 Monotone Bounded-Depth Complexity of Homomorphism Polynomials, Prateek Dwivedi

11.00-11.10 Paus

Chair: Valentin Polishchuk
11.10-11.30 Hitting all longest paths in H-free graphs, Amir Nikabadi
11.30-11.50 Local Correction of Low Degree Polynomials, Amik Raj Behera
11.50-12.10 An Optimal Randomized Algorithm for Finding the Saddlepoint, Frederik Haagensen
12.10-12.30 Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems, Lars Rohwedder

12.30-13.30 Lunch

13.30-14-00 Business meeting

Chair: Suzanna Rezende
14,00-14.20 Online Bin Covering with Frequency Predictions, Magnus Berg
14.20-14.40 LPS via LCS, Rolf Fagerberg
14.40-15.00 Pure Binary Finger Search Trees, Casper Rysgaard

15.00-15.30 Coffee

Chair: Kim Skak Larsen
15.30-15.50 A New Perspective on Adaptive Sorting Based on Persistence, Jens Kristian Refsgaard Schou
15.50-16.10 Sweeping a Domain with Line-of-Sight Between Covisible Agents, Kien C. Huynh
16.10-16.30 An Improved Lower Bound on the Number of Pseudoline Arrangements, Justin Dallant

18.30 Dinner

Lars Rohwedder

Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems

We consider the problem of finding a basis of a matroid with weight exactly equal to a given target. Here weights can be discrete values from {-Delta,...,Delta} or more generally m-dimensional vectors of such discrete values. We resolve the parameterized complexity completely, by presenting an FPT algorithm parameterized by Delta and m for arbitrary matroids. Prior to our work, no such algorithms were known even when weights are in {0,1}, or arbitrary Delta and m=1. Our main technical contributions are new proximity and sensitivity bounds for matroid problems, independent of the number of elements. These bounds imply FPT algorithms via matroid intersection. Joint work with Friedrich Eisenbrand and Karol Węgrzycki.

Jens Kristian Refsgaard Schou

PersiSort: A New Perspective on Adaptive Sorting Based on Persistence

Adaptive sorting exploits the structure of a partially sorted list---in particular, the sorted segments of a list called runs---to improve its performance.
Persistent homology, on the other hand, is a topological data analysis tool that captures a space's topological features at different scales.
In this paper, we combine these two seemingly unrelated concepts and introduce a new perspective on adaptive sorting.

We introduce a new stable sorting algorithm, referred to as the Persistence Sort (or PersiSort in short), which utilizes the persistence pairs among the local extrema of a list.
Given a list of $n$ elements containing $r$ runs with run entropy $H$, we prove, for the first time, that any adaptive sorting algorithm that uses the two-way-merge subroutine (AdaptMerge) of Carlsson \etal~(1990) performs $\Oh{nH}=\Oh{n\log r}$ comparisons to merge precomputed runs based on its predetermined merge policy, and is therefore worst-case optimal.
Using PersiSort, we then provide a new way to analyze adaptive sorting with a persistence-based arrangement of runs.

Unlike previous work such as PowerSort and TimSort, PersiSort does not consider the number of elements in each run but the values of elements in the sorting process.
We finally discuss the scenarios when PersiSort outperforms several state-of-the-art adaptive sorting algorithms.

Magnus Berg

Online Bin Covering with Frequency Predictions

We study the bin covering problem where a multiset of items from a fixed set S ⊆ (0,1] must be split into disjoint subsets while maximizing the number of subsets whose contents sum to at least 1. We focus on the online discrete variant, where S is finite, and items arrive sequentially. In the purely online setting, we show that the competitive ratios of best deterministic (and randomized) algorithms converge to 1/2 for large S, similar to the continuous setting. Therefore, we consider the problem under the prediction setting, where algorithms may access a vector of frequencies predicting the frequency of items of each size in the instance. In this setting, we introduce a family of online algorithms that perform near-optimally when the predictions are correct. Further, we introduce a second family of more robust algorithms that presents a tradeoff between the performance guarantees when the predictions are perfect and when predictions are adversarial. Finally, we consider a stochastic setting where items are drawn independently from any fixed but unknown distribution of S. Using results from the PAC-learnability of probabilities in discrete distributions, we introduce a purely online algorithm whose average-case performance is near-optimal with high probability for all finite sets S and all distributions of S.

Kien C. Huynh

Sweeping a Domain with Line-of-Sight Between Covisible Agents

We consider sweeping a polygonal domain using variable-length segments whose endpoints can be considered to be mobile agents moving with bounded speeds; a point in the domain is swept when it belongs to one of the segments. The objective is to sweep the domain as quickly as possible. We show that the problem is NP-hard even in simple polygons and even for a single segment (two agents), and give constant-factor approximation algorithms, both for simple polygons and polygons with holes.
Our approximations are obtained by introducing a new type of "window partition" of the polygon, which may find other applications. For domains with holes, our results are based on a non-trivial topological argument proving a surprising fact: a connected subset of the domain, whose points are not traced by the agents, may contain at most one hole.

Casper Rysgaard

Pure Binary Finger Search Trees

We present dynamic binary search trees where each node only stores a value and pointers to its parent and its children. We denote such binary search trees pure binary search trees. Our structure supports finger searches in worst-case $O(\lg d)$ time, where $d$ is the rank difference between the node given by the finger and the node found by the search. Inserting a new node with a successor or predecessor value for a node pointed to by a finger and deleting a node in the tree pointed to by a finger are supported in amortized $O(1)$ time and worst-case $O(\lg n)$ time, where $n$ is the number of nodes in the tree. The temporary working space during the operations is $O(1)$ words.
The result is obtained by an alternative representation of the red-black trees by Guibas and Sedgewick [FOCS 1978] that encodes bits of information in the tree structure, generalizing the encoding of 2-3-trees by Brown [IPL 1979], and rearranging the nodes in a red-black tree ("folding" left and right paths) such that the predecessor and successor of a node can always be found in worst-case constant time. The same time bounds can easily be obtained by, say, red-black trees and AVL trees augmented with pointers to the predecessor and successor of each node. The novelty of our result is that we store no extra information than the binary tree structure. The structure can be represented by two pointers per value, i.e., the same representation as a doubly linked list.

Rolf Fagerberg

LPS via LCS

Two standard textbook problems illustrating dynamic programming are to find the longest common subsequence (LCS) of two strings and to find the longest palindromic subsequence (LPS) of a single string. A popular claim is that the LPS of a string can be computed as the LCS of the string and its reversal. We investigate the correctness of this claim.

Tuukka Korhonen

Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More

The k-edge-connected components of a graph are defined by putting two vertices u and v into the same component if they cannot be separated from each other by cutting less than k edges (it can be shown that this is indeed an equivalence relation among the vertices). We give an algorithm for computing the k-edge-connected components of a given graph that works in linear-time when k is any constant, solving a long-standing problem in graph algorithms. We also give linear-time algorithms for other problems about finding edge cuts or vertex separators of size less than k and decomposing a graph along them.

Amik Raj Behera

Local Correction of Low-Degree Polynomials

Local correction refers to the algorithmic task of recovering a local piece of information about a codeword from its corrupted version, and the challenge is to do this by making very few queries to the corrupted codeword.
Evaluations of low-degree polynomials over finite fields form a code with good properties and have been studied extensively. In our work, we consider the setting where low-degree polynomials are over product sets and not over a vector space. Without the rich algebraic properties of vector spaces, the task of local correction becomes significantly difficult and requires new approaches, more combinatorial in flavor.

We will see the results regarding local (list) correction and see a couple of combinatorial tasks that we understand in the way to design these algorithms. This is based on a joint work with Prashanth Amireddy, Manaswi Paraashar, Srikanth Srinivasan, and Madhu Sudan.

Low Degree Local Correction Over the Boolean Cube

Hanzhi Wang

Revisiting Local Computation of PageRank: Simple and Optimal

PageRank is an important graph analysis metric, initially proposed by the founders of Google to compute the importance ranking of web pages on the Google search engine. In 2007, Reid Andersen, Christian Borgs, Jennifer Chayes, John E. Hopcroft, Vahab S. Mirrokni, and Shang-Hua Teng began studying the problem of computing PageRank contributions on large graphs, i.e., given a target node t in a graph, finding all nodes in the graph that significantly affect the PageRank score of t. They jointly proposed the ApproxContributions algorithm, which uses local search on large graphs to compute these PageRank contributions. Since its proposal, the ApproxContributions algorithm has received widespread attention and has become a cornerstone algorithm for PageRank computation, with various modifications widely applied to a variety of graph analysis problems. However, the ApproxContributions algorithm has long lacked meaningful analytical results regarding worst-case computational complexity.

In this talk, I will revisit the ApproxContributions algorithm and present a concise analysis establishing an optimal upper bound on its worst-case time complexity under the arc-centric graph-access model. Furthermore, I will discuss how our optimal analysis of ApproxContributions helps bridge the longstanding theoretical gap between the upper and lower bounds on the time complexity for computing single-node PageRank, a crucial query problem in PageRank computation.

This is based on joint work with Zhewei Wei, Ji-Rong Wen, and Mingji Yang.

Prateek Dwivedi

Monotone Bounded-Depth Complexity of Homomorphism Polynomials

For every fixed graph H, it is known that homomorphism counts from H and colourful H-subgraph counts can be determined in O(n^{t+1}) time on n-vertex input graphs G, where t is the treewidth of H. On the other hand, a running time of n^{o(t / \log t)} would refute the exponential-time hypothesis. Komarath et al. studied algebraic variants of these counting problems, i.e., homomorphism and subgraph polynomials for fixed graphs H. In recent work, we characterize the power of monotone bounded-depth circuits for homomorphism and colourful subgraph polynomials. This leads us to a natural hierarchy of graph parameters, which capture the width of tree decompositions for H when the underlying tree is required to have depth at most \Delta. We prove monotone circuit lower bounds for product-depth \Delta circuits computing homomorphism polynomial for H. This allows us to derive an optimal depth hierarchy theorem for monotone bounded-depth circuits through graph-theoretic arguments.

Frederik Haagensen

An Optimal Randomized Algorithm for Finding the Saddlepoint

A saddlepoint of an n × n matrix is an entry that is the maximum of its row and the minimum
of its column. Saddlepoints give the value of a two-player zero-sum game, corresponding to its
pure-strategy Nash equilibria; efficiently finding a saddlepoint is thus a natural and fundamental
algorithmic task.
For finding a strict saddlepoint (an entry that is the strict maximum of its row and the strict
minimum of its column) we recently gave an O(n log∗ n)-time algorithm, improving the O(n log n)
bounds from 1991 of Bienstock, Chung, Fredman, Schäffer, Shor, Suri and of Byrne and Vaserstein.
In this paper, we present an optimal O(n)-time algorithm for finding a strict saddlepoint based on
random sampling. Our algorithm, like earlier approaches, accesses matrix entries only via unit-cost
binary comparisons. For finding a (non-strict) saddlepoint, we extend an existing lower bound to
randomized algorithms, showing that the trivial O(n^2) runtime cannot be improved even with the
use of randomness

Amir Nikabadi

Hitting all longest paths in H-free graphs

Under what conditions does a connected graph G have a vertex that intersects all of its longest paths? This question has been resolved for certain graph families, including split graphs, graphs of treewidth at most 2, and graphs of matching numbers at most 3. However, it is still unclear whether other graphs characterized by a finite set of forbidden induced subgraphs yield a positive answer to this question.

I will try to prove that if G is a connected graph that does not contain any of the following as an induced subgraph:
(i) K_{1,3} together with a graph H of size at most 5, or
(ii) P_5 along with any of the following graphs: triangle, paw, or diamond,
then G admits a vertex intersecting all of its longest paths.

Based on a joint work with Paloma T. Lima.

Justin Dallant

An Improved Lower Bound on the Number of Pseudoline Arrangements

Arrangements of pseudolines are classic objects in discrete and computational geometry. They have been studied with increasing intensity since their introduction almost 100 years ago. The study of the number B_n of non-isomorphic simple arrangements of n pseudolines goes back to Goodman and Pollack, Knuth, and others. It is known that Bn is in the order of 2^Θ(n^2) and finding asymptotic bounds on b_n=log_2(Bn)/n^2 remains a challenging task. In 2011, Felsner and Valtr showed that 0.1887≤b_n≤0.6571 for sufficiently large n. The upper bound remains untouched but in 2020 Dumitrescu and Mandal improved the lower bound constant to 0.2083. Their approach utilizes the known values of B_n for up to n=12.

We tackle the lower bound by utilizing dynamic programming and the Lindström-Gessel-Viennot lemma. Our new bound is b_n≥0.2721 for sufficiently large n. The result is based on a delicate interplay of theoretical ideas and computer assistance.

• Jacob Holm, DIKU
• Inge Li Gørtz, DTU
• Thore Husfeldt, ITU
• Susanna Rezende, LU
• Bengt J. Nilsson (Captain), Malmö
• Kim Skak Larsen, SDU