Doost Ali Mojdeh ; Iztok Peterin ; Babak Samadi ; Ismael G. Yero.
The packing number of a graph $G$ is the maximum number of closed
neighborhoods of vertices in $G$ with pairwise empty intersections. Similarly,
the open packing number of $G$ is the maximum number of open neighborhoods in
$G$ with pairwise empty intersections. We consider the packing and open packing
numbers on graph products. In particular we give a complete solution with
respect to some properties of factors in the case of lexicographic and rooted
products. For Cartesian, strong and direct products, we present several lower
and upper bounds on these parameters.
Section:
Graph Theory
Paweł Parys.
We consider nondeterministic higher-order recursion schemes as recognizers of languages of finite words or finite trees. We propose a type system that allows to solve the simultaneous-unboundedness problem (SUP) for schemes, which asks, given a set of letters A and a scheme G, whether it is the case that for every number n the scheme accepts a word (a tree) in which every letter from A appears at least n times. Using this type system we prove that SUP is (m-1)-EXPTIME-complete for word-recognizing schemes of order m, and m-EXPTIME-complete for tree-recognizing schemes of order m. Moreover, we establish the reflection property for SUP: out of an input scheme G one can create its enhanced version that recognizes the same language but is aware of the answer to SUP.
Section:
Automata, Logic and Semantics
Joost Engelfriet ; Heiko Vogler.
We introduce MSO graph storage types, and call a storage type MSO-expressible
if it is isomorphic to some MSO graph storage type. An MSO graph storage type
has MSO-definable sets of graphs as storage configurations and as storage
transformations. We consider sequential automata with MSO graph storage and
associate with each such automaton a string language (in the usual way) and a
graph language; a graph is accepted by the automaton if it represents a correct
sequence of storage configurations for a given input string. For each MSO graph
storage type, we define an MSO logic which is a subset of the usual MSO logic
on graphs. We prove a Büchi-Elgot-Trakhtenbrot theorem, both for the string
case and the graph case. Moreover, we prove that (i) each MSO graph
transduction can be used as storage transformation in an MSO graph storage
type, (ii) every automatic storage type is MSO-expressible, and (iii) the
pushdown operator on storage types preserves the property of
MSO-expressibility. Thus, the iterated pushdown storage types are
MSO-expressible.
Section:
Automata, Logic and Semantics
Jurek Czyzowicz ; Konstantinos Georgiou ; Evangelos Kranakis ; Lata Narayanan ; Jarda Opatrny ; Birgit Vogtenhuber.
Assume that two robots are located at the centre of a unit disk. Their goal
is to evacuate from the disk through an exit at an unknown location on the
boundary of the disk. At any time the robots can move anywhere they choose on
the disk, independently of each other, with maximum speed $1$. The robots can
cooperate by exchanging information whenever they meet. We study algorithms for
the two robots to minimize the evacuation time: the time when both robots reach
the exit.
In [CGGKMP14] the authors gave an algorithm defining trajectories for the two
robots yielding evacuation time at most $5.740$ and also proved that any
algorithm has evacuation time at least $3+ \frac{\pi}{4} + \sqrt{2} \approx
5.199$. We improve both the upper and lower bound on the evacuation time of a
unit disk. Namely, we present a new non-trivial algorithm whose evacuation time
is at most $5.628$ and show that any algorithm has evacuation time at least $3+
\frac{\pi}{6} + \sqrt{3} \approx 5.255$. To achieve the upper bound, we
designed an algorithm which proposes a forced meeting between the two robots,
even if the exit has not been found by either of them. We also show that such a
strategy is provably optimal for a related problem of searching for an exit
placed at the vertices of a regular hexagon.
Section:
Distributed Computing and Networking
Eric Duchêne ; Victor Marsault ; Aline Parreau ; Michel Rigo.
This work is a contribution to the study of rewrite games. Positions are
finite words, and the possible moves are defined by a finite number of local
rewriting rules. We introduce and investigate taking-and-merging games, that
is, where each rule is of the form a^k->epsilon.
We give sufficient conditions for a game to be such that the losing positions
(resp. the positions with a given Grundy value) form a regular language or a
context-free language. We formulate several related open questions in parallel
with the famous conjecture of Guy about the periodicity of the Grundy function
of octal games.
Finally we show that more general rewrite games quickly lead to undecidable
problems. Namely, it is undecidable whether there exists a winning position in
a given regular language, even if we restrict to games where each move strictly
reduces the length of the current position. We formulate several related open
questions in parallel with the famous conjecture of Guy about the periodicity
of the Grundy function of octal games.
Shanshan Zhang ; Xiumei Wang ; Jinjiang Yuan.
Lov{á}sz showed that a matching covered graph $G$ has an ear decomposition
starting with an arbitrary edge of $G$. Let $G$ be a graph which has a perfect
matching. We call $G$ cycle-nice if for each even cycle $C$ of $G$, $G-V(C)$
has a perfect matching. If $G$ is a cycle-nice matching covered graph, then $G$
has ear decompositions starting with an arbitrary even cycle of $G$. In this
paper, we characterize cycle-nice claw-free plane graphs. We show that the only
cycle-nice simple 3-connected claw-free plane graphs are $K_4$, $W_5$ and
$\overline C_6$. Furthermore, every cycle-nice 2-connected claw-free plane
graph can be obtained from a graph in the family ${\cal F}$ by a sequence of
three types of operations, where ${\cal F}$ consists of even cycles, a diamond,
$K_4$, and $\overline C_6$.
Section:
Graph Theory
Marcin Pilipczuk ; Manuel Sorge.
In the (binary) Distinct Vectors problem we are given a binary matrix A with
pairwise different rows and want to select at most k columns such that,
restricting the matrix to these columns, all rows are still pairwise different.
A result by Froese et al. [JCSS] implies a 2^2^(O(k)) * poly(|A|)-time
brute-force algorithm for Distinct Vectors. We show that this running time
bound is essentially optimal by showing that there is a constant c such that
the existence of an algorithm solving Distinct Vectors with running time
2^(O(2^(ck))) * poly(|A|) would contradict the Exponential Time Hypothesis.
Section:
Discrete Algorithms
Petr Kolman ; Martin Koutecký ; Hans Raj Tiwary.
We consider the convex hull $P_{\varphi}(G)$ of all satisfying assignments of
a given MSO formula $\varphi$ on a given graph $G$. We show that there exists
an extended formulation of the polytope $P_{\varphi}(G)$ that can be described
by $f(|\varphi|,\tau)\cdot n$ inequalities, where $n$ is the number of vertices
in $G$, $\tau$ is the treewidth of $G$ and $f$ is a computable function
depending only on $\varphi$ and $\tau.$
In other words, we prove that the extension complexity of $P_{\varphi}(G)$ is
linear in the size of the graph $G$, with a constant depending on the treewidth
of $G$ and the formula $\varphi$. This provides a very general yet very simple
meta-theorem about the extension complexity of polytopes related to a wide
class of problems and graphs. As a corollary of our main result, we obtain an
analogous result % for the weaker MSO$_1$ logic on the wider class of graphs of
bounded cliquewidth.
Furthermore, we study our main geometric tool which we term the glued product
of polytopes. While the glued product of polytopes has been known since the
'90s, we are the first to show that it preserves decomposability and
boundedness of treewidth of the constraint matrix. This implies that our
extension of $P_\varphi(G)$ is decomposable and has a constraint matrix of
bounded treewidth; so far only few classes of polytopes are known to be
decomposable. These properties make our extension useful in the construction of
algorithms.
Section:
Discrete Algorithms
Loïc Dubois ; Gwenaël Joret ; Guillem Perarnau ; Marcin Pilipczuk ; François Pitois.
Given a graph $G$ and an integer $p$, a coloring $f : V(G) \to \mathbb{N}$ is
\emph{$p$-centered} if for every connected subgraph $H$ of $G$, either $f$ uses
more than $p$ colors on $H$ or there is a color that appears exactly once in
$H$. The notion of $p$-centered colorings plays a central role in the theory of
sparse graphs. In this note we show two lower bounds on the number of colors
required in a $p$-centered coloring.
First, we consider monotone classes of graphs whose shallow minors have
average degree bounded polynomially in the radius, or equivalently (by a result
of Dvo\v{r}ák and Norin), admitting strongly sublinear separators. We
construct such a class such that $p$-centered colorings require a number of
colors super-polynomial in $p$. This is in contrast with a recent result of
Pilipczuk and Siebertz, who established a polynomial upper bound in the special
case of graphs excluding a fixed minor.
Second, we consider graphs of maximum degree $\Delta$. D\k{e}bski, Felsner,
Micek, and Schröder recently proved that these graphs have $p$-centered
colorings with $O(\Delta^{2-1/p} p)$ colors. We show that there are graphs of
maximum degree $\Delta$ that require $\Omega(\Delta^{2-1/p} p
\ln^{-1/p}\Delta)$ colors in any $p$-centered coloring, thus matching their
upper bound up to a logarithmic factor.
Section:
Graph Theory
Margaret Archibald ; Aubrey Blecher ; Charlotte Brennan ; Arnold Knopfmacher ; Stephan Wagner ; Mark Ward.
A sequence of geometric random variables of length $n$ is a sequence of $n$
independent and identically distributed geometric random variables ($\Gamma_1,
\Gamma_2, \dots, \Gamma_n$) where $\mathbb{P}(\Gamma_j=i)=pq^{i-1}$ for
$1~\leq~j~\leq~n$ with $p+q=1.$ We study the number of distinct adjacent two
letter patterns in such sequences. Initially we directly count the number of
distinct pairs in words of short length. Because of the rapid growth of the
number of word patterns we change our approach to this problem by obtaining an
expression for the expected number of distinct pairs in words of length $n$. We
also obtain the asymptotics for the expected number as $n \to \infty$.
Section:
Analysis of Algorithms
Raphael Steiner.
Neumann-Lara and Škrekovski conjectured that every planar digraph is 2-colourable. We show that this conjecture is equivalent to the more general statement that all oriented K_5-minor-free graphs are 2-colourable.
Section:
Graph Theory
Samvel Kh. Darbinyan.
Y. Manoussakis (J. Graph Theory 16, 1992, 51-59) proposed the following
conjecture.
\noindent\textbf{Conjecture}. {\it Let $D$ be a 2-strongly connected digraph
of order $n$ such that for all distinct pairs of non-adjacent vertices $x$, $y$
and $w$, $z$, we have $d(x)+d(y)+d(w)+d(z)\geq 4n-3$. Then $D$ is Hamiltonian.}
In this paper, we confirm this conjecture. Moreover, we prove that if a
digraph $D$ satisfies the conditions of this conjecture and has a pair of
non-adjacent vertices $\{x,y\}$ such that $d(x)+d(y)\leq 2n-4$, then $D$
contains cycles of all lengths $3, 4, \ldots , n$.
Section:
Graph Theory
Xiao-Lu Gao ; Shou-Jun Xu.
A graph $G$ is a cocomparability graph if there exists an acyclic transitive
orientation of the edges of its complement graph $\overline{G}$. LBFS$^{+}$ is
a variant of the generic Lexicographic Breadth First Search (LBFS), which uses
a specific tie-breaking mechanism. Starting with some ordering $\sigma_{0}$ of
$G$, let $\{\sigma_{i}\}_{i\geq 1}$ be the sequence of orderings such that
$\sigma_{i}=$LBFS$^{+}(G, \sigma_{i-1})$. The LexCycle($G$) is defined as the
maximum length of a cycle of vertex orderings of $G$ obtained via such a
sequence of LBFS$^{+}$ sweeps. Dusart and Habib conjectured in 2017 that
LexCycle($G$)=2 if $G$ is a cocomparability graph and proved it holds for
interval graphs. In this paper, we show that LexCycle($G$)=2 if $G$ is a
$\overline{P_{2}\cup P_{3}}$-free cocomparability graph, where a
$\overline{P_{2}\cup P_{3}}$ is the graph whose complement is the disjoint
union of $P_{2}$ and $P_{3}$. As corollaries, it's applicable for diamond-free
cocomparability graphs, cocomparability graphs with girth at least 4, as well
as interval graphs.
Section:
Graph Theory