ABSTRACT. Cover-free families are families of finite sets where no set is contained in the union of d others. Superimposed codes, disjunct matrices, and strongly selective families are other names for the same combinatorial object. Cover-free families have applications in group testing, information retrieval, cryptography, and communications, among other areas.

Let us consider the incidence matrix representation of a family of sets, where rows correspond to elements and columns correspond to the characteristic vectors of the sets in the family. The cover-free property specifies that the union (logical-and) of any d columns of this binary matrix must not contain (cover) any other column. In our research, the cover-free property is generalized so that the edges of a hypergraph specify the sets of columns whose union must not cover any other column. Using this model, the classical cover-free family corresponds to the special case where the hypergraph is the d-uniform complete hypergraph. This generalization of cover-free families, which we call cover-free families on hypergraphs, is interesting combinatorially and motivated by applications. 

In this talk, we will begin with classical results on cover-free families,  and discuss initial results, constructions, and ongoing research on this new generalization involving hypergraphs. We will also discuss some of their applications in group testing and cryptography.

ABSTRACT. A Hamiltonian path (cycle) in a graph is a path (cycle, respectively) which passes through all of its vertices. The problems of deciding the existence of a Hamiltonian cycle (path) in an input graph are well known to be NP-complete, and restricted classes of graphs which allow for their polynomial-time solutions are intensively investigated. Until very recently the complexity was open even for graphs of independence number at most 3. So far unpublished result of Jedli\v{c}kov\'{a} and Kratochv\'{\i}l [arXiv:2309.09228] shows that for every integer $k$, Hamiltonian path and cycle are polynomial-time solvable in graphs of independence number bounded by $k$. As a companion structural result, we determine explicit obstacles for the existence of Hamiltonian path for small values of $k$, namely for graphs of independence number 2, 3, and 4. Identifying these obstacles in an input graph yields alternative polynomial-time algorithms for Hamiltonian path and cycle with no large hidden multiplicative constants.

