Search

Given access to the hypergraph through a subset query oracle in the query model, we give sublinear time algorithms for Hitting-Set with almost tight parameterized query complexity. In parameterized query complexity, we estimate the number of queries to the oracle based on the parameter $k$, the size of the Hitting-Set. The subset query oracle we use in this paper is called Generalized $d$-partite Independent Set query oracle (GPIS) and it was introduced by Bishnu et al. (ISAAC'18). GPIS is a generalization to hypergraphs of the Bipartite Independent Set query oracle (BIS) introduced by Beame et al. (ITCS'18 and TALG'20) for estimating the number of edges in graphs. Formally, GPIS is defined as follows: GPIS oracle for a $d$-uniform hypergraph $\mathcal{H}$ takes as input $d$ pairwise disjoint non-empty subsets $A_1, \ldots, A_d$ of vertices in $\cal H$ and answers whether there is a hyperedge in $\mathcal{H}$ that intersects each set $A_i$, where $i \in \{1, \, 2, \, \ldots, d\}$. } For $d=2$, the GPIS oracle is nothing but BIS oracle. We show that $d$-Hitting-Set, the hitting set problem for $d$-uniform hypergraphs, can be solved using $\widetilde{\mathcal{O}}_d(k^{d} \log n)$ GPIS queries. Additionally, we also showed that $d$-Decesion-Hitting-Set, the decision version of $d$-Hitting-Set can be solved with $\widetilde{\mathcal{O}}_d\left( \min \left\{ k^d\log n, k^{2d^2} \right\} \right)$ {\sc GPIS} queries. We complement these parameterized upper bounds with an almost matching parameterized lower bound that states that any algorithm that solves $d$-Decesion-Hitting-Set requires $\Omega \left( \binom{k+d}{d} \right)$ GPIS queries., Comment: 22 pages. A preliminary version has appeared in ISAAC'19 and the full version has been accepted in JCSS

For unweighted graphs, finding isometric embeddings is closely related to decompositions of $G$ into Cartesian products of smaller graphs. When $G$ is isomorphic to a Cartesian graph product, we call the factors of this product a factorization of $G$. When $G$ is isomorphic to an isometric subgraph of a Cartesian graph product, we call those factors a pseudofactorization of $G$. Prior work has shown that an unweighted graph's pseudofactorization can be used to generate a canonical isometric embedding into a product of the smallest possible pseudofactors. However, for arbitrary weighted graphs, which represent a richer variety of metric spaces, methods for finding isometric embeddings or determining their existence remain elusive, and indeed pseudofactorization and factorization have not previously been extended to this context. In this work, we address the problem of finding the factorization and pseudofactorization of a weighted graph $G$, where $G$ satisfies the property that every edge constitutes a shortest path between its endpoints. We term such graphs minimal graphs, noting that every graph can be made minimal by removing edges not affecting its path metric. We generalize pseudofactorization and factorization to minimal graphs and develop new proof techniques that extend the previously proposed algorithms due to Graham and Winkler [Graham and Winkler, '85] and Feder [Feder, '92] for pseudofactorization and factorization of unweighted graphs. We show that any $m$-edge, $n$-vertex graph with positive integer edge weights can be factored in $O(m^2)$ time, plus the time to find all pairs shortest paths (APSP) distances in a weighted graph, resulting in an overall running time of $O(m^2+n^2\log\log n)$ time. We also show that a pseudofactorization for such a graph can be computed in $O(mn)$ time, plus the time to solve APSP, resulting in an $O(mn+n^2\log\log n)$ running time., Comment: 37 pages, 10 figures

We generalize the tree doubling and Christofides algorithm, the two most common approximations for TSP, to parameterized approximations for ATSP. The parameters we consider for the respective parameterizations are upper bounded by the number of asymmetric distances in the given instance, which yields algorithms to efficiently compute constant factor approximations also for moderately asymmetric TSP instances. As generalization of the Christofides algorithm, we derive a parameterized 2.5-approximation, where the parameter is the size of a vertex cover for the subgraph induced by the asymmetric edges. Our generalization of the tree doubling algorithm gives a parameterized 3-approximation, where the parameter is the number of asymmetric edges in a given minimum spanning arborescence. Both algorithms are also stated in the form of additive lossy kernelizations, which allows to combine them with known polynomial time approximations for ATSP. Further, we combine them with a notion of symmetry relaxation which allows to trade approximation guarantee for runtime. We complement our results by experimental evaluations, which show that generalized tree-doubling frequently outperforms generalized Christofides with respect to parameter size.

We describe a practical algorithm for computing normal forms for semigroups and monoids with finite presentations satisfying so-called small overlap conditions. Small overlap conditions are natural conditions on the relations in a presentation, which were introduced by J. H. Remmers and subsequently studied extensively by M. Kambites. Presentations satisfying these conditions are ubiquitous; Kambites showed that a randomly chosen finite presentation satisfies the $C(4)$ condition with probability tending to 1 as the sum of the lengths of relation words tends to infinity. Kambites also showed that several key problems for finitely presented semigroups and monoids are tractable in $C(4)$ monoids: the word problem is solvable in $O(\min\{|u|, |v|\})$ time in the size of the input words $u$ and $v$; the uniform word problem for $\langle A|R\rangle$ is solvable in $O(N ^ 2 \min\{|u|, |v|\})$ where $N$ is the sum of the lengths of the words in $R$; and a normal form for any given word $u$ can be found in $O(|u|)$ time. Although Kambites' algorithm for solving the word problem in $C(4)$ monoids is highly practical, it appears that the coefficients in the linear time algorithm for computing normal forms are too large in practice. In this paper, we present an algorithm for computing normal forms in $C(4)$ monoids that has time complexity $O(|u| ^ 2)$ for input word $u$, but where the coefficients are sufficiently small to allow for practical computation. Additionally, we show that the uniform word problem for small overlap monoids can be solved in $O(N \min\{|u|, |v|\})$ time., Comment: 31 pages, 6 figures (some further minor corrections from the referee are resolved, to appear in Journal of Algebra)

Let $\mathcal{G}$ be a minor-closed graph class. We say that a graph $G$ is a $k$-apex of $\mathcal{G}$ if $G$ contains a set $S$ of at most $k$ vertices such that $G\setminus S$ belongs to $\mathcal{G}.$ We denote by $\mathcal{A}_k (\mathcal{G})$ the set of all graphs that are $k$-apices of $\mathcal{G}.$ We prove that every graph in the obstruction set of $\mathcal{A}_k (\mathcal{G}),$ i.e., the minor-minimal set of graphs not belonging to $\mathcal{A}_k (\mathcal{G}),$ has size at most $2^{2^{2^{2^{\mathsf{poly}(k)}}}},$ where $\mathsf{poly}$ is a polynomial function whose degree depends on the size of the minor-obstructions of $\mathcal{G}.$ This bound drops to $2^{2^{\mathsf{poly}(k)}}$ when $\mathcal{G}$ excludes some apex graph as a minor., Comment: 48 pages and 12 figures. arXiv admin note: text overlap with arXiv:2004.12692

We study the classical expander codes, introduced by Sipser and Spielman [M. Sipser and D. A. Spielman, 1996]. Given any constants 0 < ��, �� < 1/2, and an arbitrary bipartite graph with N vertices on the left, M < N vertices on the right, and left degree D such that any left subset S of size at most �� N has at least (1-��)|S|D neighbors, we show that the corresponding linear code given by parity checks on the right has distance at least roughly {�� N}/{2 ��}. This is strictly better than the best known previous result of 2(1-��) �� N [Madhu Sudan, 2000; Viderman, 2013] whenever �� < 1/2, and improves the previous result significantly when �� is small. Furthermore, we show that this distance is tight in general, thus providing a complete characterization of the distance of general expander codes. Next, we provide several efficient decoding algorithms, which vastly improve previous results in terms of the fraction of errors corrected, whenever �� < 1/4. Finally, we also give a bound on the list-decoding radius of general expander codes, which beats the classical Johnson bound in certain situations (e.g., when the graph is almost regular and the code has a high rate). Our techniques exploit novel combinatorial properties of bipartite expander graphs. In particular, we establish a new size-expansion tradeoff, which may be of independent interests., LIPIcs, Vol. 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), pages 43:1-43:3

