The section covers research in all aspects of the design and analysis of discrete algorithms. This extends also to data structures, combinatorial structures, and lower bounds.
Topics includes: Algorithmic aspects of networks - Algorithmic game theory - Approximation algorithms - Combinatorial optimization - Computational biology - Distributed algorithms - Computational geometry - Data compression - Data structures - Databases and information retrieval - Graph algorithms - Hierarchical memories - Mobile computing - On-line algorithms - Parallel algorithms - Parametrized complexity - Pattern matching - Randomized algorithms - Scheduling - Streaming algorithms
Editors:Mikkel Abrahamsen, Hans Bodlaender, Glencora Borradaile, Sergio Cabello, Anne Driemel, Esther Ezra, Isabelle Guérin Lassous, Magnús Halldórsson, Klaus Jansen, Christian Komusiewicz, Kitty Meeks, Rolf Niedermeier, Andrzej Pelc, M. S. Ramanujan, Natan Rubin, Ignasi Sau, Jiří Sgall, Hadas Shachnai, Roohani Sharma, Raphael Steiner, Zsolt Tuza, Rob van Stee
Editors:Mikkel Abrahamsen, Hans Bodlaender, Glencora Borradaile, Sergio Cabello, Anne Driemel, Esther Ezra, Isabelle Guérin Lassous, Magnús Halldórsson, Klaus Jansen, Christian Komusiewicz, Kitty Meeks, Rolf Niedermeier, Andrzej Pelc, M. S. Ramanujan, Natan Rubin, Ignasi Sau, Jiří Sgall, Hadas Shachnai, Roohani Sharma, Raphael Steiner, Zsolt Tuza, Rob van Stee
Bastien Harismendy, Tom da Silva, Gaëlle Largeteau-Skapin, Éric Andrès
Abstract
A solid polycube is a face-connected set of unit cubes, where, unlike classical definitions for polycubes, shared faces between adjacent cubes are not removed. We prove by mathematical induction that any such polycube can be edge-unfolded into a 2D net without refinement. Our proof relies on the concept of a perfect net, defined as a net in which two designated edges are placed on the far left and far right sides. This configuration enables consistent gluing of nets in a single direction throughout the induction process, thereby guaranteeing that no overlaps occur at any step.
Sarita de Berg, Guillermo Esteban, Rodrigo I. Silveira, Frank Staals
Abstract
In this paper, we consider the Weighted Region Problem. In the Weighted Region Problem, the length of a path is defined as the sum of the weights of the subpaths within each region, where the weight of a subpath is its Euclidean length multiplied by a weight $ α\geq 0 $ depending on the region. We study a restricted version of the problem of determining shortest paths through a single weighted rectangular region. We prove that even this very restricted version of the problem is unsolvable within the Algebraic Computation Model over the Rational Numbers (ACMQ). On the positive side, we provide the equations for the shortest paths that are computable within the ACMQ. Additionally, we provide equations for the bisectors between regions of the Shortest Path Map for a source point on the boundary of (or inside) the rectangular region.
In the area of query complexity of Boolean functions, the most widely studied cost measure of an algorithm is the worst-case number of queries made by it on an input. Motivated by the most natural cost measure studied in online algorithms, the competitive ratio, we consider a different cost measure for query algorithms for Boolean functions that captures the ratio of the cost of the algorithm and the cost of an optimal algorithm that knows the input in advance. The cost of an algorithm is its largest cost over all inputs. Grossman, Komargodski and Naor [ITCS'20] introduced this measure for Boolean functions, and dubbed it instance complexity. Grossman et al. showed, among other results, that monotone Boolean functions with instance complexity 1 are precisely those that depend on one or two variables. We complement the above-mentioned result of Grossman et al. by completely characterizing the instance complexity of symmetric Boolean functions. As a corollary we conclude that the only symmetric Boolean functions with instance complexity 1 are the Parity function and its complement. We also study the instance complexity of some graph properties like Connectivity and k-clique containment. In all the Boolean functions we study above, and those studied by Grossman et al., the instance complexity turns out to be the ratio of query complexity to minimum certificate complexity. It is a natural question to ask if this is the correct bound for all Boolean functions. We show a negative answer in a very strong sense, by analyzing the instance complexity of the Greater-Than and Odd-Max-Bit functions. We show that the above-mentioned ratio is linear in the input size for both of these functions, while we exhibit algorithms for which the instance complexity is a constant. Journal (DMTCS) version
A stable or locally-optimal cut of a graph is a cut whose weight cannot be increased by changing the side of a single vertex. In this paper we study Minimum Stable Cut, the problem of finding a stable cut of minimum weight. Since this problem is NP-hard, we study its complexity on graphs of low treewidth, low degree, or both. We begin by showing that the problem remains weakly NP-hard on severely restricted trees, so bounding treewidth alone cannot make it tractable. We match this hardness with a pseudo-polynomial DP algorithm solving the problem in time $(Δ\cdot W)^{O(tw)}n^{O(1)}$, where $tw$ is the treewidth, $Δ$ the maximum degree, and $W$ the maximum weight. On the other hand, bounding $Δ$ is also not enough, as the problem is NP-hard for unweighted graphs of bounded degree. We therefore parameterize Minimum Stable Cut by both $tw$ and $Δ$ and obtain an FPT algorithm running in time $2^{O(Δtw)}(n+\log W)^{O(1)}$. Our main result for the weighted problem is to provide a reduction showing that both aforementioned algorithms are essentially optimal, even if we replace treewidth by pathwidth: if there exists an algorithm running in $(nW)^{o(pw)}$ or $2^{o(Δpw)}(n+\log W)^{O(1)}$, then the ETH is false. Complementing this, we show that we can, however, obtain an FPT approximation scheme parameterized by treewidth, if we consider almost-stable solutions, that is, solutions where no single vertex can unilaterally increase the weight of its incident cut edges by more than a factor of $(1+\varepsilon)$. Motivated by these mostly negative results, we consider Unweighted Minimum Stable Cut. Here our results already imply a much faster exact algorithm running in time $Δ^{O(tw)}n^{O(1)}$. We show that this is also probably essentially optimal: an algorithm running in $n^{o(pw)}$ would contradict the ETH. Full version of ICALP 2021 paper
In the Fully Leafed Induced Subtrees, one is given a graph $G$ and two integers $a$ and $b$ and the question is to find an induced subtree of $G$ with $a$ vertices and at least $b$ leaves. This problem is known to be NP-complete even when the input graph is $4$-regular. Polynomial algorithms are known when the input graph is restricted to be a tree or series-parallel. In this paper we generalize these results by providing an FPT algorithm parameterized by treewidth. We also provide a polynomial algorithm when the input graph is restricted to be a chordal graph. arXiv admin note: substantial text overlap with arXiv:1704.07284, arXiv:2103.06536
Ioannis Lamprou, Ioannis Sigalas, Ioannis Vaxevanakis, Vassilis Zissimopoulos
Abstract
In $\textit{total domination}$, given a graph $G=(V,E)$, we seek a minimum-size set of nodes $S\subseteq V$, such that every node in $V$ has at least one neighbor in $S$. We define a $\textit{fault-tolerant}$ version of total domination, where we require any node in $V \setminus S$ to have at least $m$ neighbors in $S$. Let $Δ$ denote the maximum degree in $G$. We prove a first $1 + \ln(Δ+ m - 1)$ approximation for fault-tolerant total domination. We also consider fault-tolerant variants of the weighted $\textit{partial positive influence dominating set}$ problem, where we seek a minimum-size set of nodes $S\subseteq V$, such that every node in $V$ is either a member of $S$ or the sum of weights of its incident edges leading to nodes in $S$ is at least half of the sum of weights over all its incident edges. We prove the first logarithmic approximations for the simple, total, and connected variants of this problem. To prove the result for the connected case, we extend the general approximation framework for non-submodular functions from integer-valued to fractional-valued functions, which we believe is of independent interest.
Alberto Dennunzio, Enrico Formenti, Luciano Margara, Sara Riva
Abstract
Endowing the set of functional graphs (FGs) with the sum (disjoint union of graphs) and product (standard direct product on graphs) operations induces on FGs a structure of a commutative semiring R. The operations on R can be naturally extended to the set of univariate polynomials R[X] over R. This paper provides a polynomial time algorithm for deciding if equations of the type AX=B have solutions when A is just a single cycle and B a set of cycles of identical size. We also prove a similar complexity result for some variants of the previous equation. Final version accepted by DMTCS; added a linefeed before 'Clearly' in the before last page, as asked by the editor
We investigate a combinatorial optimization problem that involves patrolling the edges of an acute triangle using a unit-speed agent. The goal is to minimize the maximum (1-gap) idle time of any edge, which is defined as the time gap between consecutive visits to that edge. This problem has roots in a centuries-old optimization problem posed by Fagnano in 1775, who sought to determine the inscribed triangle of an acute triangle with the minimum perimeter. It is well-known that the orthic triangle, giving rise to a periodic and cyclic trajectory obeying the laws of geometric optics, is the optimal solution to Fagnano's problem. Such trajectories are known as Fagnano orbits, or more generally as billiard trajectories. We demonstrate that the orthic triangle is also an optimal solution to the patrolling problem. Our main contributions pertain to new connections between billiard trajectories and optimal patrolling schedules in combinatorial optimization. In particular, as an artifact of our arguments, we introduce a novel 2-gap patrolling problem that seeks to minimize the visitation time of objects every three visits. We prove that there exist infinitely many well-structured billiard-type optimal trajectories for this problem, including the orthic trajectory, which has the special property of minimizing the visitation time gap between any two consecutively visited edges. Complementary to that, we also examine the cost of dynamic, sub-optimal trajectories to the 1-gap patrolling optimization problem. These trajectories result from a greedy algorithm and can be implemented by a computationally primitive mobile agent.
We study a graph-theoretic problem in the Penrose P2-graphs which are the dual graphs of Penrose tilings by kites and darts. Using substitutions, local isomorphism and other properties of Penrose tilings, we construct a family of arbitrarily large induced subtrees of Penrose graphs with the largest possible number of leaves for a given number $n$ of vertices. These subtrees are called fully leafed induced subtrees. We denote their number of leaves $L_{P2}(n)$ for any non-negative integer $n$, and the sequence $\left(L_{P2}(n)\right)_{n\in\mathbb{N}}$ is called the leaf function of Penrose P2-graphs. We present exact and recursive formulae for $L_{P2}(n)$, as well as an infinite sequence of fully leafed induced subtrees, which are caterpillar graphs. In particular, our proof relies on the construction of a finite graded poset of 3-internal-regular subtrees. 25 pages, 19 figures
We study the parameterized complexity of the following factorization problem: given elements $a,a_1, \ldots, a_m$ of a monoid and a parameter $k$, can $a$ be written as the product of at most (or exactly) $k$ elements from $a_1, \ldots, a_m$. Several new upper bounds and fpt-equivalences with more restricted problems (subset sum and knapsack) are shown. Finally, some new upper bounds for variants of the parameterized change-making problems are shown.
The role of symmetry in Boolean functions $f:\{0,1\}^n \to \{0,1\}$ has been extensively studied in complexity theory. For example, symmetric functions, that is, functions that are invariant under the action of $S_n$, is an important class of functions in the study of Boolean functions. A function $f:\{0,1\}^n \to \{0,1\}$ is called transitive (or weakly-symmetric) if there exists a transitive group $G$ of $S_n$ such that $f$ is invariant under the action of $G$ - that is the function value remains unchanged even after the bits of the input of $f$ are moved around according to some permutation $σ\in G$. Understanding various complexity measures of transitive functions has been a rich area of research for the past few decades. In this work, we study transitive functions in light of several combinatorial measures. We look at the maximum separation between various pairs of measures for transitive functions. Such study for general Boolean functions has been going on for past many years. The best-known results for general Boolean functions have been nicely compiled by Aaronson et. al (STOC, 2021). The separation between a pair of combinatorial measures is shown by constructing interesting functions that demonstrate the separation. But many of the celebrated separation results are via the construction of functions (like "pointer functions" from Ambainis et al. (JACM, 2017) and "cheat-sheet functions" Aaronson et al. (STOC, 2016)) that are not transitive. Hence, we don't have such separation between the pairs of measures for transitive functions. In this paper we show how to modify some of these functions to construct transitive functions that demonstrate similar separations between pairs of combinatorial measures.
The Minimum Branch Vertices Spanning Tree problem aims to find a spanning tree $T$ in a given graph $G$ with the fewest branch vertices, defined as vertices with a degree three or more in $T$. This problem, known to be NP-hard, has attracted significant attention due to its importance in network design and optimization. Extensive research has been conducted on the algorithmic and combinatorial aspects of this problem, with recent studies delving into its fixed-parameter tractability. In this paper, we focus primarily on the parameter modular-width. We demonstrate that finding a spanning tree with the minimum number of branch vertices is Fixed-Parameter Tractable (FPT) when considered with respect to modular-width. Additionally, in cases where each vertex in the input graph has an associated cost for serving as a branch vertex, we prove that the problem of finding a spanning tree with the minimum branch cost (i.e., minimizing the sum of the costs of branch vertices) is FPT with respect to neighborhood diversity.
We present combinatorial approximation algorithms for the weighted correlation clustering problem. In this problem, we have a set of vertices and two weight values for each pair of vertices, denoting their difference and similarity. The goal is to cluster the vertices with minimum total intra-cluster difference weights plus inter-cluster similarity weights. We present two results for weighted instances with $n$ vertices: - A randomized 3-approximation combinatorial algorithm for instances that satisfy probability constraints, running in $O(n^2)$ time. This improves the $O(n^6)$ running time of the previous best-known combinatorial approximation, a 3-approximation algorithm, introduced by Chawla et al. (2015). - A randomized 1.6-approximation combinatorial algorithm for instances that satisfy probability and triangle inequality constraints, running in $O(n^2)$ time. This improves the longstanding combinatorial 2-approximation of Ailon et al. (2008) while matching its running time.
A path graph is the intersection graph of paths in a tree. A directed path graph is the intersection graph of paths in a directed tree. Even if path graphs and directed path graphs are characterized very similarly, their recognition algorithms differ widely. We further unify these two graph classes by presenting the first recognition algorithm for both path graphs and directed path graphs. We deeply use a recent characterization of path graphs, and we extend it to directed path graphs. Our algorithm does not require complex data structures and has an easy and intuitive implementation, simplifying recognition algorithms for both graph classes. Comment: 13 pages, 3 figures
Tobias Mömke, Alexandru Popa, Aida Roshany-Tabrizi, Michael Ruderer, Roland Vincze
Abstract
In a simple, undirected graph G, an edge 2-coloring is a coloring of the edges such that no vertex is incident to edges with more than 2 distinct colors. The problem maximum edge 2-coloring (ME2C) is to find an edge 2-coloring in a graph G with the goal to maximize the number of colors. For a relevant graph class, ME2C models anti-Ramsey numbers and it was considered in network applications. For the problem a 2-approximation algorithm is known, and if the input graph has a perfect matching, the same algorithm has been shown to have a performance guarantee of 5/3. It is known that ME2C is APX-hard and that it is UG-hard to obtain an approximation ratio better than 1.5. We show that if the input graph has a perfect matching, there is a polynomial time 1.625-approximation and if the graph is claw-free or if the maximum degree of the input graph is at most three (i.e., the graph is subcubic), there is a polynomial time 1.5-approximation algorithm for ME2C Comment: 24 pages, 6 figures, preliminary version published at WAOA 2023
Maël Dumas, Anthony Perez, Mathis Rocton, Ioan Todinca
Abstract
We consider edge modification problems towards block and strictly chordal graphs, where one is given an undirected graph $G = (V,E)$ and an integer $k \in \mathbb{N}$ and seeks to edit (add or delete) at most $k$ edges from $G$ to obtain a block graph or a strictly chordal graph. The completion and deletion variants of these problems are defined similarly by only allowing edge additions for the former and only edge deletions for the latter. Block graphs are a well-studied class of graphs and admit several characterizations, e.g. they are diamond-free chordal graphs. Strictly chordal graphs, also referred to as block duplicate graphs, are a natural generalization of block graphs where one can add true twins of cut-vertices. Strictly chordal graphs are exactly dart and gem-free chordal graphs. We prove the NP-completeness for most variants of these problems and provide $O(k^2)$ vertex-kernels for Block Graph Editing and Block Graph Deletion, $O(k^3)$ vertex-kernels for Strictly Chordal Completion and Strictly Chordal Deletion and a $O(k^4)$ vertex-kernel for Strictly Chordal Editing.
We study a primitive vehicle routing-type problem in which a fleet of $n$unit speed robots start from a point within a non-obtuse triangle $\Delta$, where $n \in \{1,2,3\}$. The goal is to design robots' trajectories so as to visit all edges of the triangle with the smallest visitation time makespan. We begin our study by introducing a framework for subdividing $\Delta$into regions with respect to the type of optimal trajectory that each point $P$ admits, pertaining to the order that edges are visited and to how the cost of the minimum makespan $R_n(P)$ is determined, for $n\in \{1,2,3\}$. These subdivisions are the starting points for our main result, which is to study makespan trade-offs with respect to the size of the fleet. In particular, we define $ R_{n,m} (\Delta)= \max_{P \in \Delta} R_n(P)/R_m(P)$, and we prove that, over all non-obtuse triangles $\Delta$: (i) $R_{1,3}(\Delta)$ ranges from $\sqrt{10}$ to $4$, (ii) $R_{2,3}(\Delta)$ ranges from $\sqrt{2}$ to $2$, and (iii) $R_{1,2}(\Delta)$ ranges from $5/2$ to $3$. In every case, we pinpoint the starting points within every triangle $\Delta$ that maximize $R_{n,m} (\Delta)$, as well as we identify the triangles that determine all $\inf_\Delta R_{n,m}(\Delta)$ and $\sup_\Delta R_{n,m}(\Delta)$ over the set of non-obtuse triangles. Comment: 47 pages, 27 figures
We study the parameterized complexity of computing the tree-partition-width, a graph parameter equivalent to treewidth on graphs of bounded maximum degree. On one hand, we can obtain approximations of the tree-partition-width efficiently: we show that there is an algorithm that, given an $n$-vertex graph $G$ and an integer $k$, constructs a tree-partition of width $O(k^7)$ for $G$ or reports that $G$ has tree-partition-width more than $k$, in time $k^{O(1)}n^2$. We can improve slightly on the approximation factor by sacrificing the dependence on $k$, or on $n$. On the other hand, we show the problem of computing tree-partition-width exactly is XALP-complete, which implies that it is $W[t]$-hard for all $t$. We deduce XALP-completeness of the problem of computing the domino treewidth. Next, we adapt some known results on the parameter tree-partition-width and the topological minor relation, and use them to compare tree-partition-width to tree-cut width. Finally, for the related parameter weighted tree-partition-width, we give a similar approximation algorithm (with ratio now $O(k^{15})$) and show XALP-completeness for the special case where vertices and edges have weight 1. Comment: Journal version (DMTCS)
We consider the matching problem on the line with advice complexity. We give a 1-competitive online algorithm with advice complexity $n-1,$ and show that there is no 1-competitive online algorithm reading less than $n-1$ bits of advice. Moreover, for each $0<k<n$ we present a $c(n/k)$-competitive online algorithm with advice complexity $O(k(\log N + \log n))$ where $n$ is the number of servers, $N$ is the distance of the minimal and maximal servers, and $c(n)$ is the complexity of the best online algorithm without advice.
Cover-Incomparability graphs (C-I graphs) are an interesting class of graphs from posets. A C-I graph is a graph from a poset $P=(V,\le)$ with vertex set $V$, and the edge-set is the union of edge sets of the cover graph and the incomparability graph of the poset. The recognition of the C-I graphs is known to be NP-complete (Maxov\'{a} et al., Order 26(3), 229--236(2009)). In this paper, we prove that chordal graphs having at most two independent simplicial vertices are exactly the chordal graphs which are also C-I graphs. A similar result is obtained for cographs as well. Using the structural results of these graphs, we derive linear time recognition algorithms for chordal graphs and cographs which are C-I graphs. Comment: 17 pages, 7 figures
, Hans Bodlaender, Glencora Borradaile, Sergio Cabello