Stefan Balev ; Juan Jiménez Laredo ; Ioannis Lamprou ; Yoann Pigné ; Eric Sanlaville.
We examine the classic game of Cops and Robbers played on models of dynamic graphs, that is, graphs evolving over discrete time steps. At each time step, a graph instance is generated as a subgraph of the underlying graph of the model. The cops and the robber take their turns on the current graph instance. The cops win if they can capture the robber at some point in time. Otherwise, the robber wins. In the offline case, the players are fully aware of the evolution sequence, up to some finite time horizon T. We provide a O(n 2k+1 T) algorithm to decide whether a given evolution sequence for an underlying graph with n vertices is k-cop-win via a reduction to a reachability game. In the online case, there is no knowledge of the evolution sequence, and the game might go on forever. Also, each generated instance is required to be connected. We provide a nearly tight characterization for sparse underlying graphs, i.e., with at most linear number of edges. We prove λ + 1 cops suffice to capture the robber in any underlying graph with n − 1 + λ edges. Further, we define a family of underlying graphs with n−1+λ edges where λ−1 cops are necessary (and sufficient) for capture.
Section:
Discrete Algorithms
Ruben Ascoli ; Livia Betti ; Jacob Lehmann Duke ; Xuyan Liu ; Wyatt Milgrim ; Steven J. Miller ; Eyvindur A. Palsson ; Francisco Romero Acosta ; Santiago Velazquez Iannuzzelli.
In 1946, Erdős posed the distinct distance problem, which seeks to find
the minimum number of distinct distances between pairs of points selected from
any configuration of $n$ points in the plane. The problem has since been
explored along with many variants, including ones that extend it into higher
dimensions. Less studied but no less intriguing is Erdős' distinct angle
problem, which seeks to find point configurations in the plane that minimize
the number of distinct angles. In their recent paper "Distinct Angles in
General Position," Fleischmann, Konyagin, Miller, Palsson, Pesikoff, and Wolf
use a logarithmic spiral to establish an upper bound of $O(n^2)$ on the minimum
number of distinct angles in the plane in general position, which prohibits
three points on any line or four on any circle.
We consider the question of distinct angles in three dimensions and provide
bounds on the minimum number of distinct angles in general position in this
setting. We focus on pinned variants of the question, and we examine explicit
constructions of point configurations in $\mathbb{R}^3$ which use
self-similarity to minimize the number of distinct angles. Furthermore, we
study a variant of the distinct angles question regarding distinct angle chains
and provide bounds on the minimum number of distinct chains in $\mathbb{R}^2$
and $\mathbb{R}^3$.
Section:
Combinatorics
Juan Carlos García-Altamirano ; Mika Olsen ; Jorge Cervantes-Ojeda.
In 2020 Bang-Jensen et. al. generalized the Hajós join of two graphs to the
class of digraphs and generalized several results for vertex colorings in
digraphs. Although, as a consequence of these results, a digraph can be
obtained by Hajós constructions (directed Hajós join and identifying
non-adjacent vertices), determining the Hajós constructions to obtain the
digraph is a complex problem. In particular, Bang-Jensen et al. posed the
problem of determining the Hajós operations to construct the symmetric
5-cycle from the complete symmetric digraph of order 3 using only Hajós
constructions. We successfully adapted a rank-based genetic algorithm to solve
this problem by the introduction of innovative recombination and mutation
operators from graph theory. The Hajós Join became the recombination operator
and the identification of independent vertices became the mutation operator. In
this way, we were able to obtain a sequence of only 16 Hajós operations to
construct the symmetric cycle of order 5.
Section:
Discrete Algorithms
Rémy Belmonte ; Tesshu Hanaka ; Ioannis Katsikarelis ; Eun Jung Kim ; Michael Lampis.
We study a family of generalizations of Edge Dominating Set on directed
graphs called Directed $(p,q)$-Edge Dominating Set. In this problem an arc
$(u,v)$ is said to dominate itself, as well as all arcs which are at distance
at most $q$ from $v$, or at distance at most $p$ to $u$.
First, we give significantly improved FPT algorithms for the two most
important cases of the problem, $(0,1)$-dEDS and $(1,1)$-dEDS (that correspond
to versions of Dominating Set on line graphs), as well as polynomial kernels.
We also improve the best-known approximation for these cases from logarithmic
to constant. In addition, we show that $(p,q)$-dEDS is FPT parameterized by
$p+q+tw$, but W-hard parameterized by $tw$ (even if the size of the optimal is
added as a second parameter), where $tw$ is the treewidth of the underlying
graph of the input.
We then go on to focus on the complexity of the problem on tournaments. Here,
we provide a complete classification for every possible fixed value of $p,q$,
which shows that the problem exhibits a surprising behavior, including cases
which are in P; cases which are solvable in quasi-polynomial time but not in P;
and a single case $(p=q=1)$ which is NP-hard (under randomized reductions) and
cannot be solved in sub-exponential time, under standard assumptions.
Lélia Blin ; Laurent Feuilloley ; Gabriel Le Bouder.
Given a boolean predicate $\Pi$ on labeled networks (e.g., proper coloring,
leader election, etc.), a self-stabilizing algorithm for $\Pi$ is a distributed
algorithm that can start from any initial configuration of the network (i.e.,
every node has an arbitrary value assigned to each of its variables), and
eventually converge to a configuration satisfying $\Pi$. It is known that
leader election does not have a deterministic self-stabilizing algorithm using
a constant-size register at each node, i.e., for some networks, some of their
nodes must have registers whose sizes grow with the size $n$ of the networks.
On the other hand, it is also known that leader election can be solved by a
deterministic self-stabilizing algorithm using registers of $O(\log \log n)$
bits per node in any $n$-node bounded-degree network. We show that this latter
space complexity is optimal. Specifically, we prove that every deterministic
self-stabilizing algorithm solving leader election must use $\Omega(\log \log
n)$-bit per node registers in some $n$-node networks. In addition, we show that
our lower bounds go beyond leader election, and apply to all problems that
cannot be solved by anonymous algorithms.
Section:
Distributed Computing and Networking
Sylwia Cichacz ; Karol Suchan.
The following problem has been known since the 80's. Let $\Gamma$ be an
Abelian group of order $m$ (denoted $|\Gamma|=m$), and let $t$ and $m_i$, $1
\leq i \leq t$, be positive integers such that $\sum_{i=1}^t m_i=m-1$.
Determine when $\Gamma^*=\Gamma\setminus\{0\}$, the set of non-zero elements of
$\Gamma$, can be partitioned into disjoint subsets $S_i$, $1 \leq i \leq t$,
such that $|S_i|=m_i$ and $\sum_{s\in S_i}s=0$ for every $i$, $1 \leq i \leq
t$. It is easy to check that $m_i\geq 2$ (for every $i$, $1 \leq i \leq t$) and
$|I(\Gamma)|\neq 1$ are necessary conditions for the existence of such
partitions, where $I(\Gamma)$ is the set of involutions of $\Gamma$. It was
proved that the condition $m_i\geq 2$ is sufficient if and only if
$|I(\Gamma)|\in\{0,3\}$. For other groups (i.e., for which $|I(\Gamma)|\neq 3$
and $|I(\Gamma)|>1$), only the case of any group $\Gamma$ with
$\Gamma\cong(Z_2)^n$ for some positive integer $n$ has been analyzed completely
so far, and it was shown independently by several authors that $m_i\geq 3$ is
sufficient in this case. Moreover, recently Cichacz and Tuza proved that, if
$|\Gamma|$ is large enough and $|I(\Gamma)|>1$, then $m_i\geq 4$ is sufficient.
In this paper we generalize this result for every Abelian group of order $2^n$.
Namely, we show that the condition $m_i\geq 3$ is sufficient for $\Gamma$ such
that $|I(\Gamma)|>1$ and $|\Gamma|=2^n$, for every positive integer $n$. We
also present some applications of this result to […]
Section:
Combinatorics
Nils Jakob Eckstein ; Niels Grüttemeier ; Christian Komusiewicz ; Frank Sommer.
We study the computational complexity of $c$-Colored $P_\ell$ Deletion and
$c$-Colored $C_\ell$ Deletion. In these problems, one is given a
$c$-edge-colored graph and wants to destroy all induced $c$-colored paths or
cycles, respectively, on $\ell$ vertices by deleting at most $k$ edges. Herein,
a path or cycle is $c$-colored if it contains edges of $c$ distinct colors. We
show that $c$-Colored $P_\ell$ Deletion and $c$-Colored $C_\ell$ Deletion are
NP-hard for each non-trivial combination of $c$ and $\ell$. We then analyze the
parameterized complexity of these problems. We extend the notion of
neighborhood diversity to edge-colored graphs and show that both problems are
fixed-parameter tractable with respect to the colored neighborhood diversity of
the input graph. We also provide hardness results to outline the limits of
parameterization by the standard parameter solution size $k$. Finally, we
consider bicolored input graphs and show a special case of $2$-Colored $P_4$
Deletion that can be solved in polynomial time.
Section:
Graph Theory
Iztok Banič ; Andrej Taranenko.
Inspired by Lelek's idea from [Disjoint mappings and the span of spaces,
Fund. Math. 55 (1964), 199 -- 214], we introduce the novel notion of the span
of graphs. Using this, we solve the problem of determining the \emph{maximal
safety distance} two players can keep at all times while traversing a graph.
Moreover, their moves must be made with respect to certain move rules. For this
purpose, we introduce different variants of a span of a given connected graph.
All the variants model the maximum safety distance kept by two players in a
graph traversal, where the players may only move with accordance to a specific
set of rules, and their goal: visit either all vertices, or all edges. For each
variant, we show that the solution can be obtained by considering only
connected subgraphs of a graph product and the projections to the factors. We
characterise graphs in which it is impossible to keep a positive safety
distance at all moments in time. Finally, we present a polynomial time
algorithm that determines the chosen span variant of a given graph.
Section:
Graph Theory
Gerold Jäger ; Klas Markström ; Denys Shcherbak ; Lars-Daniel Öhman.
In this paper we first study $k \times n$ Youden rectangles of small orders.
We have enumerated all Youden rectangles for a range of small parameter values,
excluding the almost square cases where $k = n-1$, in a large scale computer
search. In particular, we verify the previous counts for $(n,k) = (7,3),
(7,4)$, and extend this to the cases $(11,5), (11,6), (13,4)$ and $(21,5)$. For
small parameter values where no Youden rectangles exist, we also enumerate
rectangles where the number of symbols common to two columns is always one of
two possible values, differing by 1, which we call \emph{near Youden
rectangles}. For all the designs we generate, we calculate the order of the
autotopism group and investigate to which degree a certain transformation can
yield other row-column designs, namely double arrays, triple arrays and sesqui
arrays. Finally, we also investigate certain Latin rectangles with three
possible pairwise intersection sizes for the columns and demonstrate that these
can give rise to triple and sesqui arrays which cannot be obtained from Youden
rectangles, using the transformation mentioned above.
Section:
Combinatorics