Semi-online models where decisions may be revoked in a limited way have been studied extensively in the last years. This is motivated by the fact that the pure online model is often too restrictive to model real-world applications, where some changes might be allowed. A well-studied measure of the amount of decisions that can be revoked is the migration factor $\beta$: When an object $o$ of size $s(o)$ arrives, the decisions for objects of total size at most $\beta\cdot s(o)$ may be revoked. Usually $\beta$ should be a constant. This means that a small object only leads to small changes. This measure has been successfully investigated for different, classic problems such as bin packing or makespan minimization. The dual of makespan minimization - the Santa Claus or machine covering problem - has also been studied, whereas the dual of bin packing - the bin covering problem - has not been looked at from such a perspective. In this work, we extensively study the bin covering problem with migration in different scenarios. We develop algorithms both for the static case - where only insertions are allowed - and for the dynamic case, where items may also depart. We also develop lower bounds for these scenarios both for amortized migration and for worst-case migration showing that our algorithms have nearly optimal migration factor and asymptotic competitive ratio (up to an arbitrary small $\eps$). We therefore resolve the competitiveness of the bin covering problem with migration.

We introduce a Generalized LU-Factorization (\textbf{GLU}) for low-rank matrix approximation. We relate this to past approaches and extensively analyze its approximation properties. The established deterministic guarantees are combined with sketching ensembles satisfying Johnson-Lindenstrauss properties to present complete bounds. Particularly good performance is shown for the sub-sampled randomized Hadamard transform (SRHT) ensemble. Moreover, the factorization is shown to unify and generalize many past algorithms. It also helps to explain the effect of sketching on the growth factor during Gaussian Elimination.

