Manuel Lafond ; Ben Seamone ; Rezvan Sherkati.
Recently, a conjecture due to Hendry was disproved which stated that every
Hamiltonian chordal graph is cycle extendible. Here we further explore the
conjecture, showing that it fails to hold even when a number of extra
conditions are imposed. In particular, we show that Hendry's Conjecture fails
for strongly chordal graphs, graphs with high connectivity, and if we relax the
definition of "cycle extendible" considerably. We also consider the original
conjecture from a subtree intersection model point of view, showing that a
result of Abuieda et al is nearly best possible.
Section:
Graph Theory
Tiziana Calamoneri ; Angelo Monti ; Blerina Sinaimeri.
Motivated by the work on the domination number of directed de Bruijn graphs
and some of its generalizations, in this paper we introduce a natural
generalization of de Bruijn graphs (directed and undirected), namely
$t$-constrained de Bruijn graphs, where $t$ is a positive integer, and then
study the domination number of these graphs.
Within the definition of $t$-constrained de Bruijn graphs, de Bruijn and
Kautz graphs correspond to 1-constrained and 2-constrained de Bruijn graphs,
respectively. This generalization inherits many structural properties of de
Bruijn graphs and may have similar applications in interconnection networks or
bioinformatics.
We establish upper and lower bounds for the domination number on
$t$-constrained de Bruijn graphs both in the directed and in the undirected
case. These bounds are often very close and in some cases we are able to find
the exact value.
Section:
Graph Theory
Mitre C. Dourado ; Vitor S. Ponciano ; Rômulo L. O. da Silva.
A set of vertices $S$ of a graph $G$ is {\em monophonically convex} if every
induced path joining two vertices of $S$ is contained in $S$. The {\em
monophonic convex hull of $S$}, $\langle S \rangle$, is the smallest
monophonically convex set containing $S$. A set $S$ is {\em monophonic convexly
independent} if $v \not\in \langle S - \{v\} \rangle$ for every $v \in S$. The
{\em monophonic rank} of $G$ is the size of the largest monophonic convexly
independent set of $G$. We present a characterization of the monophonic
convexly independent sets. Using this result, we show how to determine the
monophonic rank of graph classes like bipartite, cactus, triangle-free, and
line graphs in polynomial time. Furthermore, we show that this parameter can
computed in polynomial time for $1$-starlike graphs, i.e., for split graphs,
and that its determination is $\NP$-complete for $k$-starlike graphs for any
fixed $k \ge 2$, a subclass of chordal graphs. We also consider this problem on
the graphs whose intersection graph of the maximal prime subgraphs is a tree.
Section:
Graph Theory
Richard C Brewster ; Arnott Kidner ; Gary MacGillivray.
A mixed graph is a set of vertices together with an edge set and an arc set.
An $(m,n)$-mixed graph $G$ is a mixed graph whose edges are each assigned one
of $m$ colours, and whose arcs are each assigned one of $n$ colours. A
\emph{switch} at a vertex $v$ of $G$ permutes the edge colours, the arc
colours, and the arc directions of edges and arcs incident with $v$. The group
of all allowed switches is $\Gamma$.
Let $k \geq 1$ be a fixed integer and $\Gamma$ a fixed permutation group. We
consider the problem that takes as input an $(m,n)$-mixed graph $G$ and asks if
there a sequence of switches at vertices of $G$ with respect to $\Gamma$ so
that the resulting $(m,n)$-mixed graph admits a homomorphism to an
$(m,n)$-mixed graph on $k$ vertices. Our main result establishes this problem
can be solved in polynomial time for $k \leq 2$, and is NP-hard for $k \geq 3$.
This provides a step towards a general dichotomy theorem for the
$\Gamma$-switchable homomorphism decision problem.
Section:
Graph Theory
Marc Distel ; Robert Hickingbotham ; Tony Huynh ; David R. Wood.
Dujmovi\'c, Joret, Micek, Morin, Ueckerdt and Wood [J. ACM 2020] proved that
for every graph $G$ with Euler genus $g$ there is a graph $H$ with treewidth at
most 4 and a path $P$ such that $G\subseteq H \boxtimes P \boxtimes
K_{\max\{2g,3\}}$. We improve this result by replacing "4" by "3" and with $H$
planar. We in fact prove a more general result in terms of so-called framed
graphs. This implies that every $(g,d)$-map graph is contained in $ H \boxtimes
P\boxtimes K_\ell$, for some planar graph $H$ with treewidth $3$, where
$\ell=\max\{2g\lfloor \frac{d}{2} \rfloor,d+3\lfloor\frac{d}{2}\rfloor-3\}$. It
also implies that every $(g,1)$-planar graph (that is, graphs that can be drawn
in a surface of Euler genus $g$ with at most one crossing per edge) is
contained in $H\boxtimes P\boxtimes K_{\max\{4g,7\}}$, for some planar graph
$H$ with treewidth $3$.
Section:
Graph Theory
Khaled Elbassioni.
Given a partially order set (poset) $P$, and a pair of families of ideals
$\mathcal{I}$ and filters $\mathcal{F}$ in $P$ such that each pair $(I,F)\in
\mathcal{I}\times\mathcal{F}$ has a non-empty intersection, the dualization
problem over $P$ is to check whether there is an ideal $X$ in $P$ which
intersects every member of $\mathcal{F}$ and does not contain any member of
$\mathcal{I}$. Equivalently, the problem is to check for a distributive lattice
$L=L(P)$, given by the poset $P$ of its set of joint-irreducibles, and two
given antichains $\mathcal{A},\mathcal{B}\subseteq L$ such that no
$a\in\mathcal{A}$ is dominated by any $b\in\mathcal{B}$, whether $\mathcal{A}$
and $\mathcal{B}$ cover (by domination) the entire lattice. We show that the
problem can be solved in quasi-polynomial time in the sizes of $P$,
$\mathcal{A}$ and $\mathcal{B}$, thus answering an open question in Babin and
Kuznetsov (2017). As an application, we show that minimal infrequent closed
sets of attributes in a rational database, with respect to a given implication
base of maximum premise size of one, can be enumerated in incremental
quasi-polynomial time.
Section:
Discrete Algorithms
Yen Hung Chen.
Given an undirected graph $G=(V,E)$ with a nonnegative edge length function
and an integer $p$, $0 < p < |V|$, the $p$-centdian problem is to find $p$
vertices (called the {\it centdian set}) of $V$ such that the {\it
eccentricity} plus {\it median-distance} is minimized, in which the {\it
eccentricity} is the maximum (length) distance of all vertices to their nearest
{\it centdian set} and the {\it median-distance} is the total (length) distance
of all vertices to their nearest {\it centdian set}. The {\it eccentricity}
plus {\it median-distance} is called the {\it centdian-distance}. The purpose
of the $p$-centdian problem is to find $p$ open facilities (servers) which
satisfy the quality-of-service of the minimum total distance ({\it
median-distance}) and the maximum distance ({\it eccentricity}) to their
service customers, simultaneously. If we converse the two criteria, that is
given the bound of the {\it centdian-distance} and the objective function is to
minimize the cardinality of the {\it centdian set}, this problem is called the
converse centdian problem. In this paper, we prove the $p$-centdian problem is
NP-Complete. Then we design the first non-trivial brute force exact algorithms
for the $p$-centdian problem and the converse centdian problem, respectively.
Finally, we design two approximation algorithms for both problems.
Section:
Discrete Algorithms
Ahmad Biniaz ; Kshitij Jain ; Anna Lubiw ; Zuzana Masárová ; Tillmann Miltzow ; Debajyoti Mondal ; Anurag Murty Naredla ; Josef Tkadlec ; Alexi Turcotte.
The input to the token swapping problem is a graph with vertices $v_1, v_2,
\ldots, v_n$, and $n$ tokens with labels $1, 2, \ldots, n$, one on each vertex.
The goal is to get token $i$ to vertex $v_i$ for all $i= 1, \ldots, n$ using a
minimum number of swaps, where a swap exchanges the tokens on the endpoints of
an edge. We present some results about token swapping on a tree, also known as
"sorting with a transposition tree":
1. An optimum swap sequence may need to perform a swap on a leaf vertex that
has the correct token (a "happy leaf"), disproving a conjecture of Vaughan.
2. Any algorithm that fixes happy leaves -- as all known approximation
algorithms for the problem do -- has approximation factor at least $4/3$.
Furthermore, the two best-known 2-approximation algorithms have approximation
factor exactly 2.
3. A generalized problem -- weighted coloured token swapping -- is
NP-complete on trees, even when they are restricted to be subdivided stars, but
solvable in polynomial time on paths and stars. In this version, tokens and
vertices have colours, and colours have weights. The goal is to get every token
to a vertex of the same colour, and the cost of a swap is the sum of the
weights of the two tokens involved.
Section:
Discrete Algorithms
Peter Dankelmann ; Sonwabile Mafunda ; Sufiyan Mallu.
The average distance of a vertex $v$ of a connected graph $G$ is the
arithmetic mean of the distances from $v$ to all other vertices of $G$. The
proximity $\pi(G)$ and the remoteness $\rho(G)$ of $G$ are the minimum and the
maximum of the average distances of the vertices of $G$, respectively.
In this paper, we give upper bounds on the remoteness and proximity for
graphs of given order, minimum degree and maximum degree. Our bounds are sharp
apart from an additive constant.
Section:
Graph Theory
Luciano Margara.
We study the following problem. Given a multiset $M$ of non-negative
integers, decide whether there exist and, in the positive case, compute two
non-trivial multisets whose Minkowski sum is equal to $M$. The Minkowski sum of
two multisets A and B is a multiset containing all possible sums of any element
of A and any element of B. This problem was proved to be NP-complete when
multisets are replaced by sets. This version of the problem is strictly related
to the factorization of boolean polynomials that turns out to be NP-complete as
well. When multisets are considered, the problem is equivalent to the
factorization of polynomials with non-negative integer coefficients. The
computational complexity of both these problems is still unknown.
The main contribution of this paper is a heuristic technique for decomposing
multisets of non-negative integers. Experimental results show that our
heuristic decomposes multisets of hundreds of elements within seconds
independently of the magnitude of numbers belonging to the multisets. Our
heuristic can be used also for factoring polynomials in N[x]. We show that,
when the degree of the polynomials gets larger, our technique is much faster
than the state-of-the-art algorithms implemented in commercial software like
Mathematica and MatLab.
Section:
Analysis of Algorithms
Paul Levrie ; John Campbell.
In 2010, Kh. Hessami Pilehrood and T. Hessami Pilehrood introduced generating function identities used to obtain series accelerations for values of Dirichlet's $\beta$ function, via the Markov--Wilf--Zeilberger method. Inspired by these past results, together with related results introduced by Chu et al., we introduce a variety of hypergeometric recurrences. We prove these recurrences using the WZ method, and we apply these recurrences to obtain series acceleration identities. We introduce a family of summations generalizing a Ramanujan-type series for $\frac{1}{\pi^2}$ due to Guillera, and a family of summations generalizing an accelerated series for Catalan's constant due to Lupa\c{s}, and many related results.
Section:
Analysis of Algorithms