ABSTRACT. The \emph{weighted ancestor} problem on a rooted node-weighted tree $T$ is a generalization of the classic \emph{predecessor} problem: construct a data structure for a set of integers that supports fast predecessor queries. Both problems are known to require $\Omega(\log\log n)$ time for queries provided $\cO(n\text{ poly} \log n)$ space is available, where $n$ is the input size. The weighted ancestor problem has attracted a lot of attention by the combinatorial pattern matching community due to its direct application to suffix trees. In this formulation of the problem, the nodes are weighted by string depth. This attention has culminated in a data structure for weighted ancestors in suffix trees with $\cO(1)$ query time and an $\cO(n)$-time construction algorithm [Belazzougui et al., CPM 2021].

In this paper, we consider a different version of the weighted ancestor problem, where the nodes are weighted by any function $\weight$ that maps the nodes of $T$ to positive integers, such that $\weight(u)\le \size(u)$ for any node $u$ and $\weight(u_1)\le \weight(u_2)$ if node $u_1$ is a descendant of node $u_2$, where $\size(u)$ is the number of nodes in the subtree rooted at $u$. In the \emph{size-constrained weighted ancestor} (\SWAQp) problem, for any node $u$ of $T$ and any integer $k$, we are asked to return the lowest ancestor $w$ of $u$ with weight at least $k$. We show that for \emph{any rooted tree} with $n$ nodes, we can locate node $w$ in $\cO(1)$ time after $\cO(n)$-time preprocessing. In particular, this implies a data structure for the \SWAQp problem in suffix trees with $\cO(1)$ query time and $\cO(n)$-time preprocessing, when the nodes are weighted by $\weight$. We also show several string-processing applications of this result.

ABSTRACT. Given an undirected weighted graph, an (approximate) distance oracle is a data structure that can (approximately) answer distance queries. A {\em Path-Reporting Distance Oracle}, or {\em PRDO}, is a distance oracle that must also return a path between the queried vertices. Given a graph on $n$ vertices and an integer parameter $k\ge 1$, \cite{TZ01} showed a PRDO with stretch $2k-1$, size $O(k\cdot n^{1+1/k})$ and query time $O(k)$ (for the query time of PRDOs, we omit the time needed to report the path itself). Subsequent works \cite{MN06,C14,C15} improved the size to $O(n^{1+1/k})$ and the query time to $O(1)$. However, these improvements produce distance oracles which are not path-reporting. Several other works \cite{ENW16,EP15} focused on small size PRDO for general graphs, but all known results on distance oracles with linear size suffer from polynomial stretch, polynomial query time, or not being path-reporting.

In this paper we devise the first linear size PRDO with poly-logarithmic stretch and low query time $O(\log\log n)$. More generally, for any integer $k\ge 1$, we obtain a PRDO with stretch at most $O(k^{4.82})$, size $O(n^{1+1/k})$, and query time $O(\log k)$. In addition, we can make the size of our PRDO as small as $n+o(n)$, at the cost of increasing the query time to poly-logarithmic. For unweighted graphs, we improve the stretch to $O(k^2)$.

We also consider {\em pairwise PRDO}, which is a PRDO that is only required to answer queries from a given set of pairs ${\cal P}$. An exact PRDO of size $O(n+|{\cal P}|^2)$ and constant query time was shown in \cite{EP15}. In this work we dramatically improve the size, at the cost of slightly increasing the stretch. Specifically, given any $\epsilon>0$, we devise a pairwise PRDO with stretch $1+\epsilon$, constant query time, and near optimal size $n^{o(1)}\cdot (n+|{\cal P}|)$.

