vol. 20 no. 2


1. Tropical Vertex-Disjoint Cycles of a Vertex-Colored Digraph: Barter Exchange with Multiple Items Per Agent

Highley, Timothy ; Le, Hoang.
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 […]
Section: Analysis of Algorithms

2. On fixed-parameter tractability of the mixed domination problem for graphs with bounded tree-width

Rajaati, M. ; Hooshmandasl, M. R. ; Dinneen, M. J. ; Shakiba, A..
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, […]
Section: Graph Theory

3. Convexity of tableau sets for type A Demazure characters (key polynomials), parabolic Catalan numbers

Proctor, Robert A. ; Willis, Matthew J..
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 […]
Section: Combinatorics