(see paper for full abstract) We show that the Edge-Disjoint Paths problem is W[1]-hard parameterized by the number $k$ of terminal pairs, even when the input graph is a planar directed acyclic graph (DAG). This answers a question of Slivkins (ESA '03, SIDMA '10). Moreover, under the Exponential Time Hypothesis (ETH), we show that there is no $f(k)\cdot n^{o(k)}$ algorithm for Edge-Disjoint Paths on planar DAGs, where $k$ is the number of terminal pairs, $n$ is the number of vertices and $f$ is any computable function. Our hardness holds even if both the maximum in-degree and maximum out-degree of the graph are at most $2$. Our result shows that the $n^{O(k)}$ algorithm of Fortune et al. (TCS '80) for Edge-Disjoint Paths on DAGs is asymptotically tight, even if we add an extra restriction of planarity. As a special case of our result, we obtain that Edge-Disjoint Paths on planar directed graphs is W[1]-hard parameterized by the number $k$ of terminal pairs. This answers a question of Cygan et al. (FOCS '13) and Schrijver (pp. 417-444, Building Bridges II, '19), and completes the landscape of the parameterized complexity status of edge and vertex versions of the Disjoint Paths problem on planar directed and planar undirected graphs., Comment: A preliminary version of the paper to appear in CIAC 2021

A graph $H$ is an induced minor of a graph $G$ if $H$ can be obtained from $G$ by vertex deletions and edge contractions. We show that there is a function $f(k, d) = O(k^{10} + 2^{d^5})$ so that if a graph has treewidth at least $f(k, d)$ and maximum degree at most $d$, then it contains a $k \times k$-grid as an induced minor. This proves the conjecture of Aboulker, Adler, Kim, Sintiari, and Trotignon [Eur. J. Comb., 98, 2021] that any graph with large treewidth and bounded maximum degree contains a large wall or the line graph of a large wall as an induced subgraph. It also implies that for any fixed planar graph $H$, there is a subexponential time algorithm for maximum weight independent set on $H$-induced-minor-free graphs., 7 pages. To appear in JCTB

Klinz and Woeginger (1995) prove that the minimum cost quickest flow problem is NP-hard. On the other hand, the quickest minimum cost flow problem can be solved efficiently via a straightforward reduction to the quickest flow problem without costs. More generally, we show how the quickest minimum cost transshipment problem can be reduced to the efficiently solvable quickest transshipment problem, thus adding another mosaic tile to the rich complexity landscape of flows over time.

The Covering Salesman Problem (CSP) is a generalization of the Traveling Salesman Problem in which the tour is not required to visit all vertices, as long as all vertices are covered by the tour. The objective of CSP is to find a minimum length Hamiltonian cycle over a subset of vertices that covers an undirected graph. In this paper, valid inequalities from the generalized traveling salesman problem are applied to the CSP in addition to new valid inequalities that explore distinct aspects of the problem. A branch-and-cut framework assembles exact and heuristic separation routines for integer and fractional CSP solutions. Computational experiments show that the proposed framework outperformed methodologies from literature with respect to optimality gaps. Moreover, optimal solutions were proven for several previously unsolved instances.

The problem of community detection with two equal-sized communities is closely related to the minimum graph bisection problem over certain random graph models. In the stochastic block model distribution over networks with community structure, a well-known semidefinite programming (SDP) relaxation of the minimum bisection problem recovers the underlying communities whenever possible. Motivated by their superior scalability, we study the theoretical performance of linear programming (LP) relaxations of the minimum bisection problem for the same random models. We show that unlike the SDP relaxation that undergoes a phase transition in the logarithmic average-degree regime, the LP relaxation exhibits a transition from recovery to non-recovery in the linear average-degree regime. We show that in the logarithmic average-degree regime, the LP relaxation fails in recovering the planted bisection with high probability., 32 pages, 3 figures; includes revisions for print version

Unmanned aerial vehicles (UAVs), commonly known as drones, are being increasingly deployed throughout the globe as a means to streamline monitoring, inspection, mapping, and logistic routines. When dispatched on autonomous missions, drones require an intelligent decision-making system for trajectory planning and tour optimization. Given the limited capacity of their onboard batteries, a key design challenge is to ensure the underlying algorithms can efficiently optimize the mission objectives along with recharging operations during long-haul flights. With this in view, the present work undertakes a comprehensive study on automated tour management systems for an energy-constrained drone: (1) We construct a machine learning model that estimates the energy expenditure of typical multi-rotor drones while accounting for real-world aspects and extrinsic meteorological factors. (2) Leveraging this model, the joint program of flight mission planning and recharging optimization is formulated as a multi-criteria Asymmetric Traveling Salesman Problem (ATSP), wherein a drone seeks for the time-optimal energy-feasible tour that visits all the target sites and refuels whenever necessary. (3) We devise an efficient approximation algorithm with provable worst-case performance guarantees and implement it in a drone management system, which supports real-time flight path tracking and re-computation in dynamic environments. (4) The effectiveness and practicality of the proposed approach are validated through extensive numerical simulations as well as real-world experiments.

In this paper, we study a data caching problem in the cloud environment, where multiple frequently co-utilised data items could be packed as a single item being transferred to serve a sequence of data requests dynamically with reduced cost. To this end, we propose an online algorithm with respect to a homogeneous cost model, called PackCache, that can leverage the FP-Tree technique to mine those frequently co-utilised data items for packing whereby the incoming requests could be cost-effectively served online by exploiting the concept of anticipatory caching. We show the algorithm is 2\alpha competitive, reaching the lower bound of the competitive ratio for any deterministic online algorithm on the studied caching problem, and also time and space efficient to serve the requests. Finally, we evaluate the performance of the algorithm via experimental studies to show its actual cost-effectiveness and scalability., Comment: Accepted by IEEE Transactions on Computers

Significant efforts have been expended in the research and development of a database management system (DBMS) that has a wide range of applications for managing an enormous collection of multisource, heterogeneous, complex, or growing data. Besides the primary function (i.e., create, delete, and update), a practical and impeccable DBMS can interact with users through information selection, that is, querying with their targets. Previous querying algorithms, such as frequent itemset querying and sequential pattern querying (SPQ) have focused on the measurement of frequency, which does not involve the concept of utility, which is helpful for users to discover more informative patterns. To apply the querying technology for wider applications, we incorporate utility into target-oriented SPQ and formulate the task of targeted utility-oriented sequence querying. To address the proposed problem, we develop a novel algorithm, namely targeted high-utility sequence querying (TUSQ), based on two novel upper bounds suffix remain utility and terminated descendants utility as well as a vertical Last Instance Table structure. For further efficiency, TUSQ relies on a projection technology utilizing a compact data structure called the targeted chain. An extensive experimental study conducted on several real and synthetic datasets shows that the proposed algorithm outperformed the designed baseline algorithm in terms of runtime, memory consumption, and candidate filtering., Preprint. 8 figures, 4 tables

We consider the problem of computing the \emph{distance-based representative skyline} in the plane, a problem introduced by Tao, Ding, Lin and Pei [Proc. 25th IEEE International Conference on Data Engineering (ICDE), 2009] and independently considered by Dupin, Nielsen and Talbi [Optimization and Learning - Third International Conference, OLA 2020] in the context of multi-objective optimization. Given a set $P$ of $n$ points in the plane and a parameter $k$, the task is to select $k$ points of the skyline defined by $P$ (also known as Pareto front for $P$) to minimize the maximum distance from the points of the skyline to the selected points. We show that the problem can be solved in $O(n\log h)$ time, where $h$ is the number of points in the skyline of $P$. We also show that the decision problem can be solved in $O(n\log k)$ time and the optimization problem can be solved in $O(n \log k + n \operatorname{loglog} n)$ time. This improves previous algorithms and is optimal for a large range of values of $k$., 25 pages

For decision making under uncertainty, min-max regret has been established as a popular methodology to find robust solutions. In this approach, we compare the performance of our solution against the best possible performance had we known the true scenario in advance. We introduce a generalization of this setting which allows us to compare against solutions that are also affected by uncertainty, which we call balanced regret. Using budgeted uncertainty sets, this allows for a wider range of possible alternatives the decision maker may choose from. We analyze this approach for general combinatorial problems, providing an iterative solution method and insights into solution properties. We then consider a type of selection problem in more detail and show that, while the classic regret setting with budgeted uncertainty sets can be solved in polynomial time, the balanced regret problem becomes NP-hard. In computational experiments using random and real-world data, we show that balanced regret solutions provide a useful trade-off for the performance in classic performance measures.

For general antiferromagnetic 2-spin systems, including the hardcore model and the antiferromagnetic Ising model, there is an $\mathsf{FPTAS}$ for the partition function on graphs of maximum degree $\Delta$ when the infinite regular tree lies in the uniqueness region by Li et al. (2013). Moreover, in the tree non-uniqueness region, Sly (2010) showed that there is no $\mathsf{FPRAS}$ to estimate the partition function unless $\mathsf{NP}=\mathsf{RP}$. The algorithmic results follow from the correlation decay approach due to Weitz (2006) or the polynomial interpolation approach developed by Barvinok (2016). However the running time is only polynomial for constant $\Delta$. For the hardcore model, recent work of Anari et al. (2020) establishes rapid mixing of the simple single-site Markov chain known as the Glauber dynamics in the tree uniqueness region. Our work simplifies their analysis of the Glauber dynamics by considering the total pairwise influence of a fixed vertex $v$ on other vertices, as opposed to the total influence on $v$, thereby extending their work to all 2-spin models and improving the mixing time. More importantly our proof ties together the three disparate algorithmic approaches: we show that contraction of the tree recursions with a suitable potential function, which is the primary technique for establishing efficiency of Weitz's correlation decay approach and Barvinok's polynomial interpolation approach, also establishes rapid mixing of the Glauber dynamics. We emphasize that this connection holds for all 2-spin models (both antiferromagnetic and ferromagnetic), and existing proofs for correlation decay or polynomial interpolation immediately imply rapid mixing of Glauber dynamics. Our proof utilizes that the graph partition function divides that of Weitz's self-avoiding walk trees, leading to new tools for analyzing influence of vertices., Comment: Section 7 and Appendix E are updated to fix a small error

We examine the problem of smoothed online optimization, where a decision maker must sequentially choose points in a normed vector space to minimize the sum of per-round, non-convex hitting costs and the costs of switching decisions between rounds. The decision maker has access to a black-box oracle, such as a machine learning model, that provides untrusted and potentially inaccurate predictions of the optimal decision in each round. The goal of the decision maker is to exploit the predictions if they are accurate, while guaranteeing performance that is not much worse than the hindsight optimal sequence of decisions, even when predictions are inaccurate. We impose the standard assumption that hitting costs are globally $\alpha$-polyhedral. We propose a novel algorithm, Adaptive Online Switching (AOS), and prove that, for a large set of feasible $\delta > 0$, it is $(1+\delta)$-competitive if predictions are perfect, while also maintaining a uniformly bounded competitive ratio of $2^{\tilde{\mathcal{O}}(1/(\alpha \delta))}$ even when predictions are adversarial. Further, we prove that this trade-off is necessary and nearly optimal in the sense that \emph{any} deterministic algorithm which is $(1+\delta)$-competitive if predictions are perfect must be at least $2^{\tilde{\Omega}(1/(\alpha \delta))}$-competitive when predictions are inaccurate. In fact, we observe a unique threshold-type behavior in this trade-off: if $\delta$ is not in the set of feasible options, then \emph{no} algorithm is simultaneously $(1 + \delta)$-competitive if predictions are perfect and $\zeta$-competitive when predictions are inaccurate for any $\zeta < \infty$. Furthermore, we discuss that memory is crucial in AOS by proving that any algorithm that does not use memory cannot benefit from predictions. We complement our theoretical results by a numerical study on a microgrid application., Comment: 38 pages, 4 figures

We consider the classic problem of computing the Longest Common Subsequence (LCS) of two strings of length $n$. While a simple quadratic algorithm has been known for the problem for more than 40 years, no faster algorithm has been found despite an extensive effort. The lack of progress on the problem has recently been explained by Abboud, Backurs, and Vassilevska Williams [FOCS'15] and Bringmann and K��nnemann [FOCS'15] who proved that there is no subquadratic algorithm unless the Strong Exponential Time Hypothesis fails. This has led the community to look for subquadratic approximation algorithms for the problem. Yet, unlike the edit distance problem for which a constant-factor approximation in almost-linear time is known, very little progress has been made on LCS, making it a notoriously difficult problem also in the realm of approximation. For the general setting, only a naive $O(n^{\varepsilon/2})$-approximation algorithm with running time $\tilde{O}(n^{2-\varepsilon})$ has been known, for any constant $0 < \varepsilon \le 1$. Recently, a breakthrough result by Hajiaghayi, Seddighin, Seddighin, and Sun [SODA'19] provided a linear-time algorithm that yields a $O(n^{0.497956})$-approximation in expectation; improving upon the naive $O(\sqrt{n})$-approximation for the first time. In this paper, we provide an algorithm that in time $O(n^{2-\varepsilon})$ computes an $\tilde{O}(n^{2\varepsilon/5})$-approximation with high probability, for any $0 < \varepsilon \le 1$. Our result (1) gives an $\tilde{O}(n^{0.4})$-approximation in linear time, improving upon the bound of Hajiaghayi, Seddighin, Seddighin, and Sun, (2) provides an algorithm whose approximation scales with any subquadratic running time $O(n^{2-\varepsilon})$, improving upon the naive bound of $O(n^{\varepsilon/2})$ for any $\varepsilon$, and (3) instead of only in expectation, succeeds with high probability., full version of ICALP'21 paper, abstract shortened to fit Arxiv requirements

Core decomposition is a classic technique for discovering densely connected regions in a graph with large range of applications. Formally, a $k$-core is a maximal subgraph where each vertex has at least $k$ neighbors. A natural extension of a $k$-core is a $(k, h)$-core, where each node must have at least $k$ nodes that can be reached with a path of length $h$. The downside in using $(k, h)$-core decomposition is the significant increase in the computational complexity: whereas the standard core decomposition can be done in $O(m)$ time, the generalization can require $O(n^2m)$ time, where $n$ and $m$ are the number of nodes and edges in the given graph. In this paper we propose a randomized algorithm that produces an $\epsilon$-approximation of $(k, h)$ core decomposition with a probability of $1 - \delta$ in $O(\epsilon^{-2} hm (\log^2 n - \log \delta))$ time. The approximation is based on sampling the neighborhoods of nodes, and we use Chernoff bound to prove the approximation guarantee. We also study distance-generalized dense subgraphs, show that the problem is NP-hard, provide an algorithm for discovering such graphs with approximate core decompositions, and provide theoretical guarantees for the quality of the discovered subgraphs. We demonstrate empirically that approximating the decomposition complements the exact computation: computing the approximation is significantly faster than computing the exact solution for the networks where computing the exact solution is slow, Comment: Extended version

We present an $O(n^2)$-time algorithm to test whether an $n$-vertex directed partial $2$-tree is upward planar. This result improves upon the previously best known algorithm, which runs in $O(n^4)$ time., Appears in the Proceedings of the 30th International Symposium on Graph Drawing and Network Visualization (GD 2022)

Computing an accurate mean of a set of time series is a critical task in applications like nearest-neighbor classification and clustering of time series. While there are many distance functions for time series, the most popular distance function used for the computation of time series means is the non-metric dynamic time warping (DTW) distance. A recent algorithm for the exact computation of a DTW-Mean has a running time of $\mathcal{O}(n^{2k+1}2^kk)$, where $k$ denotes the number of time series and $n$ their maximum length. In this paper, we study the mean problem for the move-split-merge (MSM) metric that not only offers high practical accuracy for time series classification but also carries of the advantages of the metric properties that enable further diverse applications. The main contribution of this paper is an exact and efficient algorithm for the MSM-Mean problem of time series. The running time of our algorithm is $\mathcal{O}(n^{k+3}2^k k^3 )$, and thus better than the previous DTW-based algorithm. The results of an experimental comparison confirm the running time superiority of our algorithm in comparison to the DTW-Mean competitor. Moreover, we introduce a heuristic to improve the running time significantly without sacrificing much accuracy., 25 pages, 14 figures

In group testing, the goal is to identify a subset of defective items within a larger set of items based on tests whose outcomes indicate whether at least one defective item is present. This problem is relevant in areas such as medical testing, DNA sequencing, communication protocols, and many more. In this paper, we study (i) a sparsity-constrained version of the problem, in which the testing procedure is subjected to one of the following two constraints: items are finitely divisible and thus may participate in at most $\gamma$ tests; or tests are size-constrained to pool no more than $\rho$ items per test; and (ii) a noisy version of the problem, where each test outcome is independently flipped with some constant probability. Under each of these settings, considering the for-each recovery guarantee with asymptotically vanishing error probability, we introduce a fast splitting algorithm and establish its near-optimality not only in terms of the number of tests, but also in terms of the decoding time. While the most basic formulations of our algorithms require $\Omega(n)$ storage for each algorithm, we also provide low-storage variants based on hashing, with similar recovery guarantees., Comment: Information and Inference: A Journal of the IMA

Node-link diagrams are widely used to visualize graphs. Most graph layout algorithms only use graph topology for aesthetic goals (e.g., minimize node occlusions and edge crossings) or use node attributes for exploration goals (e.g., preserve visible communities). Existing hybrid methods that bind the two perspectives still suffer from various generation restrictions (e.g., limited input types and required manual adjustments and prior knowledge of graphs) and the imbalance between aesthetic and exploration goals. In this paper, we propose a flexible embedding-based graph exploration pipeline to enjoy the best of both graph topology and node attributes. First, we leverage embedding algorithms for attributed graphs to encode the two perspectives into latent space. Then, we present an embedding-driven graph layout algorithm, GEGraph, which can achieve aesthetic layouts with better community preservation to support an easy interpretation of the graph structure. Next, graph explorations are extended based on the generated graph layout and insights extracted from the embedding vectors. Illustrated with examples, we build a layout-preserving aggregation method with Focus+Context interaction and a related nodes searching approach with multiple proximity strategies. Finally, we conduct quantitative and qualitative evaluations, a user study, and two case studies to validate our approach., accepted by TVCG

We present a new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem. Its approximation ratio is $\frac{4}{3}$, which matches the current best ratio. The approximation ratio of the algorithm is $\frac{6}{5}$ on subcubic graphs, which is an improvement upon the previous best ratio of $\frac{5}{4}$. The algorithm is a novel extension of the primal-dual schema, which consists of two distinct phases. Both the algorithm and the analysis are much simpler than those of the previous approaches., Comment: 14 pages, appeared in TCS

We study the problem of deciding reconfigurability of target sets of a graph. Given a graph $G$ with vertex thresholds $\tau$, consider a dynamic process in which vertex $v$ becomes activated once at least $\tau(v)$ of its neighbors are activated. A vertex set $S$ is called a target set if all vertices of $G$ would be activated when initially activating vertices of $S$. In the Target Set Reconfiguration problem, given two target sets $X$ and $Y$ of the same size, we are required to determine whether $X$ can be transformed into $Y$ by repeatedly swapping one vertex in the current set with another vertex not in the current set preserving every intermediate set as a target set. In this paper, we investigate the complexity of Target Set Reconfiguration in restricted cases. On the hardness side, we prove that Target Set Reconfiguration is PSPACE-complete on bipartite planar graphs of degree $3$ and $4$ and of threshold $2$, bipartite $3$-regular graphs and planar $3$-regular graphs of threshold $1$ and $2$, and split graphs, which is in contrast to the fact that a special case called Vertex Cover Reconfiguration is in P for the last graph class. On the positive side, we present a polynomial-time algorithm for Target Set Reconfiguration on graphs of maximum degree $2$ and trees. The latter result can be thought of as a generalization of that for Vertex Cover Reconfiguration., Comment: 36 pages; changed according to referee suggestions; to appear in Theoretical Computer Science

In this paper we consider the algorithmic problem of sampling from the Potts model and computing its partition function at low temperatures. Instead of directly working with spin configurations, we consider the equivalent problem of sampling flows. We show, using path coupling, that a simple and natural Markov chain on the set of flows is rapidly mixing. As a result we find a $\delta$-approximate sampling algorithm for the Potts model at low enough temperatures, whose running time is bounded by $O(m^2\log(m\delta^{-1}))$ for graphs $G$ with $m$ edges., Comment: Slightly revised version based on referee comments. No significant changes. Accepted in Random Structures and Algorithms

We revisit the classical change propagation framework for query evaluation under updates. The standard framework takes a query plan and materializes the intermediate views, which incurs high polynomial costs in both space and time, with the join operator being the culprit. In this paper, we propose a new change propagation framework without joins, thus naturally avoiding this polynomial blowup. Meanwhile, we show that the new framework still supports constant-delay enumeration of both the deltas and the full query results, the same as in the standard framework. Furthermore, we provide a quantitative analysis of its update cost, which not only recovers many recent theoretical results on the problem, but also yields an effective approach to optimizing the query plan. The new framework is also easy to be integrated into an existing streaming database system. Experimental results show that our system prototype, implemented using Flink DataStream API, significantly outperforms other systems in terms of space, time, and latency., Full version of the VLDB paper

Roughly speaking, gerrymandering is the systematic manipulation of the boundaries of electoral districts to make a specific (political) party win as many districts as possible. While typically studied from a geographical point of view, addressing social network structures, the investigation of gerrymandering over graphs was recently initiated by Cohen-Zemach et al. [AAMAS 2018]. Settling three open questions of Ito et al. [AAMAS 2019], we classify the computational complexity of the NP-hard problem Gerrymandering over Graphs when restricted to paths and trees. Our results, which are mostly of negative nature (that is, worst-case hardness), in particular yield two complexity dichotomies for trees. For instance, the problem is polynomial-time solvable for two parties but becomes weakly NP-hard for three. Moreover, we show that the problem remains NP-hard even when the input graph is a path.

Symmetry plays a major role in subgraph matching both in the description of the graphs in question and in how it confounds the search process. This work addresses how to quantify these effects and how to use symmetries to increase the efficiency of subgraph isomorphism algorithms. We introduce rigorous definitions of structural equivalence and establish conditions for when it can be safely used to generate more solutions. We illustrate how to adapt standard search routines to utilize these symmetries to accelerate search and compactly describe the solution space. We then adapt a state-of-the-art solver and perform a comprehensive series of tests to demonstrate these methods' efficacy on a standard benchmark set. We extend these methods to multiplex graphs and present results on large multiplex networks drawn from transportation systems, social media, adversarial attacks, and knowledge graphs., To appear in IEEE Transactions on Network Science and Engineering

We present a thorough experimental evaluation of several crossing minimization heuristics that are based on the construction and iterative improvement of a planarization, i.e., a planar representation of a graph with crossings replaced by dummy vertices. The evaluated heuristics include variations and combinations of the well-known planarization method, the recently implemented star reinsertion method, and a new approach proposed herein: the mixed insertion method. Our experiments reveal the importance of several implementation details such as the detection of non-simple crossings (i.e., crossings between adjacent edges or multiple crossings between the same two edges). The most notable finding, however, is that the insertion of stars in a fixed embedding setting is not only significantly faster than the insertion of edges in a variable embedding setting, but also leads to solutions of higher quality., Comment: Appears in the Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (GD 2021); 22 pages with 12 figures; v2: legend in Fig. 5 fixed; v3: higher contrast colors & better plot readability

A mixed dominating set of a graph $G = (V, E)$ is a mixed set $D$ of vertices and edges, such that for every edge or vertex, if it is not in $D$, then it is adjacent or incident to at least one vertex or edge in $D$. The mixed domination problem is to find a mixed dominating set with a minimum cardinality. It has applications in system control and some other scenarios and it is $NP$-hard to compute an optimal solution. This paper studies approximation algorithms and hardness of the weighted mixed dominating set problem. The weighted version is a generalization of the unweighted version, where all vertices are assigned the same nonnegative weight $w_v$ and all edges are assigned the same nonnegative weight $w_e$, and the question is to find a mixed dominating set with a minimum total weight. Although the mixed dominating set problem has a simple 2-approximation algorithm, few approximation results for the weighted version are known. The main contributions of this paper include: [1.] for $w_e\geq w_v$, a 2-approximation algorithm; [2.] for $w_e\geq 2w_v$, inapproximability within ratio 1.3606 unless $P=NP$ and within ratio 2 under UGC; [3.] for $2w_v > w_e\geq w_v$, inapproximability within ratio 1.1803 unless $P=NP$ and within ratio 1.5 under UGC; [4.] for $w_e< w_v$, inapproximability within ratio $(1-\epsilon)\ln |V|$ unless $P=NP$ for any $\epsilon >0$.

Ride-sharing is an essential aspect of modern urban mobility. In this paper, we consider a classical problem in ride-sharing - the Multi-Vehicle Dial-a-Ride Problem (Multi-Vehicle DaRP). Given a fleet of vehicles with a fixed capacity stationed at various locations and a set of ride requests specified by origins and destinations, the goal is to serve all requests such that no vehicle is assigned more passengers than its capacity at any point in its trip. We give an algorithm HGR, which is the first non-trivial approximation algorithm for the Multi-Vehicle DaRP. The main technical contribution is to reduce Multi-Vehicle DaRP to a certain capacitated partitioning problem, which we solve using a novel hierarchical grouping algorithm. Experimental results show that the vehicle routes produced by our algorithm not only exhibit less total travel distance compared to state-of-the-art baselines, but also enjoy a small in-transit latency, which crucially relates to each individual rider's traveling time. This suggests that HGR enhances rider experience while being energy-efficient.

We consider a discrete system of $n$ simple indistinguishable devices, called \emph{agents}, forming a \emph{connected} shape $S_I$ on a two-dimensional square grid. Agents are equipped with a linear-strength mechanism, called a \emph{line move}, by which an agent can push a whole line of consecutive agents in one of the four directions in a single time-step. We study the problem of transforming an initial shape $S_I$ into a given target shape $S_F$ via a finite sequence of line moves in a distributed model, where each agent can observe the states of nearby agents in a Moore neighbourhood. Our main contribution is the first distributed connectivity-preserving transformation that exploits line moves within a total of $O(n \log_2 n)$ moves, which is asymptotically equivalent to that of the best-known centralised transformations. The algorithm solves the \emph{line formation problem} that allows agents to form a final straight line $S_L$, starting from any shape $ S_I $, whose \emph{associated graph} contains a Hamiltonian path., Comment: 31 pages, 18 figures

This paper studies the \emph{subset sampling} problem. The input is a set $\mathcal{S}$ of $n$ records together with a function $\textbf{p}$ that assigns each record $v\in\mathcal{S}$ a probability $\textbf{p}(v)$. A query returns a random subset $X$ of $\mathcal{S}$, where each record $v\in\mathcal{S}$ is sampled into $X$ independently with probability $\textbf{p}(v)$. The goal is to store $\mathcal{S}$ in a data structure to answer queries efficiently. If $\mathcal{S}$ fits in memory, the problem is interesting when $\mathcal{S}$ is dynamic. We develop a dynamic data structure with $\mathcal{O}(1+\mu_{\mathcal{S}})$ expected \emph{query} time, $\mathcal{O}(n)$ space and $\mathcal{O}(1)$ amortized expected \emph{update}, \emph{insert} and \emph{delete} time, where $\mu_{\mathcal{S}}=\sum_{v\in\mathcal{S}}\textbf{p}(v)$. The query time and space are optimal. If $\mathcal{S}$ does not fit in memory, the problem is difficult even if $\mathcal{S}$ is static. Under this scenario, we present an I/O-efficient algorithm that answers a \emph{query} in $\mathcal{O}\left((\log^*_B n)/B+(\mu_\mathcal{S}/B)\log_{M/B} (n/B)\right)$ amortized expected I/Os using $\mathcal{O}(n/B)$ space, where $M$ is the memory size, $B$ is the block size and $\log^*_B n$ is the number of iterative $\log_2(.)$ operations we need to perform on $n$ before going below $B$. In addition, when each record is associated with a real-valued key, we extend the \emph{subset sampling} problem to the \emph{range subset sampling} problem, in which we require that the keys of the sampled records fall within a specified input range $[a,b]$. For this extension, we provide a solution under the dynamic setting, with $\mathcal{O}(\log n+\mu_{\mathcal{S}\cap[a,b]})$ expected \emph{query} time, $\mathcal{O}(n)$ space and $\mathcal{O}(\log n)$ amortized expected \emph{update}, \emph{insert} and \emph{delete} time., Comment: 17 pages

In this paper, we present novel algorithms that efficiently compute a shortest reconfiguration sequence between two given dominating sets in trees and interval graphs under the Token Sliding model. In this problem, a graph is provided along with its two dominating sets, which can be imagined as tokens placed on vertices. The objective is to find a shortest sequence of dominating sets that transforms one set into the other, with each set in the sequence resulting from sliding a single token in the previous set. While identifying any sequence has been well studied, our work presents the first polynomial algorithms for this optimization variant in the context of dominating sets., To appear at FCT 2023 (Fundamentals of Computation Theory)

The concept of mutual-visibility in graphs has been recently introduced. If $X$ is a subset of vertices of a graph $G$, then vertices $u$ and $v$ are $X$-visible if there exists a shortest $u,v$-path $P$ such that $V(P)\cap X \subseteq \{u, v\}$. If every two vertices from $X$ are $X$-visible, then $X$ is a mutual-visibility set. The mutual-visibility number of $G$ is the cardinality of a largest mutual-visibility set of $G$. It is known that computing the mutual-visibility number of a graph is NP-complete, whereas it has been shown that there are exact formulas for special graph classes like paths, cycles, blocks, cographs, and grids. In this paper, we study the mutual-visibility in distance-hereditary graphs and show that the mutual-visibility number can be computed in linear time for this class., 16 pages, 5 figures, a preliminary version will appear on the proc. of the XII Latin and American Algorithms, Graphs and Optimization Symposium, {LAGOS} 2023, Huatulco, Mexico, September 18-22, 2023. Procedia Computer Science, Elsevier

The ellipsoid fitting conjecture of Saunderson, Chandrasekaran, Parrilo and Willsky considers the maximum number $n$ random Gaussian points in $\mathbb{R}^d$, such that with high probability, there exists an origin-symmetric ellipsoid passing through all the points. They conjectured a threshold of $n = (1-o_d(1)) \cdot d^2/4$, while until recently, known lower bounds on the maximum possible $n$ were of the form $d^2/(\log d)^{O(1)}$. We give a simple proof based on concentration of sample covariance matrices, that with probability $1 - o_d(1)$, it is possible to fit an ellipsoid through $d^2/C$ random Gaussian points. Similar results were also obtained in two recent independent works by Hsieh, Kothari, Potechin and Xu [arXiv, July 2023] and by Bandeira, Maillard, Mendelson, and Paquette [arXiv, July 2023]., Comment: 11 pages

Sliding-window aggregation is a foundational stream processing primitive that efficiently summarizes recent data. The state-of-the-art algorithms for sliding-window aggregation are highly efficient when stream data items are evicted or inserted one at a time, even when some of the insertions occur out-of-order. However, real-world streams are often not only out-of-order but also burtsy, causing data items to be evicted or inserted in larger bulks. This paper introduces a new algorithm for sliding-window aggregation with bulk eviction and bulk insertion. For the special case of single insert and evict, our algorithm matches the theoretical complexity of the best previous out-of-order algorithms. For the case of bulk evict, our algorithm improves upon the theoretical complexity of the best previous algorithm for that case and also outperforms it in practice. For the case of bulk insert, there are no prior algorithms, and our algorithm improves upon the naive approach of emulating bulk insert with a loop over single inserts, both in theory and in practice. Overall, this paper makes high-performance algorithms for sliding window aggregation more broadly applicable by efficiently handling the ubiquitous cases of out-of-order data and bursts., Extended version for VLDB 2023 paper

We present a near-linear time approximation algorithm for the subtrajectory cluster problem of $c$-packed trajectories. The problem involves finding $m$ subtrajectories within a given trajectory $T$ such that their Fr\'echet distances are at most $(1 + \varepsilon)d$, and at least one subtrajectory must be of length~$l$ or longer. A trajectory $T$ is $c$-packed if the intersection of $T$ and any ball $B$ with radius $r$ is at most $c \cdot r$ in length. Previous results by Gudmundsson and Wong \cite{GudmundssonWong2022Cubicupperlower} established an $\Omega(n^3)$ lower bound unless the Strong Exponential Time Hypothesis fails, and they presented an $O(n^3 \log^2 n)$ time algorithm. We circumvent this conditional lower bound by studying subtrajectory cluster on $c$-packed trajectories, resulting in an algorithm with an $O((c^2 n/\varepsilon^2)\log(c/\varepsilon)\log(n/\varepsilon))$ time complexity.

The development of simple and fast hypergraph spectral methods has been hindered by the lack of numerical algorithms for simulating heat diffusions and computing fundamental objects, such as Personalized PageRank vectors, over hypergraphs. In this paper, we overcome this challenge by designing two novel algorithmic primitives. The first is a simple, easy-to-compute discrete-time heat diffusion that enjoys the same favorable properties as the discrete-time heat diffusion over graphs. This diffusion can be directly applied to speed up existing hypergraph partitioning algorithms. Our second contribution is the novel application of mirror descent to compute resolvents of non-differentiable squared norms, which we believe to be of independent interest beyond hypergraph problems. Based on this new primitive, we derive the first nearly-linear-time algorithm that simulates the discrete-time heat diffusion to approximately compute resolvents of the hypergraph Laplacian operator, which include Personalized PageRank vectors and solutions to the hypergraph analogue of Laplacian systems. Our algorithm runs in time that is linear in the size of the hypergraph and inversely proportional to the hypergraph spectral gap $\lambda_G$, matching the complexity of analogous diffusion-based algorithms for the graph version of the problem.

The paper proposes dynamic parallel algorithms for connectivity and bipartiteness of undirected graphs that require constant time and $O(n^{1/2+\epsilon})$ work on the CRCW PRAM model. The work of these algorithms almost matches the work of the $O(\log n)$ time algorithm for connectivity by Kopelowitz et al. (2018) on the EREW PRAM model and the time of the sequential algorithm for bipartiteness by Eppstein et al. (1997). In particular, we show that the sparsification technique, which has been used in both mentioned papers, can in principle also be used for constant time algorithms in the CRCW PRAM model, despite the logarithmic depth of sparsification trees.

We study dynamic algorithms in the model of algorithms with predictions. We assume the algorithm is given imperfect predictions regarding future updates, and we ask how such predictions can be used to improve the running time. This can be seen as a model interpolating between classic online and offline dynamic algorithms. Our results give smooth tradeoffs between these two extreme settings. First, we give algorithms for incremental and decremental transitive closure and approximate APSP that take as an additional input a predicted sequence of updates (edge insertions, or edge deletions, respectively). They preprocess it in $\tilde{O}(n^{(3+\omega)/2})$ time, and then handle updates in $\tilde{O}(1)$ worst-case time and queries in $\tilde{O}(\eta^2)$ worst-case time. Here $\eta$ is an error measure that can be bounded by the maximum difference between the predicted and actual insertion (deletion) time of an edge, i.e., by the $\ell_\infty$-error of the predictions. The second group of results concerns fully dynamic problems with vertex updates, where the algorithm has access to a predicted sequence of the next $n$ updates. We show how to solve fully dynamic triangle detection, maximum matching, single-source reachability, and more, in $O(n^{\omega-1}+n\eta_i)$ worst-case update time. Here $\eta_i$ denotes how much earlier the $i$-th update occurs than predicted. Our last result is a reduction that transforms a worst-case incremental algorithm without predictions into a fully dynamic algorithm which is given a predicted deletion time for each element at the time of its insertion. As a consequence we can, e.g., maintain fully dynamic exact APSP with such predictions in $\tilde{O}(n^2)$ worst-case vertex insertion time and $\tilde{O}(n^2 (1+\eta_i))$ worst-case vertex deletion time (for the prediction error $\eta_i$ defined as above)., Comment: Abstract shortened to meet arXiv requirements

Given a graph $G = (V, E)$, a non-empty set $S \subseteq V$ is a defensive alliance, if for every vertex $v \in S$, the majority of its closed neighbours are in $S$, that is, $|N_G[v] \cap S| \geq |N_G[v] \setminus S|$. The decision version of the problem is known to be NP-Complete even when restricted to split and bipartite graphs. The problem is \textit{fixed-parameter tractable} for the parameters solution size, vertex cover number and neighbourhood diversity. For the parameters treewidth and feedback vertex set number, the problem is W[1]-hard. \\ \hspace*{2em} In this paper, we study the defensive alliance problem for graphs with bounded degree. We show that the problem is \textit{polynomial-time solvable} on graphs with maximum degree at most 5 and NP-Complete on graphs with maximum degree 6. This rules out the fixed-parameter tractability of the problem for the parameter maximum degree of the graph. We also consider the problem from the standpoint of parameterized complexity. We provide an FPT algorithm using the Integer Linear Programming approach for the parameter distance to clique. We also answer an open question posed in \cite{AG2} by providing an FPT algorithm for the parameter twin cover., 20 pages

We prove tight bounds on the site percolation threshold for $k$-uniform hypergraphs of maximum degree $\Delta$ and for $k$-uniform hypergraphs of maximum degree $\Delta$ in which any pair of edges overlaps in at most $r$ vertices. The hypergraphs that achieve these bounds are hypertrees, but unlike in the case of graphs, there are many different $k$-uniform, $\Delta$-regular hypertrees. Determining the extremal tree for a given $k, \Delta, r$ involves an optimization problem, and our bounds arise from a convex relaxation of this problem. By combining our percolation bounds with the method of disagreement percolation we obtain improved bounds on the uniqueness threshold for the hard-core model on hypergraphs satisfying the same constraints. Our uniqueness conditions imply exponential weak spatial mixing, and go beyond the known bounds for rapid mixing of local Markov chains and existence of efficient approximate counting and sampling algorithms. Our results lead to natural conjectures regarding the aforementioned algorithmic tasks, based on the intuition that uniqueness thresholds for the extremal hypertrees for percolation determine computational thresholds.

For approximate nearest neighbor search, graph-based algorithms have shown to offer the best trade-off between accuracy and search time. We propose the Dynamic Exploration Graph (DEG) which significantly outperforms existing algorithms in terms of search and exploration efficiency by combining two new ideas: First, a single undirected even regular graph is incrementally built by partially replacing existing edges to integrate new vertices and to update old neighborhoods at the same time. Secondly, an edge optimization algorithm is used to continuously improve the quality of the graph. Combining this ongoing refinement with the graph construction process leads to a well-organized graph structure at all times, resulting in: (1) increased search efficiency, (2) predictable index size, (3) guaranteed connectivity and therefore reachability of all vertices, and (4) a dynamic graph structure. In addition we investigate how well existing graph-based search systems can handle indexed queries where the seed vertex of a search is the query itself. Such exploration tasks, despite their good starting point, are not necessarily easy. High efficiency in approximate nearest neighbor search (ANNS) does not automatically imply good performance in exploratory search. Extensive experiments show that our new Dynamic Exploration Graph outperforms existing algorithms significantly for indexed and unindexed queries.

We propose efficient algorithms for enumerating maximal common subsequences (MCSs) of two strings. Efficiency of the algorithms are estimated by the preprocessing-time, space, and delay-time complexities. One algorithm prepares a cubic-space data structure in cubic time to output each MCS in linear time. This data structure can be used to search for particular MCSs satisfying some condition without performing an explicit enumeration. Another prepares a quadratic-space data structure in quadratic time to output each MCS in linear time, and the other prepares a linear-space data structure in quadratic time to output each MCS in linearithmic time., 23 pages, 5 Postscript figures

In the run-up to any major sports tournament, winning probabilities of participants are publicized for engagement and betting purposes. These are generally based on simulating the tournament tens of thousands of times by sampling from single-match outcome models. We show that, by virtue of the tournament schedule, exact computation of winning probabilties can be substantially faster than their approximation through simulation. This notably applies to the 2022 and 2023 FIFA World Cup Finals, and is independent of the model used for individual match outcomes., Working paper; first draft published prior to WWC2023