ABSTRACT. Chordal graphs is a well-studied large graph class that is also a strict super-class of path graphs. Munro and Wu (ISAAC 2018) have given an $(n^2/4+o(n^2))-$bit succinct representation for $n-$vertex unlabeled chordal graphs. A chordal graph $G=(V,E)$ is the intersection graph of sub-trees of a tree $T$. Based on this characterization, the two parameters of chordal graphs which we consider in this work are \textit{leafage}, introduced by Lin, McKee and West (Discussiones Mathematicae Graph Theory 1998) and \textit{vertex leafage}, introduced by Chaplick and Stacho (Discret. Appl. Math. 2014). Leafage is the minimum number of leaves in any possible tree $T$ characterizing $G$. Let $L(u)$ denote the number of leaves of the sub-tree in $T$ corresponding to $u \in V$ and $k=\max\limits_{u \in V} L(u)$. The smallest $k$ for which there exists a tree $T$ for $G$ is called its vertex leafage.

In this work, we improve the worst-case information theoretic lower bound of Munro and Wu (ISAAC 2018) for unlabeled chordal graphs when vertex leafage is bounded and leafage is unbounded. The class of unlabeled $k-$vertex leafage chordal graphs that consists of all chordal graphs with vertex leafage at most $k$ and unbounded leafage, denoted $\mathcal{G}_k$, is introduced for the first time. For $k>1$ in $o(n/\log n)$, we obtain a lower bound of $((k-1)n \log n -kn \log k - O(\log n))-$bits on the size of any data structure that encodes a graph in $\mathcal{G}_k$. Further, for every $k-$vertex leafage chordal graph $G$ such that $k>1$ in $o(n/\log n)$, we present a $((k-1)n \log n + o(kn \log n))-$bit data structure, constructed using the succinct data structure for path graphs with $kn/2$ vertices. Our data structure supports adjacency query in $O(k \log n)$ time and using additional $2n \log n$ bits, an $O(k^2 d_v \log n + \log^2 n)$ time neighbourhood query where $d_v$ is degree of $v \in V$.

ABSTRACT. For a set of points P in the plane and a family of regions F, a local t-spanne of P is a sparse graph G over P, such that for any region r in F the subgraph restricted to r is a t-spanner for all the points of the intersection of r with P.

We present algorithms for the construction of local spanners with respect to several families of regions such as homothets of a convex region. Unfortunately, the number of edges in the resulting graph depends logarithmically on the spread of the input point set. We prove that this dependency can not be removed, thus settling an open problem raised by Abam and Borouny. We also show improved constructions (with no dependency on the spread) of local spanners for fat triangles, and regular k-gons. In particular, this improves over the known construction for axis parallel squares.

We also study notions of weaker local spanners where one is allowed to shrink the region a ``bit''. Surprisingly, we show a near linear size construction of a weak spanner for axis-parallel rectangles, where the shrinkage is multiplicative. Any spanner is a weak local spanner if the shrinking is proportional to the diameter of the region.

ABSTRACT. For an optimization problem Pi on graphs whose solutions are vertex sets, a vertex v is called c-essential for Pi if all solutions of size at most c * opt contain v. Recent work showed that polynomial-time algorithms to detect c-essential vertices can be used to reduce the search space of fixed-parameter tractable algorithms solving such problems parameterized by the size k of the solution. We provide several new upper- and lower bounds for detecting essential vertices. For example, we give a polynomial-time algorithm for 3-Essential detection for Vertex Multicut, which translates into an algorithm that finds a minimum multicut of an undirected n-vertex graph G in time 2^O(l^3) * n^O(1), where l is the number of vertices in an optimal solution that are not 3-essential. Our positive results are obtained by analyzing the integrality gaps of certain linear programs. Our lower bounds show that for sufficiently small values of c, the detection task becomes NP-hard assuming the Unique Games Conjecture. For example, we show that (2-eps)-Essential detection for Directed Feedback Vertex Set is NP-hard under this conjecture, thereby proving that the existing algorithm that detects 2-essential vertices is best-possible.

ABSTRACT. This paper studies the computational complexity of a robust variant of a two-stage submodular minimization problem that we call Robust Submodular Minimizer. In this problem, we are given k submodular functions f_1,...,f_k over a set family 2^V, which represent k possible scenarios in the future when we will need to find an optimal solution for one of these scenarios, i.e., a minimizer for one of the functions. The present task is to find a subset X of V that is close to some optimal solution for each f_i in the sense that some minimizer of f_i can be obtained from X by adding/removing at most d elements for a given integer d. The main contribution of this paper is to provide a complete computational map of this problem with respect to parameters k and d, which reveals a tight complexity threshold for both parameters:

