ABSTRACT. A garden is populated by n bamboos, each with its own daily growth rate. The Bamboo Garden Trimming Problem (BGT) is to design for a robotic gardener a perpetual schedule of cutting bamboos to keep the elevation of the garden as low as possible. The frequency of cutting is constrained by the time needed to move from one bamboo to the next, which is one day in Discrete BGT and is defined by the distance between the two bamboos in Continuous BGT. The bamboo garden is a metaphor for a collection of machines that have to be serviced, with different frequencies, by a robot that can service only one machine at a time. For Discrete BGT, we show a simple 4-approximation algorithm and, by exploiting the relationship between BGT and the classical Pinwheel Scheduling Problem, we derive a 2-approximation for the general case and a tighter approximation when the growth rates are balanced. For Continuous BGT, we propose approximation algorithms that achieve logarithmic approximation ratios.

ABSTRACT. A resolving set R in a graph G is a set of vertices such that every vertex of G is uniquely identified by its distances to the vertices of R. Introduced in the 1970’s, this concept has been since then extensively studied from both combinatorial and algorithmic point of view. We propose a generalization of the concept of resolving sets to temporal graphs, i.e., graphs with edge sets that change over discrete time-steps. In this setting, the temporal distance from u to v is the earliest possible time-step at which a journey with strictly increasing time-steps on edges leaving u reaches v, i.e., the first time-step at which v could receive a message broadcast from u. A temporal resolving set of a temporal graph G is a subset R of its vertices such that every vertex of G is uniquely identified by its temporal distances from vertices of R. We study the problem of finding a minimum-size temporal resolving set, and show that it is NP-complete even on very restricted graph classes and with strong constraints on the time-steps: temporal complete graphs where every edge appears in either time-step 1 or 2, temporal trees where every edge appears in at most two consecutive time-steps, and even temporal subdivided stars where every edge appears in at most two (not necessarily consecutive) time-steps. On the other hand, we give polynomial-time algorithms for temporal paths and temporal stars where every edge appears in exactly one time-step, and give a combinatorial analysis and algorithms for several temporal graph classes where the edges appear in periodic time-steps.

ABSTRACT. Broadcasting is an information dissemination problem in a connected network. One informed node, called the originator, must distribute a message to all other nodes by placing a series of calls along the communication lines of the network. Once a vertex has been informed, it contributes to the broadcasting process by distributing the message to its neighbors. Finding the broadcast time of any vertex in an arbitrary graph is NP-complete. In this paper, we study the broadcasting problem in the Windmill graph Wd_{k,l}, which contains k copies of the complete graph K_l connected to a universal vertex. We also investigate the broadcast problem in a novel topology termed Star of Cliques (SOC), which is an extension of the Windmill graph with arbitrary clique sizes. We present an algorithm to find the broadcast time of any vertex in an arbitrary SOC graph and discuss the optimality of the algorithm.

ABSTRACT. We study the question of whether a sequence $d = (d_1,d_2, ..., d_n)$ of positive integers is the degree sequence of some outerplanar (a.k.a. 1-page book embeddable) graph $G$. If so, $G$ is an outerplanar realization of $d$ and $d$ is an outerplanaric sequence. The case where $\sum d \leq 2n - 2$ is easy, as $d$ has a realization by a forest (which is trivially an outerplanar graph). In this paper, we consider the family $D$ of all sequences $d$ of even sum $2n \leq \sum d \le 4n-6-2\omega_1$, where $\omega_x$ is the number of $x$'s in $d$. (The second inequality is a necessary condition for a sequence $d$ with $\sum d\geq 2n$ to be outerplanaric.) We partition $D$ into two disjoint subfamilies, $D=D_{NOP}\cup D_{2PBE}$, such that every sequence in $D_{NOP}$ is provably non-outerplanaric, and every sequence in $D_{2PBE}$ is given a realizing graph $G$ enjoying a 2-page book embedding (and moreover, one of the pages is also bipartite).

ABSTRACT. We consider a natural generalization of chordal graphs, in which every minimal separator induces a subgraph with independence number at most~$2$. Such graphs can be equivalently defined as graphs that do not contain the complete bipartite graph $K_{2,3}$ as an induced minor, that is, graphs from which $K_{2,3}$ cannot be obtained by a sequence of edge contractions and vertex deletions.

We develop a polynomial-time algorithm for recognizing these graphs. Our algorithm relies on a characterization of $K_{2,3}$-induced minor-free graphs in terms of excluding particular induced subgraphs, called Truemper configurations.

ABSTRACT. In this paper, we consider the problems of enumerating minimal vertex covers and minimal dominating sets with capacity and/or connectivity constraints. We develop polynomial-delay enumeration algorithms for these problems on bounded-degree graphs. For the case of minimal connected vertex covers, our algorithm runs in polynomial delay even on the class of d-claw free graphs, which extends the result on bounded-degree graphs. To complement these algorithmic results, we show that the problems of enumerating minimal connected vertex covers and minimal capacitated vertex covers in bipartite graphs are at least as hard as enumerating minimal transversals in hypergraphs.