ABSTRACT. Hub labeling (HL) comprises a class of algorithms that construct fast distance oracles on weighted graphs. The goal of HL is to assign each node a label such that the shortest path distance between any node pair can be deduced solely based on their label information. HL has been extensively studied from a theoretical and practical perspective, including parameterized upper bounds. It was shown that average label sizes in O(kappa * log n) are possible where kappa denotes the skeleton dimension of the graph. In this paper, we focus on a special type of HL, called path-consistent HL (PC-HL). This type of labeling is beneficial for fast shortest path extraction and compact storage. We prove novel parameterized upper bounds for path-consistent labelings (which also apply to HL). In particular, we show that label sizes can be bounded by O(gt * log n) where gt denotes the geodetic transversal number. Furthermore, we propose a new variant kappa+ of the skeleton dimension, show that there are graphs where kappa+ is a factor of Theta(sqrt n) smaller than kappa, and prove that O(kappa(+)* log n$ constitutes a valid upper bound for the label size of a PC-HL. We devise polytime algorithms to construct labelings that adhere to the parameterized upper bounds. Those are the first non-hierarchical labelings that are path-consistent, which were not known to exist before. Furthermore, we prove that gt and kappa(+) are incomparable. We compute their values on diverse benchmark graphs to assess which of them provides the tightest upper bound based on the graph structure.

ABSTRACT. Perfect Roman dominating functions and unique response Roman dominating functions are two ways to translate perfect code into the framework of Roman dominating functions. We also consider the enumeration of minimal perfect Roman dominating functions and show a tight relation to minimal Roman dominating functions. Furthermore, we consider the complexity of the underlying decision problems Perfect Roman Domination and Unique Response Roman Domination on special graph classes. Split graphs are the first graph class for which Unique Response Roman Domination is polynomial-time solvable while Perfect Roman Domination is NP-complete. Beyond this, we give polynomial-time algorithms for Perfect Roman Domination on interval graphs and for both decision problems on cobipartite graphs. However both problems are NP-complete on chordal bipartite graphs. We show that both problems are W[1]-complete if parameterized by solution size and FPT if parameterized by the dual parameter or by clique-width.

ABSTRACT. Temporal graphs are graphs that evolve over time. Many problems which are polynomial-time solvable in standard graphs become NP-hard when appropriately defined in the realm of temporal graphs. This suggested the definition of several parameters for temporal graphs and to prove the fixed-parameter tractability of several problems with respect to these parameters. In this paper, we introduce a hierarchy of parameters based on the previously defined interval membership width and on the temporal evolution of the connected components of the underlying static graph. We then show that the Eulerian trail problem and the temporal 2-coloring problem are both fixed-parameter tractable (in short, FPT) with respect to any of the parameters in the hierarchy. We also introduce a vertex-variant of the parameters and we show that the firefighter problem (which was known to be FPT with respect to the vertex-variant of the interval membership width) is also FPT with respect to one of the parameters in the second level of the hierarchy.

ABSTRACT. At STOC 2002, Eiter, Gottlob, and Makino presented a technique called ordered generation that yields an $n^{O(d)}$-delay algorithm listing all minimal transversals of an n-vertex hypergraph of degeneracy d. Recently at IWOCA 2019, Conte, Kanté, Marino, and Uno asked whether this XP-delay algorithm parameterized by d could be made FPT-delay for a weaker notion of degeneracy, or even parameterized by the maximum degree $\Delta$, i.e., whether it can be turned into an algorithm with delay $f(\Delta)\cdot n^{O(1)}$ for some computable function f. Moreover, and as a first step toward answering that question, they note that they could not achieve these time bounds even for the particular case of minimal dominating sets enumeration. In this paper, using ordered generation, we show that an FPT-delay algorithm can be devised for minimal transversals enumeration parameterized by the maximum degree and dimension, giving a positive and more general answer to the latter question.

ABSTRACT. The $d$-dimensional hypercube graph~$Q_d$ has as vertices all subsets of~$\{1,\ldots,d\}$, and an edge between any two sets that differ in a single element. The Ruskey-Savage conjecture asserts that every matching of~$Q_d$, $d\ge 2$, can be extended to a Hamilton cycle, i.e., to a cycle that visits every vertex exactly once. We prove that every matching of~$Q_d$, $d\ge 2$, can be extended to a cycle that visits at least a~$2/3$-fraction of all vertices.

ABSTRACT. We study the computational complexity of the Hamiltonian cycle problem on monotone classes of graphs, i.e. classes closed under taking subgraphs. We focus on classes defined by a single forbidden subgraph and present some necessary and some sufficient conditions for polynomial-time solvability of the problem in this case (assuming P ̸= NP). The main result is a polynomial-time algorithm to solve the problem for graphs excluding a certain tree, called the long-H, as a subgraph.

ABSTRACT. Consider a set of mobile computational elements, called robots, that are viewed as points, and operate in the Euclidean plane in synchronous rounds. The robots are oblivious (they forget all computations performed in previous rounds), silent (unable of direct communication), and anonymous (indistinguishable from the outside). Each robot is provided with a private coordinate system and can determine the position of the other robots (performing a Look operation); it has an algorithm, which it executes (performing a Compute operation) to determine a destination point; and it can move towards the destination (performing a Move operation).

The {\tt $k$-Grouping} problem requires the robots, starting from an arbitrary initial configuration in the plane, to gather at $k$ distinct locations, not chosen in advance, by performing Look-Compute-Move cycles, and no longer move. This simple problem is however unsolvable if the all the robots execute the same algorithm. It has been recently shown that, were different subgroups of the robots to execute different algorithms, the problem remains still unsolvable if the number of the algorithms is less than $k$.

In this paper we prove that this number is minimum: we design $k$ distinct algorithms and prove that, if each is executed by an arbitrary non-empty subset of the robots, they will collectively be able to solve the problem; furthermore, they are able to do so under a weak assumption on the level of agreement among the local coordinate systems. We further prove that, without any agreement, the problem becomes unsolvable even with $k+1$ different algorithms. However, if an unbounded number of algorithms are allowed such that each robot has a unique algorithm, then we can solve {\tt $k$-Grouping} without any agreement.

ABSTRACT. We consider \emph{weighted group search on a disk}, which is a search-type problem involving 2 mobile agents with unit-speed. The two agents start collocated and their goal is to reach a (hidden) target at an unknown location within a known distance of 1 (i.e., the search domain is the unit disk). The agents operate in the so-called \emph{wireless} model that allows them instantaneous knowledge of each others findings. The termination cost of agents' trajectories is the worst-case \emph{arithmetic weighted average}, which we quantify by parameter $w$, of the times it takes each agent to reach the target, hence the name of the problem. For this problem, we derive upper and lower bounds for the entire range of weighted averages, and the gap is tighter as the weights become more equal.

Our work follows a long line of research in search and evacuation, but quite importantly it is a variation and extension of two well-studied problems, respectively. The known variant is that where the search domain is the line, and for which an optimal solution is known. Our problem is also the extension of the so-called \emph{priority evacuation} problem that is obtained in our model by fixing $w=0$ for the objective function. For the latter problem the best upper/lower bound gap known is significant.

Our contributions for weighted group search on a disk are threefold. \textit{First}, we derive upper bounds for the entire spectrum of weighted averages. Our algorithms are obtained as a adaptations of known techniques, however the analysis is much more technical. \textit{Second}, our main contribution is the derivation of lower bounds for all weighted averages. This follows from a \emph{novel framework} for proving lower bounds for combinatorial search problems based on linear programming and inspired by metric embedding relaxations. \textit{Third}, we apply our framework to the priority evacuation problem, improving the previously best lower bound known from $4.38962$ to $4.56798$, thus reducing the upper/lower gap from $0.42892$ to $0.25056$.

ABSTRACT. We consider linear search for an escaping target whose speed and initial position are unknown to the searcher. A searcher (an autonomous mobile agent) is initially placed at the origin of the real line and can move with maximum speed 1 in either direction along the line. An oblivious mobile target that is moving away from the origin with an unknown constant speed v<1 is initially placed by an adversary on the infinite line at distance d from the origin in an unknown direction. We consider two cases, depending on whether d is known or unknown. The main contribution of this paper is to prove a new lower bound and give algorithms leading to new upper bounds for search in these settings. This results in an optimal (up to lower order terms in the exponent) competitive ratio in the case where d is known and improved upper and lower bounds for the case where d is unknown. Our results solve an open problem proposed in [Coleman et al., Proc. OPODIS 2022].

ABSTRACT. A drawing of a graph is $k$-planar if every edge has at most $k$ crossings with other edges of the graph and it is $k$-quasiplanar if it has no set of $k$ pairwise crossing edges. We say that a graph drawing is simple if two edges intersect at most once. In 2020, Angelini et al. proved that all simple $k$-planar graphs are simple $(k+1)$-quasiplanar, which was the first non-trivial relationship between these two classes. We say that a graph drawing is convex-geometric if its vertices are drawn as points on a circle and its edges are drawn as straight line segments between them. In this paper we prove that, for $k\ge2$, every convex-geometric $k$-planar graph is convex-geometric $(k+1)$-quasiplanar.

ABSTRACT. We deal with the problem of decomposing a complete geometric graph into plane star-forests. In particular, we disprove a recent conjecture by Pach, Saghafian and Schnider by constructing for each $n$ a complete geometric graph on $n$ vertices which can be decomposed into $\lceil\frac{n}{2}\rceil+1$ plane star-forests. Additionally we prove that for even $n$, every decomposition of complete abstract graph on $n$ vertices into $\frac{n}{2}+1$ star-forests is composed of a perfect matching and $\frac{n}{2}$ star-forests with two edge-balanced components, which we call broken double stars.