• Robust Submodular Minimizer can be solved in polynomial time when k >= 2, but is NP-hard if k is a constant with k >= 3.
• Robust Submodular Minimizer can be solved in polynomial time when d=0, but is NP-hard if d is a constant with d >= 1.
• Robust Submodular Minimizer is fixed-parameter tractable when parameterized by (k,d).

We also show that if some submodular function f_i has a polynomial number of minimizers, then the problem becomes fixed-parameter tractable when parameterized by d. We remark that all our hardness results hold even if each submodular function is given by a cut function of a directed graph.

ABSTRACT. We introduce and study the weighted version of an online matching problem in Euclidean plane with non-crossing constraints: $2n$ points with non-negative weights arrive online, and an algorithm can match an arriving point to one of the unmatched previously arrived points. In the vanilla model, the decision on how to match (if at all) a newly arriving point is irrevocable. The goal is to maximize the total weight of matched points under the constraint that straight-line segments corresponding to the edges of the matching do not intersect. The unweighted version of the problem was introduced in the offline setting by Atallah in 1985, and this problem became a subject of study in the online setting with and without advice in several recent papers.

We observe that deterministic online algorithms cannot guarantee non-trivial competitive ratio for the weighted problem. We study various regimes of the problem which permit non-trivial online algorithms. In particular, when weights are restricted to the interval $[1, U]$ we give a deterministic algorithm achieving competitive ratio $\Omega\left(2^{-2\sqrt{\log U}}\right)$. We also prove that deterministic online algorithms cannot achieve competitive ratio better than $O\left(2^{-\sqrt{\log U}}\right)$. Interestingly, we establish that randomization alone suffices to achieve competitive ratio $1/3$ even when there are no restrictions on the weights. Additionally, if one allows an online algorithm to revoke acceptances, then one can achieve a constant competitive ratio deterministically for arbitrary weights. We also establish a lower bound on the competitive ratio of randomized algorithms in the unweighted setting, and improve the best-known bound on advice complexity of the unweighted problem.

