Timothy Highley ; Hoang Le.
In a barter exchange market, agents bring items and seek to exchange their
items with one another. Agents may agree to a k-way exchange involving a cycle
of k agents. A barter exchange market can be represented by a digraph where the
vertices represent items and the edges out of a vertex indicate the items that
an agent is willing to accept in exchange for that item. It is known that the
problem of finding a set of vertex-disjoint cycles with the maximum total
number of vertices (MAX-SIZE-EXCHANGE) can be solved in polynomial time. We
consider a barter exchange where each agent may bring multiple items, and items
of the same agent are represented by vertices with the same color. A set of
cycles is said to be tropical if for every color there is a cycle that contains
a vertex of that color. We show that the problem of determining whether there
exists a tropical set of vertex-disjoint cycles in a digraph
(TROPICAL-EXCHANGE) is NP-complete and APX-hard. This is equivalent to
determining whether it is possible to arrange an exchange of items among agents
such that every agent trades away at least one item. TROPICAL-MAX-SIZE-EXCHANGE
is a similar problem, where the goal is to find a set of vertex-disjoint cycles
that contains the maximum number of vertices and also contains all of the
colors in the graph. We show that this problem is likewise NP-complete and
APX-hard. For the restricted case where there are at most two vertices of each
color (corresponding to a restriction that […]
Section:
Analysis of Algorithms
M. Rajaati ; M. R. Hooshmandasl ; M. J. Dinneen ; A. Shakiba.
A mixed dominating set for a graph $G = (V,E)$ is a set $S\subseteq V \cup E$
such that every element $x \in (V \cup E) \backslash S$ is either adjacent or
incident to an element of $S$. The mixed domination number of a graph $G$,
denoted by $\gamma_m(G)$, is the minimum cardinality of mixed dominating sets
of $G$. Any mixed dominating set with the cardinality of $\gamma_m(G)$ is
called a minimum mixed dominating set. The mixed domination set (MDS) problem
is to find a minimum mixed dominating set for a graph $G$ and is known to be an
NP-complete problem. In this paper, we present a novel approach to find all of
the mixed dominating sets, called the AMDS problem, of a graph with bounded
tree-width $tw$. Our new technique of assigning power values to edges and
vertices, and combining with dynamic programming, leads to a fixed-parameter
algorithm of time $O(3^{tw^{2}}\times tw^2 \times |V|)$. This shows that MDS is
fixed-parameter tractable with respect to tree-width. In addition, we
theoretically improve the proposed algorithm to solve the MDS problem in
$O(6^{tw} \times |V|)$ time.
Section:
Graph Theory
Robert A. Proctor ; Matthew J. Willis.
This is the first of three papers that develop structures which are counted
by a "parabolic" generalization of Catalan numbers. Fix a subset R of
{1,..,n-1}. Consider the ordered partitions of {1,..,n} whose block sizes are
determined by R. These are the "inverses" of (parabolic) multipermutations
whose multiplicities are determined by R. The standard forms of the ordered
partitions are refered to as "R-permutations". The notion of 312-avoidance is
extended from permutations to R-permutations. Let lambda be a partition of N
such that the set of column lengths in its shape is R or R union {n}. Fix an
R-permutation pi. The type A Demazure character (key polynomial) in x_1, ..,
x_n that is indexed by lambda and pi can be described as the sum of the weight
monomials for some of the semistandard Young tableau of shape lambda that are
used to describe the Schur function indexed by lambda. Descriptions of these
"Demazure" tableaux developed by the authors in earlier papers are used to
prove that the set of these tableaux is convex in Z^N if and only if pi is
R-312-avoiding if and only if the tableau set is the entire principal ideal
generated by the key of pi. These papers were inspired by results of Reiner and
Shimozono and by Postnikov and Stanley concerning coincidences between Demazure
characters and flagged Schur functions. This convexity result is used in the
next paper to deepen those results from the level of polynomials to the […]
Section:
Combinatorics
Stefan Bard ; Thomas Bellitto ; Christopher Duffy ; Gary MacGillivray ; Feiran Yang.
For oriented graphs $G$ and $H$, a homomorphism $f: G \rightarrow H$ is
locally-injective if, for every $v \in V(G)$, it is injective when restricted
to some combination of the in-neighbourhood and out-neighbourhood of $v$. Two
of the possible definitions of local-injectivity are examined. In each case it
is shown that the associated homomorphism problem is NP-complete when $H$ is a
reflexive tournament on three or more vertices with a loop at every vertex, and
solvable in polynomial time when $H$ is a reflexive tournament on two or fewer
vertices.
Section:
Graph Theory
Zhuang Wei ; Hao Guoliang.
In this paper, we study a parameter that is squeezed between arguably the two
important domination parameters, namely the domination number, $\gamma(G)$, and
the total domination number, $\gamma_t(G)$. A set $S$ of vertices in $G$ is a
semitotal dominating set of $G$ if it is a dominating set of $G$ and every
vertex in S is within distance $2$ of another vertex of $S$. The semitotal
domination number, $\gamma_{t2}(G)$, is the minimum cardinality of a semitotal
dominating set of $G$. We observe that $\gamma(G)\leq \gamma_{t2}(G)\leq
\gamma_t(G)$. In this paper, we give a lower bound for the semitotal domination
number of trees and we characterize the extremal trees. In addition, we
characterize trees with equal domination and semitotal domination numbers.
Section:
Graph Theory
Mirjana Mikalački ; Miloš Stojaković.
We study the biased $(1:b)$ Maker--Breaker positional games, played on the
edge set of the complete graph on $n$ vertices, $K_n$. Given Breaker's bias
$b$, possibly depending on $n$, we determine the bounds for the minimal number
of moves, depending on $b$, in which Maker can win in each of the two standard
graph games, the Perfect Matching game and the Hamilton Cycle game.
Section:
Graph Theory
Olivier Baudon ; Julien Bensmail ; Jakub Przybyło ; Mariusz Woźniak.
The 1-2 Conjecture raised by Przybylo and Wozniak in 2010 asserts that every undirected graph admits a 2-total-weighting such that the sums of weights "incident" to the vertices yield a proper vertex-colouring. Following several recent works bringing related problems and notions (such as the well-known 1-2-3 Conjecture, and the notion of locally irregular decompositions) to digraphs, we here introduce and study several variants of the 1-2 Conjecture for digraphs. For every such variant, we raise conjectures concerning the number of weights necessary to obtain a desired total-weighting in any digraph. We verify some of these conjectures, while we obtain close results towards the ones that are still open.
Section:
Graph Theory
Yaping Mao ; Eddie Cheng ; Zhao Wang.
For a connected graph $G$ of order at least $2$ and $S\subseteq V(G)$, the
\emph{Steiner distance} $d_G(S)$ among the vertices of $S$ is the minimum size
among all connected subgraphs whose vertex sets contain $S$. Let $n$ and $k$ be
two integers with $2\leq k\leq n$. Then the \emph{Steiner $k$-eccentricity
$e_k(v)$} of a vertex $v$ of $G$ is defined by $e_k(v)=\max
\{d_G(S)\,|\,S\subseteq V(G), \ |S|=k, \ and \ v\in S\}$. Furthermore, the
\emph{Steiner $k$-diameter} of $G$ is $sdiam_k(G)=\max \{e_k(v)\,|\, v\in
V(G)\}$. In this paper, we investigate the Steiner distance and Steiner
$k$-diameter of Cartesian and lexicographical product graphs. Also, we study
the Steiner $k$-diameter of some networks.
Section:
Graph Theory
Chuanan Wei ; Lily Li Liu ; Dianxuan Gong.
By means of inversion techniques and several known hypergeometric series
identities, summation formulas for Fox-Wright function are explored. They give
some new hypergeometric series identities when the parameters are specified.
Section:
Combinatorics
Eric Angel ; Evripidis Bampis ; Bruno Escoffier ; Michael Lampis.
We study a recently introduced generalization of the Vertex Cover (VC)
problem, called Power Vertex Cover (PVC). In this problem, each edge of the
input graph is supplied with a positive integer demand. A solution is an
assignment of (power) values to the vertices, so that for each edge one of its
endpoints has value as high as the demand, and the total sum of power values
assigned is minimized. We investigate how this generalization affects the
parameterized complexity of Vertex Cover. On the positive side, when
parameterized by the value of the optimal P, we give an O*(1.274^P)-time
branching algorithm (O* is used to hide factors polynomial in the input size),
and also an O*(1.325^P)-time algorithm for the more general asymmetric case of
the problem, where the demand of each edge may differ for its two endpoints.
When the parameter is the number of vertices k that receive positive value, we
give O*(1.619^k) and O*(k^k)-time algorithms for the symmetric and asymmetric
cases respectively, as well as a simple quadratic kernel for the asymmetric
case. We also show that PVC becomes significantly harder than classical VC when
parameterized by the graph's treewidth t. More specifically, we prove that
unless the ETH is false, there is no n^o(t)-time algorithm for PVC. We give a
method to overcome this hardness by designing an FPT approximation scheme which
gives a (1+epsilon)-approximation to the optimal solution in time FPT in
parameters t and 1/epsilon.
Section:
Discrete Algorithms
Burak Ekici.
In this paper, we facilitate the reasoning about impure programming languages, by annotating terms with “decorations”that describe what computational (side) effect evaluation of a term may involve. In a point-free categorical language,called the “decorated logic”, we formalize the mutable state and the exception effects first separately, exploiting anice duality between them, and then combined. The combined decorated logic is used as the target language forthe denotational semantics of the IMP+Exc imperative programming language, and allows us to prove equivalencesbetween programs written in IMP+Exc. The combined logic is encoded in Coq, and this encoding is used to certifysome program equivalence proofs.
Section:
Automata, Logic and Semantics
Evan Chen ; Shyam Narayanan.
We present two families of Wilf-equivalences for consecutive and
quasi-consecutive vincular patterns. These give new proofs of the
classification of consecutive patterns of length $4$ and $5$. We then prove
additional equivalences to explicitly classify all quasi-consecutive patterns
of length $5$ into 26 Wilf-equivalence classes.
Section:
Combinatorics
José Cáceres ; Carmen Hernando ; Mercè Mora ; Ignacio M. Pelayo ; María Luz Puertas.
Dominating broadcasting is a domination-type structure that models a
transmission antenna network. In this paper, we study a limited version of this
structure, that was proposed as a common framework for both broadcast and
classical domination. In this limited version, the broadcast function is upper
bounded by an integer $k$ and the minimum cost of such function is the
dominating $k$-broadcast number. Our main result is a unified upper bound on
this parameter for any value of $k$ in general graphs, in terms of both $k$ and
the order of the graph. We also study the computational complexity of the
associated decision problem.
Section:
Graph Theory
Jean Cardinal ; Vera Sacristán ; Rodrigo I. Silveira.
Rectangulations are partitions of a square into axis-aligned rectangles. A
number of results provide bijections between combinatorial equivalence classes
of rectangulations and families of pattern-avoiding permutations. Other results
deal with local changes involving a single edge of a rectangulation, referred
to as flips, edge rotations, or edge pivoting. Such operations induce a graph
on equivalence classes of rectangulations, related to so-called flip graphs on
triangulations and other families of geometric partitions. In this note, we
consider a family of flip operations on the equivalence classes of diagonal
rectangulations, and their interpretation as transpositions in the associated
Baxter permutations, avoiding the vincular patterns { 3{14}2, 2{41}3 }. This
complements results from Law and Reading (JCTA, 2012) and provides a complete
characterization of flip operations on diagonal rectangulations, in both
geometric and combinatorial terms.
Section:
Combinatorics
Fábio Protti ; Uéverton S. Souza.
A graph $G$ is {\em matching-decyclable} if it has a matching $M$ such that
$G-M$ is acyclic. Deciding whether $G$ is matching-decyclable is an NP-complete
problem even if $G$ is 2-connected, planar, and subcubic. In this work we
present results on matching-decyclability in the following classes: Hamiltonian
subcubic graphs, chordal graphs, and distance-hereditary graphs. In Hamiltonian
subcubic graphs we show that deciding matching-decyclability is NP-complete
even if there are exactly two vertices of degree two. For chordal and
distance-hereditary graphs, we present characterizations of
matching-decyclability that lead to $O(n)$-time recognition algorithms.
Section:
Graph Theory
H. Galeana-Sánchez ; M. Olsen.
A digraph such that every proper induced subdigraph has a kernel is said to
be \emph{kernel perfect} (KP for short) (\emph{critical kernel imperfect} (CKI
for short) resp.) if the digraph has a kernel (does not have a kernel resp.).
The unique CKI-tournament is $\overrightarrow{C}_3$ and the unique
KP-tournaments are the transitive tournaments, however bipartite tournaments
are KP. In this paper we characterize the CKI- and KP-digraphs for the
following families of digraphs: locally in-/out-semicomplete, asymmetric
arc-locally in-/out-semicomplete, asymmetric $3$-quasi-transitive and
asymmetric $3$-anti-quasi-transitive $TT_3$-free and we state that the problem
of determining whether a digraph of one of these families is CKI is polynomial,
giving a solution to a problem closely related to the following conjecture
posted by Bang-Jensen in 1998: the kernel problem is polynomially solvable for
locally in-semicomplete digraphs.
Section:
Graph Theory
Tınaz Ekim ; Didem Gözüpek ; Ademir Hujdurović ; Martin Milanič.
We consider a relaxation of the concept of well-covered graphs, which are
graphs with all maximal independent sets of the same size. The extent to which
a graph fails to be well-covered can be measured by its independence gap,
defined as the difference between the maximum and minimum sizes of a maximal
independent set in $G$. While the well-covered graphs are exactly the graphs of
independence gap zero, we investigate in this paper graphs of independence gap
one, which we also call almost well-covered graphs. Previous works due to
Finbow et al. (1994) and Barbosa et al. (2013) have implications for the
structure of almost well-covered graphs of girth at least $k$ for $k\in
\{7,8\}$. We focus on almost well-covered graphs of girth at least $6$. We show
that every graph in this class has at most two vertices each of which is
adjacent to exactly $2$ leaves. We give efficiently testable characterizations
of almost well-covered graphs of girth at least $6$ having exactly one or
exactly two such vertices. Building on these results, we develop a
polynomial-time recognition algorithm of almost well-covered
$\{C_3,C_4,C_5,C_7\}$-free graphs.
Section:
Graph Theory
Alexander Büchel ; Ulrich Gilleßen ; Kurt-Ulrich Witt.
We present a polynomial time algorithm, which solves a nonstandard Variation
of the well-known PARTITION-problem: Given positive integers $n, k$ and $t$
such that $t \geq n$ and $k \cdot t = {n+1 \choose 2}$, the algorithm
partitions the elements of the set $I_n = \{1, \ldots, n\}$ into $k$ mutually
disjoint subsets $T_j$ such that $\cup_{j=1}^k T_j = I_n$ and $\sum_{x \in
T_{j}} x = t$ for each $j \in \{1,2, \ldots, k\}$. The algorithm needs
$\mathcal{O}(n \cdot ( \frac{n}{2k} + \log \frac{n(n+1)}{2k} ))$ steps to
insert the $n$ elements of $I_n$ into the $k$ sets $T_j$.
Section:
Discrete Algorithms
Ali Dehghan ; Mohammad-Reza Sadeghi ; Arash Ahadi.
A $\textit{sigma partitioning}$ of a graph $G$ is a partition of the vertices
into sets $P_1, \ldots, P_k$ such that for every two adjacent vertices $u$ and
$v$ there is an index $i$ such that $u$ and $v$ have different numbers of
neighbors in $P_i$. The $\textit{ sigma number}$ of a graph $G$, denoted by
$\sigma(G)$, is the minimum number $k$ such that $ G $ has a sigma partitioning
$P_1, \ldots, P_k$. Also, a $\textit{ lucky labeling}$ of a graph $G$ is a
function $ \ell :V(G) \rightarrow \mathbb{N}$, such that for every two adjacent
vertices $ v $ and $ u$ of $ G $, $ \sum_{w \sim v}\ell(w)\neq \sum_{w \sim
u}\ell(w) $ ($ x \sim y $ means that $ x $ and $y$ are adjacent). The $\textit{
lucky number}$ of $ G $, denoted by $\eta(G)$, is the minimum number $k $ such
that $ G $ has a lucky labeling $ \ell :V(G) \rightarrow \mathbb{N}_k$. It was
conjectured in [Inform. Process. Lett., 112(4):109--112, 2012] that it is $
\mathbf{NP} $-complete to decide whether $ \eta(G)=2$ for a given 3-regular
graph $G$. In this work, we prove this conjecture. Among other results, we give
an upper bound of five for the sigma number of a uniformly random graph.
Section:
Graph Theory