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
Cláudio Carvalho ; Jonas Costa ; Raul Lopes ; Ana Karolinna Maia ; Nicolas Nisse ; Cláudia Sales.
An s-branching flow f in a network N = (D, u), where u is the capacity function, is a flow thatreaches every vertex in V(D) from s while loosing exactly one unit of flow in each vertex other thans. Bang-Jensen and Bessy [TCS, 2014] showed that, when every arc has capacity n − 1, a network Nadmits k arc-disjoint s-branching flows if and only if its associated digraph D contains k arc-disjoints-branchings. Thus a classical result by Edmonds stating that a digraph contains k arc-disjoints-branchings if and only if the indegree of every set X ⊆ V (D) \ {s} is at least k also characterizesthe existence of k arc-disjoint s-branching flows in those networks, suggesting that the larger thecapacities are, the closer an s-branching flow is from simply being an s-branching. This observationis further implied by results by Bang-Jensen et al. [DAM, 2016] showing that there is a polynomialalgorithm to find the flows (if they exist) when every arc has capacity n − c, for every fixed c ≥ 1,and that such an algorithm is unlikely to exist for most other choices of the capacities. In this paper,we investigate how a property that is a natural extension of the characterization by Edmonds’ relatesto the existence of k arc-disjoint s-branching flows in networks. Although this property is alwaysnecessary for the existence of the flows, we show that it is not always sufficient and that it is hardto decide if the desired flows exist even if we know beforehand that the network satisfies it. […]
Section:
Graph Theory
Altar Çiçeksiz ; Yunus Emre Demirci ; Ümit Işlak.
We obtain an explicit formula for the variance of the number of $k$-peaks in
a uniformly random permutation. This is then used to obtain an asymptotic
formula for the variance of the length of longest $k$-alternating subsequence
in random permutations. Also a central limit is proved for the latter
statistic.
Section:
Combinatorics
Peixue Zhao ; Fei Huang.
An edge-colored graph is \emph{rainbow }if no two edges of the graph have the
same color. An edge-colored graph $G^c$ is called \emph{properly colored} if
every two adjacent edges of $G^c$ receive distinct colors in $G^c$. A
\emph{strongly edge-colored} graph is a proper edge-colored graph such that
every path of length $3$ is rainbow. We call an edge-colored graph $G^c$
\emph{rainbow vertex pair-pancyclic} if any two vertices in $G^c$ are contained
in a rainbow cycle of length $\ell$ for each $\ell$ with $3 \leq \ell \leq n$.
In this paper, we show that every strongly edge-colored graph $G^c$ of order
$n$ with minimum degree $\delta \geq \frac{2n}{3}+1$ is rainbow vertex
pair-pancyclicity.
Section:
Graph Theory
Tatjana Zec ; Milana Grbić.
This paper considers the following three Roman domination graph invariants on
Kneser graphs:
Roman domination, total Roman domination, and signed Roman domination.
For Kneser graph $K_{n,k}$, we present exact values for Roman domination
number $\gamma_{R}(K_{n,k})$ and total Roman domination number
$\gamma_{tR}(K_{n,k})$ proving that for $n\geqslant k(k+1)$,
$\gamma_{R}(K_{n,k}) =\gamma_{tR}(K_{n,k}) = 2(k+1)$. For signed Roman
domination number $\gamma_{sR}(K_{n,k})$, the new lower and upper bounds for
$K_{n,2}$ are provided: we prove that for $n\geqslant 12$, the lower bound is
equal to 2, while the upper bound depends on the parity of $n$ and is equal to
3 if $n$ is odd, and equal to $5$ if $n$ is even. For graphs of smaller
dimensions, exact values are found by applying exact methods from literature.
Section:
Graph Theory
Balázs Keszegh.
Recently geometric hypergraphs that can be defined by intersections of
pseudohalfplanes with a finite point set were defined in a purely combinatorial
way. This led to extensions of earlier results about points and halfplanes to
pseudohalfplanes, including polychromatic colorings and discrete Helly-type
theorems about pseudohalfplanes.
Here we continue this line of research and introduce the notion of convex
sets of such pseudohalfplane hypergraphs. In this context we prove several
results corresponding to classical results about convexity, namely Helly's
Theorem, Carathéodory's Theorem, Kirchberger's Theorem, Separation Theorem,
Radon's Theorem and the Cup-Cap Theorem. These results imply the respective
results about pseudoconvex sets in the plane defined using pseudohalfplanes.
It turns out that most of our results can be also proved using oriented
matroids and topological affine planes (TAPs) but our approach is different
from both of them. Compared to oriented matroids, our theory is based on a
linear ordering of the vertex set which makes our definitions and proofs quite
different and perhaps more elementary. Compared to TAPs, which are continuous
objects, our proofs are purely combinatorial and again quite different in
flavor. Altogether, we believe that our new approach can further our
understanding of these fundamental convexity results.
Section:
Combinatorics
Nevil Anto ; Manu Basavaraju.
Gallai's path decomposition conjecture states that if $G$ is a connected
graph on $n$ vertices, then the edges of $G$ can be decomposed into at most
$\lceil \frac{n }{2} \rceil$ paths. A graph is said to be an odd semi-clique if
it can be obtained from a clique on $2k+1$ vertices by deleting at most $k-1$
edges. Bonamy and Perrett asked if the edges of every connected graph $G$ on
$n$ vertices can be decomposed into at most $\lfloor \frac{n}{2} \rfloor$ paths
unless $G$ is an odd semi-clique. A graph $G$ is said to be 2-degenerate if
every subgraph of $G$ has a vertex of degree at most $2$. In this paper, we
prove that the edges of any connected 2-degenerate graph $G$ on $n$ vertices
can be decomposed into at most $\lfloor \frac{n }{2} \rfloor$ paths unless $G$
is a triangle.
Section:
Graph Theory
Rudolf Grübel.
We discuss a notion of convergence for binary trees that is based on subtree
sizes. In analogy to recent developments in the theory of graphs, posets and
permutations we investigate some general aspects of the topology, such as a
characterization of the set of possible limits and its structure as a metric
space. For random trees the subtree size topology arises in the context of
algorithms for searching and sorting when applied to random input, resulting in
a sequence of nested trees. For these we obtain a structural result based on a
local version of exchangeability. This in turn leads to a central limit
theorem, with possibly mixed asymptotic normality.
Section:
Analysis of Algorithms
William Pettersson ; John Sylvester.
Twin-width is a graph width parameter recently introduced by Bonnet, Kim,
Thomassé & Watrigant. Given two graphs $G$ and $H$ and a graph product
$\star$, we address the question: is the twin-width of $G\star H$ bounded by a
function of the twin-widths of $G$ and $H$ and their maximum degrees? It is
known that a bound of this type holds for strong products (Bonnet, Geniet, Kim,
Thomassé & Watrigant; SODA 2021). We show that bounds of the same form hold
for Cartesian, tensor/direct, corona, rooted, replacement, and zig-zag
products. For the lexicographical product it is known that the twin-width of
the product of two graphs is exactly the maximum of the twin-widths of the
individual graphs (Bonnet, Kim, Reinald, Thomassé & Watrigant; IPEC 2021).
In contrast, for the modular product we show that no bound can hold. In
addition, we provide examples showing many of our bounds are tight, and give
improved bounds for certain classes of graphs.
Section:
Graph Theory