ABSTRACT. We study the bin covering problem where a multiset of items from a fixed set $S \subseteq (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 an online manner. In the purely online setting, we show that the competitive ratios of best deterministic (and randomized) algorithms converge to $\frac{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$.

ABSTRACT. Drawing a graph in the plane with as few crossings as possible is one of the central problems in graph drawing and computational geometry. Alternatively, one can remove a small number of vertices or edges such that the remaining graph can be drawn without crossings. We study both problems in a book-embedding setting for \emph{ordered graphs}, that is, graphs with a fixed vertex order. In this setting, the vertices lie on a straight line, called the \emph{spine}, in the given order, and each edge must be drawn on one of several pages of a book such that every edge has at most a fixed number of crossings. In this setting, there is another way to reduce or avoid crossings; namely by using more pages. The minimum number of pages needed to draw an ordered graph without any crossings is its (fixed-vertex-order) \emph{page number}.

We show that the page number of an ordered graph with $n$ vertices and $m$ edges can be computed in $2^m \cdot n^{O(1)}$ time. An $O(\log n)$-approximation of this number can be computed efficiently. We can decide in $2^{O(c\sqrt{k} \log (c+k))} \cdot n^{O(1)}$ time whether it suffices to delete $k$ edges of an ordered graph to obtain a \emph{$c$-planar} layout (where every edge crosses at most $c$ other edges) on {\em one} page. As an additional parameter, we consider the size $h$ of a \emph{hitting set}, that is, a set of points on the spine such that every edge, seen as an open interval, contains at least one of the points. For $h=1$, we can efficiently compute the minimum number of edges whose deletion yields fixed-vertex-order page number~$p$. For $h>1$, we give an XP algorithm with respect to $h+p$. Finally, we consider \emph{spine+\tr-track drawings}, where some but not all vertices lie on the spine. The vertex order on the spine is given; we must map every vertex that does not lie on the spine to one of \tr tracks, each of which is a straight line on a separate page, parallel to the spine. In this setting, we can minimize in $2^n \cdot n^{O(1)}$ time either the number of crossings or, if we disallow crossings, the number of tracks.

ABSTRACT. We investigate the existence in geometric graph classes of subexponential parameterized algorithms for cycle-hitting problems like Triangle Hitting (TH), Feedback Vertex Set (FVS) or Odd Cycle Transversal (OCT). These problems respectively ask for the existence in a graph $G$ of a set $X$ of at most $k$ vertices such that $G-X$ is triangle-free, acyclic, or bipartite. It is know that subexponential FPT algorithms of the form $2^{o(k)}n^{O(1)}$ exist in planar and even $H$-minor free graphs from bidimensionality theory [Demaine et al. 2005], and there is a recent line of work lifting these results to geometric graph classes consisting of intersection of similarly sized ``fat'' objects ([Fomin et al. 2012], [Grigoriev et al. 2014], or disk graphs [Lokshtanov et al. 2022], [An et al. 2023]).

In this paper we first identify sufficient conditions, for any graph class $\mathcal C$ included in string graphs, to admit subexponential FPT algorithms for any problem in $\mathcal P$, a family of bidimensional problems where one has to find a set of size at most $k$ hitting a fixed family of graphs, containing in particular \FVS. Informally, these conditions boil down to the fact that for any $G \in \mathcal C$, the local radius of $G$ (a new parameter introduced in [Lokshtanov et al. 2023]) is polynomial in the clique number of $G$ and in the maximum matching in the neighborhood of a vertex. To demonstrate the applicability of this generic result, we bound the local radius for two special classes: intersection graphs of axis-parallel squares and of contact graphs of segments in the plane. This implies that any problem $\Pi \in \mathcal P$ (in particular, FVS) can be solved in: \begin{itemize} \item $2^{O(k^{3/4}\log k)}n^{O(1)}$-time in contact segment graphs, \item $2^{O(k^{9/10}\log k)}n^{O(1)}$ in intersection graphs of axis-parallel squares \end{itemize} On the positive side, we also provide positive results for TH by solving it in: \begin{itemize} \item $2^{O(k^{3/4}\log k)}n^{O(1)}$-time in contact segment graphs, \item $2^{O(\sqrt d t^2 (\log t) k^{2/3}\log k)} n^{O(1)}$-time in $K_{t,t}$-free d-DIR graphs (intersection of segments with at most $d$ possible slopes) \end{itemize}

On the negative side, assuming the ETH we rule out the existence of algorithms solving: \begin{itemize} \item TH and OCT in time $2^{o(n)}$ in 2-DIR graphs and more generally in time $2^{o(\sqrt{\Delta n})}$ in 2-DIR graphs with maximum degree $\Delta$, and \item TH, FVS, and OCT in time $2^{o(\sqrt{n})}$ in $K_{2,2}$-free contact-2-DIR{} graphs of maximum degree~6. \end{itemize} Observe that together, these results show that the absence of large $K_{t,t}$ is a necessary and sufficient condition for the existence of subexponential FPT algorithms for TH in 2-DIR.

ABSTRACT. In this work, we concern ourselves with the fine-grained complexity of recognition and proper coloring problems on highly restricted classes of geometric intersection graphs of ``thin'' objects (i.e., objects with unbounded aspect ratios). As a point of motivation, we remark that there has been significant interest in finding algorithmic lower bounds for classic decision and optimization problems on these types of graphs, as they appear to escape the net of known planar or geometric separator theorems for ``fat'' objects (i.e., objects with bounded aspect ratios). In particular, letting $n$ be the order of a geometric intersection graph, and assuming a geometric ply bound, per what is known as the ``square root phenomenon'', these separator theorems often imply the existence of $\mathcal{O}\left(2^{\left(\sqrt{n}\right)}\right)$ algorithms for problems ranging from finding proper colorings to finding Hamiltonian cycles. However, in contrast, it is known for instance that no $2^{o\left(n\right)}$ time algorithm can exist under the Exponential Time Hypothesis (ETH) for proper $6$-coloring intersection graphs of line segments embedded in the plane (Bir\'{o} et. al.; \textit{J. Comput. Geom.} \textbf{9}(2); pp. 47--80; 2018).

We begin by establishing algorithmic lower bounds for proper $k$-coloring and recognition problems of intersection graphs of line segments embedded in the plane under the most stringent constraints possible that allow either problem to be non-trivial. In particular, we consider the class UNIT-PURE-$k$-DIR of unit segment geometric intersection graphs, in which segments are constrained to lie in at most $k$ directions in the plane, and no two parallel segments are permitted to intersect. Here, under the ETH, we show for every $k \geq 3$ that no $2^{o\left(\sqrt{n / k}\right)}$ time algorithm can exist for either recognizing or proper $k$-coloring UNIT-PURE-$k$-DIR graphs of order $n$. In addition, for every $k \geq 4$, we establish the same algorithmic lower bound under the ETH for the problem of proper $\left(k-1\right)$-coloring UNIT-PURE-$k$-DIR graphs when provided a list of segment coordinates specified using $\mathcal{O}\left(n \cdot k\right)$ bits witnessing graph class membership. As a consequence of our approach, we are also able to show that the problem of properly $3$-coloring an arbitrary graph on $m$ edges can be reduced in $\mathcal{O}\left(m^2\right)$ time to the problem of properly $\left(k-1\right)$-coloring a UNIT-PURE-$k$-DIR graph. Finally, we consider a slightly less constrained class of geometric intersection graphs of lines (of unbounded length) in which line-line intersections must occur on any one of $\left(r=3\right)$ parallel planes in $\mathbb{R}^3$. In this context, for every $k \geq 3$, we show that no $2^{o\left(n/k\right)}$ time algorithm can exist for proper $k$-coloring these graphs unless the ETH is false.

ABSTRACT. We study the edge-colouring problem, and give efficient algorithms where the number of colours is parameterised by the graph’s arboricity, α. In a dynamic graph, subject to insertions and deletions, we give a deterministic algorithm that updates a proper ∆ + O(α) edge colouring in poly (log n) amortised time. Our algorithm is fully adaptive to the current value of the maximum degree and arboricity.

In this fully-dynamic setting, the state-of-the-art edge-colouring algorithms are either a randomised algorithm using (1 + ε)∆ colours in poly (log n, ε−1) time per update, or the naive greedy algorithm which is a deterministic 2∆ − 1 edge colouring with log(∆) update time.

Compared to the (1 + ε)∆ algorithm, our algorithm is deterministic and asymptotically faster, and when α is sufficiently small compared to ∆, it even uses fewer colours. In particular, ours is the first ∆ + O(1) edge-colouring algorithm for dynamic forests, and dynamic planar graphs, with polylogarithmic update time.

Additionally, in the static setting, we show that we can find a proper edge colouring with max{deg(u), deg(v)} + 2α colours in O(m log n) time. This time bound matches that of the greedy algorithm that computes a 2∆ − 1 colouring of the graph’s edges, and improves the number of colours when α is sufficiently small compared to ∆.

ABSTRACT. The problem of edge coloring has been extensively studied over the years. Recently, this problem has received significant attention in the \emph{dynamic setting}, where we are given a dynamic graph evolving via a sequence of edge insertions and deletions and our objective is to maintain an edge coloring of the graph.

Currently, it is not known whether it is possible to maintain a $(\Delta+ O(\Delta^{1 - \mu}))$-edge coloring in $\tilde{O}(1)$ update time, for any constant $\mu > 0$, where $\Delta$ is the maximum degree of the graph. In this paper, we show how to efficiently maintain a $(\Delta +O(\alpha))$-edge coloring in $\tilde O(1)$ amortized update time, where $\alpha$ is the arboricty of the graph. Thus, we answer this question in the affirmative for graphs of sufficiently small arboricity.