ABSTRACT. A graph is $k$-vertex-critical if $\chi(G)=k$ but $\chi(G-v)<k$ for all $v\in V(G)$ and $(G,H)$-free if it contains no induced subgraph isomorphic to $G$ or $H$. We show that there are only finitely many $k$-vertex-critical $(2P_2,H)$-free graphs for all $k$ when $H$ is isomorphic to any of the following graphs of order $5$: \begin{itemize} \item $bull$, \item $chair$, \item $claw+P_1$, or \item $\overline{diamond+P_1}$. \end{itemize}

\noindent The latter three are corollaries of more general results where $H$ is isomorphic to $(m, \ell)$-$squid$ for $m=3,4$ and any $\ell\ge 1$ where an $(m,\ell)$-$squid$ is the graph obtained from an $m$-cycle by attaching $\ell$ leaves to a single vertex of the cycle. For each of the graphs $H$ above and any fixed $k$, our results imply the existence of polynomial-time certifying algorithms for deciding the $k$-colourability problem for $(2P_2,H)$-free graphs. Further, our structural classifications allow us to exhaustively generate, with aid of computer search, all $k$-vertex-critical $(2P_2,H)$-free graphs for $k\le 7$ when $H=bull$ or $H=(4,1)$-$squid$ (also known as $banner$).

ABSTRACT. We study the problem of partitioning the vertex set of a given directed graph G = (V, E) into a small number of directed paths each of order at most a prescribed k, called the Directed k-Path Partition problem (k-PP). The k-PP problem with k = |V| is equivalent to the Directed Path Partition problem (PP), where the goal of PP is to find a minimum collection of vertex-disjoint directed paths of any order to cover all the vertices of V. The decision version of k-PP includes the Directed Hamiltonian Path problem as a special case. Therefore, when k is part of the input, the k-PP is APX-hard, and it is not approximable within two unless P = NP. Although k-PP on general graphs is intractable, several tractable cases are known. The k-PP problem with k = 2 (i.e., 2-PP) is essentially equivalent to the Maximum Matching problem on directed graphs, which is solvable in polynomial time. Also, it is claimed that if the input is restricted to directed acyclic graphs (DAGs) with height k, then PP can be solved in polynomial time. This implies that if the input graph is a DAG of height at most k, then k-PP can be solved in polynomial time since the order of every path in the directed path partition is at most k. In this paper, we prove that k-PP is APX-hard even if the input graph is restricted to planar, bipartite DAGs with height more than k and degree at most three. Also, we present the 1.0075-inapproximability of k-PP for any fixed k >= 3. In contrast, we show that k-PP on directed graphs with degree at most two can be solved in polynomial time.

ABSTRACT. The online bin covering problem is: given an input sequence of items find a placement of the items in the maximum number of bins such that the sum of the items' sizes in each bin is at least~1. Boyar~{\em et~al}.\@~\cite{boyar2021} present a strategy that with $O(\log \log n)$ bits of advice, where $n$ is the length of the input sequence, achieves a competitive ratio of $8/15\approx0.5333\ldots$. We show that with a strengthened analysis and some minor improvements, the same strategy achieves the significantly improved competitive ratio of~$135/242\approx0.5578\ldots$, still using $O(\log \log n)$ bits of advice.

ABSTRACT. Given a set of homothetic triangles (i.e., closed under scaling and translating operations) in the plane, we study the problem of computing the triangles enclosing a query object. The query objects considered are points, line segments, trapezoids, and ellipses. We show that the problem can be solved using the 3-d dominance reporting problem. The result can also be extended to higher dimensions.

ABSTRACT. The bottom-left algorithm is a simple heuristic for the Strip Packing Problem. It places the rectangles in the given order at the lowest free position in the strip, using the left most position in case of ties. Despite its simplicity, the exact approximation ratio of the bottom-left algorithm remains unknown. We will improve the more-than-40-year-old value for the lower bound from $5/4$ to $4/3 - \varepsilon$. Additionally, we will show that this lower bound holds even in the special case of squares, where the previously known lower bound was $12/11 -\varepsilon$. These lower bounds apply regardless of the ordering of the rectangles. When squares are arranged in the worst possible order, we establish a constant upper bound and a $10/3-\varepsilon$ lower bound for the approximation ratio of the bottom-left algorithm. This bound also applies to some online setting and yields an almost tight result there. Finally, we show that the approximation ratio of a local search algorithm based on permuting rectangles in the ordering of the bottom-left algorithm is at least~$2$ and that such an algorithm may need an exponential number of improvement steps to reach a local optimum.

