Rémy Belmonte ; Michael Lampis ; Valia Mitsou.
In Defective Coloring we are given a graph $G$ and two integers $\chi_d$,
$\Delta^*$ and are asked if we can $\chi_d$-color $G$ so that the maximum
degree induced by any color class is at most $\Delta^*$. We show that this
natural generalization of Coloring is much harder on several basic graph
classes. In particular, we show that it is NP-hard on split graphs, even when
one of the two parameters $\chi_d$, $\Delta^*$ is set to the smallest possible
fixed value that does not trivialize the problem ($\chi_d = 2$ or $\Delta^* =
1$). Together with a simple treewidth-based DP algorithm this completely
determines the complexity of the problem also on chordal graphs. We then
consider the case of cographs and show that, somewhat surprisingly, Defective
Coloring turns out to be one of the few natural problems which are NP-hard on
this class. We complement this negative result by showing that Defective
Coloring is in P for cographs if either $\chi_d$ or $\Delta^*$ is fixed; that
it is in P for trivially perfect graphs; and that it admits a sub-exponential
time algorithm for cographs when both $\chi_d$ and $\Delta^*$ are unbounded.
Section:
Discrete Algorithms
Nicolas Ollinger ; Guillaume Theyssier.
This paper studies three classes of cellular automata from a computational point of view: freezing cellular automata where the state of a cell can only decrease according to some order on states, cellular automata where each cell only makes a bounded number of state changes in any orbit, and finally cellular automata where each orbit converges to some fixed point. Many examples studied in the literature fit into these definitions, in particular the works on cristal growth started by S. Ulam in the 60s. The central question addressed here is how the computational power and computational hardness of basic properties is affected by the constraints of convergence, bounded number of change, or local decreasing of states in each cell. By studying various benchmark problems (short-term prediction, long term reachability, limits) and considering various complexity measures and scales (LOGSPACE vs. PTIME, communication complexity, Turing computability and arithmetical hierarchy) we give a rich and nuanced answer: the overall computational complexity of such cellular automata depends on the class considered (among the three above), the dimension, and the precise problem studied. In particular, we show that all settings can achieve universality in the sense of Blondel-Delvenne-K\r{u}rka, although short term predictability varies from NLOGSPACE to P-complete. Besides, the computability of limit configurations starting from computable initial configurations separates […]
Section:
Automata, Logic and Semantics
Isolde Adler ; Noleen Köhler.
Hamiltonian cycles in graphs were first studied in the 1850s. Since then, an
impressive amount of research has been dedicated to identifying classes of
graphs that allow Hamiltonian cycles, and to related questions. The
corresponding decision problem, that asks whether a given graph is Hamiltonian
(i.\,e.\ admits a Hamiltonian cycle), is one of Karp's famous NP-complete
problems. In this paper we study graphs of bounded degree that are \emph{far}
from being Hamiltonian, where a graph $G$ on $n$ vertices is \emph{far} from
being Hamiltonian, if modifying a constant fraction of $n$ edges is necessary
to make $G$ Hamiltonian. We give an explicit deterministic construction of a
class of graphs of bounded degree that are locally Hamiltonian, but (globally)
far from being Hamiltonian. Here, \emph{locally Hamiltonian} means that every
subgraph induced by the neighbourhood of a small vertex set appears in some
Hamiltonian graph. More precisely, we obtain graphs which differ in $\Theta(n)$
edges from any Hamiltonian graph, but non-Hamiltonicity cannot be detected in
the neighbourhood of $o(n)$ vertices. Our class of graphs yields a class of
hard instances for one-sided error property testers with linear query
complexity. It is known that any property tester (even with two-sided error)
requires a linear number of queries to test Hamiltonicity (Yoshida, Ito, 2010).
This is proved via a randomised construction of hard instances. In contrast,
our construction is deterministic. So far […]
Section:
Graph Theory
Toufik Mansour ; Mark Shattuck.
Let asc and desc denote respectively the statistics recording the number of ascents or descents in a sequence having non-negative integer entries. In a recent paper by Andrews and Chern, it was shown that the distribution of asc on the inversion sequence avoidance class $I_n(\geq,\neq,>)$ is the same as that of $n-1-\text{asc}$ on the class $I_n(>,\neq,\geq)$, which confirmed an earlier conjecture of Lin. In this paper, we consider some further enumerative aspects related to this equivalence and, as a consequence, provide an alternative proof of the conjecture. In particular, we find recurrence relations for the joint distribution on $I_n(\geq,\neq,>)$ of asc and desc along with two other parameters, and do the same for $n-1-\text{asc}$ and desc on $I_n(>,\neq,\geq)$. By employing a functional equation approach together with the kernel method, we are able to compute explicitly the generating function for both of the aforementioned joint distributions, which extends (and provides a new proof of) the recent result $|I_n(\geq,\neq,>)|=|I_n(>,\neq,\geq)|$. In both cases, an algorithm is formulated for computing the generating function of the asc distribution on members of each respective class having a fixed number of descents.
Section:
Combinatorics
Márcia R. Cappelle ; Erika Coelho ; Les R. Foulds ; Humberto J. Longo.
Let $G=(V(G),E(G))$ be a finite simple undirected graph with vertex set
$V(G)$, edge set $E(G)$ and vertex subset $S\subseteq V(G)$. $S$ is termed
\emph{open-dominating} if every vertex of $G$ has at least one neighbor in $S$,
and \emph{open-independent, open-locating-dominating} (an $OLD_{oind}$-set for
short) if no two vertices in $G$ have the same set of neighbors in $S$, and
each vertex in $S$ is open-dominated exactly once by $S$. The problem of
deciding whether or not $G$ has an $OLD_{oind}$-set has important applications
that have been reported elsewhere. As the problem is known to be
$\mathcal{NP}$-complete, it appears to be notoriously difficult as we show that
its complexity remains the same even for just planar bipartite graphs of
maximum degree five and girth six, and also for planar subcubic graphs of girth
nine. Also, we present characterizations of both $P_4$-tidy graphs and the
complementary prisms of cographs that have an $OLD_{oind}$-set.
Section:
Graph Theory
Meike Hatzel ; Pawel Komosa ; Marcin Pilipczuk ; Manuel Sorge.
A bramble in an undirected graph $G$ is a family of connected subgraphs of
$G$ such that for every two subgraphs $H_1$ and $H_2$ in the bramble either
$V(H_1) \cap V(H_2) \neq \emptyset$ or there is an edge of $G$ with one
endpoint in $V(H_1)$ and the second endpoint in $V(H_2)$. The order of the
bramble is the minimum size of a vertex set that intersects all elements of a
bramble.
Brambles are objects dual to treewidth: As shown by Seymour and Thomas, the
maximum order of a bramble in an undirected graph $G$ equals one plus the
treewidth of $G$. However, as shown by Grohe and Marx, brambles of high order
may necessarily be of exponential size: In a constant-degree $n$-vertex
expander a bramble of order $\Omega(n^{1/2+\delta})$ requires size exponential
in $\Omega(n^{2\delta})$ for any fixed $\delta \in (0,\frac{1}{2}]$. On the
other hand, the combination of results of Grohe and Marx and Chekuri and
Chuzhoy shows that a graph of treewidth $k$ admits a bramble of order
$\widetilde{\Omega}(k^{1/2})$ and size $\widetilde{\mathcal{O}}(k^{3/2})$.
($\widetilde{\Omega}$ and $\widetilde{\mathcal{O}}$ hide polylogarithmic
factors and divisors, respectively.)
In this note, we first sharpen the second bound by proving that every graph
$G$ of treewidth at least $k$ contains a bramble of order
$\widetilde{\Omega}(k^{1/2})$ and congestion $2$, i.e., every vertex of $G$ is
contained in at most two elements of the bramble (thus the bramble is of size
linear in its order). Second, we […]
Section:
Graph Theory
Anna M. Brandenberger ; Luc Devroye ; Marcel K. Goh ; Rosie Y. Zhao.
This note defines a notion of multiplicity for nodes in a rooted tree and
presents an asymptotic calculation of the maximum multiplicity over all leaves
in a Bienaymé-Galton-Watson tree with critical offspring distribution $\xi$,
conditioned on the tree being of size $n$. In particular, we show that if $S_n$
is the maximum multiplicity in a conditional Bienaymé-Galton-Watson tree,
then $S_n = \Omega(\log n)$ asymptotically in probability and under the further
assumption that ${\bf E}\{2^\xi\} < \infty$, we have $S_n = O(\log n)$
asymptotically in probability as well. Explicit formulas are given for the
constants in both bounds. We conclude by discussing links with an alternate
definition of multiplicity that arises in the root-estimation problem.
Section:
Analysis of Algorithms
Wenjie Fang.
Initiated by Davis, Nelson, Petersen and Tenner (2018), the enumerative study
of pinnacle sets of permutations has attracted a fair amount of attention
recently. In this article, we provide a recurrence that can be used to compute
efficiently the number $|\mathfrak{S}_n(P)|$ of permutations of size $n$ with a
given pinnacle set $P$, with arithmetic complexity $O(k^4 + k\log n)$ for $P$
of size $k$. A symbolic expression can also be computed in this way for
pinnacle sets of fixed size. A weighted sum $q_n(P)$ of $|\mathfrak{S}_n(P)|$
proposed in Davis, Nelson, Petersen and Tenner (2018) seems to have a simple
form, and a conjectural form is given recently by Flaque, Novelli and Thibon
(2021+). We settle the problem by providing and proving an alternative form of
$q_n(P)$, which has a strong combinatorial flavor. We also study admissible
orderings of a given pinnacle set, first considered by Rusu (2020) and
characterized by Rusu and Tenner (2021), and we give an efficient algorithm for
their counting.
Section:
Combinatorics
Ruy Fabila-Monroy ; Jesús Leaños ; Ana Laura Trujillo-Negrete.
Let $k$ and $n$ be integers such that $1\leq k \leq n-1$, and let $G$ be a
simple graph of order $n$. The $k$-token graph $F_k(G)$ of $G$ is the graph
whose vertices are the $k$-subsets of $V(G)$, where two vertices are adjacent
in $F_k(G)$ whenever their symmetric difference is an edge of $G$. In this
paper we show that if $G$ is a tree, then the connectivity of $F_k(G)$ is equal
to the minimum degree of $F_k(G)$.
Section:
Graph Theory
Angsuman Das ; Hiranya Kishore Dey.
The determining number of a graph $G = (V,E)$ is the minimum cardinality of a
set $S\subseteq V$ such that pointwise stabilizer of $S$ under the action of
$Aut(G)$ is trivial. In this paper, we provide some improved upper and lower
bounds on the determining number of Kneser graphs. Moreover, we provide the
exact value of the determining number for some subfamilies of Kneser graphs.
Section:
Graph Theory
Daniel Birmajer ; Juan B. Gil ; David S. Kenepp ; Michael D. Weiner.
Motivated by the study of pattern avoidance in the context of permutations
and ordered partitions, we consider the enumeration of weak-ordering chains
obtained as leaves of certain restricted rooted trees. A tree of order $n$ is
generated by inserting a new variable into each node at every step. A node
becomes a leaf either after $n$ steps or when a certain stopping condition is
met. In this paper we focus on conditions of size 2 ($x=y$, $x<y$, or $x\le y$)
and several conditions of size 3. Some of the cases considered here lead to the
study of descent statistics of certain `almost' pattern-avoiding permutations.
Section:
Combinatorics
Łukasz Bożyk ; Michał Pilipczuk.
We consider the Erdős-Pósa property for immersions and topological
minors in tournaments. We prove that for every simple digraph $H$, $k\in
\mathbb{N}$, and tournament $T$, the following statements hold:
(i) If in $T$ one cannot find $k$ arc-disjoint immersion copies of $H$, then
there exists a set of $\mathcal{O}_H(k^3)$ arcs that intersects all immersion
copies of $H$ in $T$.
(ii) If in $T$ one cannot find $k$ vertex-disjoint topological minor copies
of $H$, then there exists a set of $\mathcal{O}_H(k\log k)$ vertices that
intersects all topological minor copies of $H$ in $T$.
This improves the results of Raymond [DMTCS '18], who proved similar
statements under the assumption that $H$ is strongly connected.
Section:
Graph Theory
Kenjiro Takazawa.
An equitable partition into branchings in a digraph is a partition of the arc
set into branchings such that the sizes of any two branchings differ at most by
one. For a digraph whose arc set can be partitioned into $k$ branchings, there
always exists an equitable partition into $k$ branchings. In this paper, we
present two extensions of equitable partitions into branchings in digraphs:
those into matching forests in mixed graphs; and into $b$-branchings in
digraphs. For matching forests, Király and Yokoi (2022) considered a
tricriteria equitability based on the sizes of the matching forest, and the
matching and branching therein. In contrast to this, we introduce a
single-criterion equitability based on the number of covered vertices, which is
plausible in the light of the delta-matroid structure of matching forests.
While the existence of this equitable partition can be derived from a lemma in
Király and Yokoi, we present its direct and simpler proof. For
$b$-branchings, we define an equitability notion based on the size of the
$b$-branching and the indegrees of all vertices, and prove that an equitable
partition always exists. We then derive the integer decomposition property of
the associated polytopes.
Section:
Graph Theory
J. Leaños ; Christophe Ndjatchi ; L. M. Ríos-Castro.
Let $P$ be a set of $n\geq 3$ points in general position in the plane. The
edge disjointness graph $D(P)$ of $P$ is the graph whose vertices are all the
closed straight line segments with endpoints in $P$, two of which are adjacent
in $D(P)$ if and only if they are disjoint. We show that the connectivity of
$D(P)$ is at least
$\binom{\lfloor\frac{n-2}{2}\rfloor}{2}+\binom{\lceil\frac{n-2}{2}\rceil}{2}$,
and that this bound is tight for each $n\geq 3$.
Section:
Combinatorics
Jesse Racicot ; Giovanni Rosso.
Given a graph and an integer $k$, it is an NP-complete problem to decide
whether there is a dominating set of size at most $k$. In this paper we study
this problem for the Knödel Graph on $n$ vertices using elementary number
theory techniques. In particular, we show an explicit upper bound for the
domination number of the Knödel Graph on $n$ vertices any time that we can
find a prime number $p$ dividing $n$ for which $2$ is a primitive root.
Section:
Graph Theory
Andrei Asinowski ; Benjamin Hackl ; Sarah J. Selkirk.
The number of down-steps between pairs of up-steps in $k_t$-Dyck paths, a
generalization of Dyck paths consisting of steps $\{(1, k), (1, -1)\}$ such
that the path stays (weakly) above the line $y=-t$, is studied. Results are
proved bijectively and by means of generating functions, and lead to several
interesting identities as well as links to other combinatorial structures. In
particular, there is a connection between $k_t$-Dyck paths and perforation
patterns for punctured convolutional codes (binary matrices) used in coding
theory. Surprisingly, upon restriction to usual Dyck paths this yields a new
combinatorial interpretation of Catalan numbers.
Section:
Combinatorics
Prosenjit Bose ; Vida Dujmović ; Mehrnoosh Javarsineh ; Pat Morin ; David R. Wood.
Layered treewidth and row treewidth are recently introduced graph parameters
that have been key ingredients in the solution of several well-known open
problems. It follows from the definitions that the layered treewidth of a graph
is at most its row treewidth plus 1. Moreover, a minor-closed class has bounded
layered treewidth if and only if it has bounded row treewidth. However, it has
been open whether row treewidth is bounded by a function of layered treewidth.
This paper answers this question in the negative. In particular, for every
integer $k$ we describe a graph with layered treewidth 1 and row treewidth $k$.
We also prove an analogous result for layered pathwidth and row pathwidth.
Section:
Graph Theory
Helena Bergold ; Winfried Hochstättler ; Uwe Mayer.
We study the neighborhood polynomial and the complexity of its computation
for chordal graphs. The neighborhood polynomial of a graph is the generating
function of subsets of its vertices that have a common neighbor. We introduce a
parameter for chordal graphs called anchor width and an algorithm to compute
the neighborhood polynomial which runs in polynomial time if the anchor width
is polynomially bounded. The anchor width is the maximal number of different
sub-cliques of a clique which appear as a common neighborhood. Furthermore we
study the anchor width for chordal graphs and some subclasses such as chordal
comparability graphs and chordal graphs with bounded leafage. the leafage of a
chordal graphs is the minimum number of leaves in the host tree of a subtree
representation. We show that the anchor width of a chordal graph is at most
$n^{\ell}$ where $\ell$ denotes the leafage. This shows that for some
subclasses computing the neighborhood polynomial is possible in polynomial time
while it is NP-hard for general chordal graphs.
Section:
Graph Theory
Julien Baste ; Stefan Ehard ; Dieter Rautenbach.
We consider a non-monotone activation process $(X_t)_{t\in\{ 0,1,2,\ldots\}}$
on a graph $G$, where $X_0\subseteq V(G)$, $X_t=\{ u\in V(G):|N_G(u)\cap
X_{t-1}|\geq \tau(u)\}$ for every positive integer $t$, and $\tau:V(G)\to
\mathbb{Z}$ is a threshold function. The set $X_0$ is a so-called non-monotone
target set for $(G,\tau)$ if there is some $t_0$ such that $X_t=V(G)$ for every
$t\geq t_0$. Ben-Zwi, Hermelin, Lokshtanov, and Newman [Discrete Optimization 8
(2011) 87-96] asked whether a target set of minimum order can be determined
efficiently if $G$ is a tree. We answer their question in the affirmative for
threshold functions $\tau$ satisfying $\tau(u)\in \{ 0,1,d_G(u)\}$ for every
vertex~$u$. For such restricted threshold functions, we give a characterization
of target sets that allows to show that the minimum target set problem remains
NP-hard for planar graphs of maximum degree $3$ but is efficiently solvable for
graphs of bounded treewidth.
Section:
Graph Theory