ABSTRACT. Polygon simplification is an important building block in many geovisualization algorithms. Recently, the concept of shortcut hulls was proposed to obtain a simplified polygon that fully contains the original polygon. Given a set of potential shortcuts between the polygon vertices, the computation of the optimal shortcut hull crucially relies on identifying edge crossings among the shortcuts and computing so called crossing components. In this paper, we present novel algorithms to significantly accelerate these steps. For a simple polygon $P$ with $n$ vertices and a set of shortcuts $\mathcal{C}$, we describe an algorithm for computing all edge crossings in $\mathcal{O}(n + m + k)$, where $m := |\mathcal{C}|$ and $k$ is the number of crossings. This output-sensitive algorithm is clearly optimal and a significant improvement over general-purpose algorithms to identify edge crossings. Furthermore, we extend this algorithm to compute the crossing components in $\mathcal{O}(\min \{n + m + k, n^2\})$. As $k$ could potentially be up to $\Theta (n^4)$, this is a significant speed-up if only the crossing components are needed rather than each individual crossing. Finally, we propose a novel crossing component hierarchy data structure. It encodes the crossing components and allows to efficiently partition the polygon based thereupon. We show that our novel algorithms and data structures allow to significantly reduce the theoretical running time of shortcut hull computation.

ABSTRACT. The R+-F+- Consistency problem is a basic problem related to the construction of phylogenetic trees. Its input is two sets R+ and R- of resolved triplets and two sets F+ and F- of unresolved triplets (also known as fan triplets). The objective of the problem is to determine if there exists a phylogenetic tree that includes all elements in R+ ∪ F+ and excludes all elements in R- ∪ F- as embedded subtrees, and to construct such a tree if one exists. Jansson et al. [Journal of Computational Biology, 2018] cataloged the computational complexity of the problem under various restrictions, with four notable exceptions in which the output tree is required to be ternary, i.e., has degree at most three. Here, we resolve these four remaining cases by proving that for ternary trees: (i) F+ Consistency as well as R+F+ Consistency are solvable in polynomial time; and (ii) F+- Consistency and R+F+- Consistency are NP-hard. To obtain (i), we develop a novel way of expressing the triplets consistency problem for ternary trees as a system of equations whose nontrivial solutions can be used to partition the leaf labels into subsets that label subtrees of the output tree. Result (ii) is obtained after observing some new equivalences between resolved triplets and fan triplets consistent with a given phylogenetic tree.

ABSTRACT. For every graph $G$ with size $m$ and no connected component isomorphic to $K_2$, we prove that, for $L=(1,1,2,2,\dots,\lfloor m/2 \rfloor+2,\lfloor m/2 \rfloor+2)$, we can assign labels of $L$ to the edges of $G$ in an injective way so that no two adjacent vertices of $G$ are incident to the same sum of labels. This implies that every such graph with size $m$ can be labelled in an equitable and proper way with labels from $\{1,\dots,\lfloor m/2 \rfloor+2\}$, which improves on a result proved by Haslegrave, and Szabo Lyngsie and Zhong, implying this can be achieved with labels from $\{1,\dots,m\}$.

ABSTRACT. A set of vertices in a graph forms a potential maximal clique if there exists a minimal chordal completion in which it is a maximal clique. Potential maximal cliques were first introduced as a key tool to obtain an efficient, though exponential-time algorithm to compute the treewidth of a graph. As a byproduct, this allowed to compute the treewidth of various graph classes in polynomial time.

In recent years, the concept of potential maximal cliques regained interest as it proved to be useful for a handful of graph algorithmic problems. In particular, it turned out to be a key tool to obtain a polynomial time algorithm for computing maximum weight independent sets in P5-free and P6-free graphs (Lokshtanov et al., SODA `14 and Grzeskik et al., SODA `19).

In most of their applications, obtaining all the potential maximal cliques constitutes an algorithmic bottleneck, thus motivating the question of how to efficiently enumerate all the potential maximal cliques in a graph G.

The state-of-the-art algorithm by Bouchitté & Todinca can enumerate potential maximal cliques in output-polynomial time by using exponential space, a significant limitation for the size of feasible instances. In this paper, we revisit this algorithm and design an enumeration algorithm that preserves an output-polynomial time complexity while only requiring polynomial space.

ABSTRACT. The cycle double cover conjecture states that for every bridgeless graph $G$, there exists a family $\mathcal{F}$ of cycles such that each edge of the graph is contained in exactly two members of $\mathcal{F}$. Given an embedding of a graph $G$, an edge $e$ is called a \emph{bad edge} if it is visited twice by the boundary of one face. CDC conjecture is equivalent to bridgeless cubic graphs having an embedding with no bad edge. In this work, we introduce non-trivial upper bounds on the minimum number of bad edges in an embedding of a cubic graph. Moreover, we present efficient algorithms to find embeddings satisfying these bounds.

ABSTRACT. In this paper, we consider a special case of the matroids intersection problem that is, given a set of graphs with the same set of vertices, choosing a minimum cycle basis for each of these graphs such that the intersection of these bases has maximal size. For this problem with applications in chemoinformatics, we give a complete dichotomy of the complexity of this problem based on three natural parameters that are the number of graphs, the maximum degree of the graphs and the size of a longest cycle in a minimum cycle basis of those graphs. Those results are completed by approximability and parameterized complexity results of the problem.