Bounds on the domination number of a digraph

A vertex subset S of a digraph D is called a dominating set of D if every vertex not in S is adjacent from at least one vertex in S. The domination number of D, denoted by \(\gamma (D)\), is the minimum cardinality of a dominating set of D. The Slater number \(s\ell (D)\) is the smallest integer t such that t added to the sum of the first t terms of the non-increasing out-degree sequence of D is at least as large as the order of D. For any digraph D of order n with maximum out-degree \(\Delta ^+\), it is known that \(\gamma (D)\ge \lceil n/(\Delta ^++1)\rceil \). We show that \(\gamma (D)\ge s\ell (D)\ge \lceil n/(\Delta ^++1)\rceil \) and the difference between \(s\ell (D)\) and \(\lceil n/(\Delta ^++1)\rceil \) can be arbitrarily large. In particular, for an oriented tree T of order n with \(n_0\) vertices of out-degree 0, we show that \((n-n_0+1)/2\le s\ell (T)\le \gamma (T)\le 2s\ell (T)-1\) and moreover, each value between the lower bound \(s\ell (T)\) and the upper bound \(2s\ell (T)-1\) is attainable by \(\gamma (T)\) for some oriented trees. Further, we characterize the oriented trees T for which \(s\ell (T)=(n-n_0+1)/2\) hold and show that the difference between \(s\ell (T)\) and \((n-n_0+1)/2\) can be arbitrarily large. Some other elementary properties involving the Slater number are also presented.     

Optimization problems with color-induced budget constraints

In 1984, Gabow and Tarjan provided a very elegant and fast algorithm for the following problem: given a matroid defined on a red and blue colored ground set, determine a basis of minimum cost among those with k red elements, or decide that no such basis exists. In this paper, we investigate extensions of this problem from ordinary matroids to the more general notion of poset matroids which take precedence constraints on the ground set into account. We show that the problem on general poset matroids becomes -hard, already if the underlying partially ordered set (poset) consists of binary trees of height two. On the positive side, we present two algorithms: a pseudopolynomial one for integer polymatroids, i.e., the case where the poset consists of disjoint chains, and a polynomial algorithm for the problem to determine a minimum cost ideal of size l with k red elements, i.e., the uniform rank-l poset matroid, on series-parallel posets.     

A characterization of linearizable instances of the quadratic minimum spanning tree problem

We investigate special cases of the quadratic minimum spanning tree problem (QMSTP) on a graph \(G=(V,E)\) that can be solved as a linear minimum spanning tree problem. We give a characterization of such problems when G is a complete graph, which is the standard case in the QMSTP literature. We extend our characterization to a larger class of graphs that include complete bipartite graphs and cactuses, among others. Our characterization can be verified in \(O(|E|^2)\) time. In the case of complete graphs and when the cost matrix is given in factored form, we show that our characterization can be verified in O(|E|) time. Related open problems are also indicated.     

Uniqueness of equilibria in atomic splittable polymatroid congestion games

We study uniqueness of Nash equilibria in atomic splittable congestion games and derive a uniqueness result based on polymatroid theory: when the strategy space of every player is a bidirectional flow polymatroid, then equilibria are unique. Bidirectional flow polymatroids are introduced as a subclass of polymatroids possessing certain exchange properties. We show that important cases such as base orderable matroids can be recovered as a special case of bidirectional flow polymatroids. On the other hand we show that matroidal set systems are in some sense necessary to guarantee uniqueness of equilibria: for every atomic splittable congestion game with at least three players and non-matroidal set systems per player, there is an isomorphic game having multiple equilibria. Our results leave a gap between base orderable matroids and general matroids for which we do not know whether equilibria are unique.     

Subset sum problems with digraph constraints

We introduce and study optimization problems which are related to the well-known Subset Sum problem. In each new problem, a node-weighted digraph is given and one has to select a subset of vertices whose total weight does not exceed a given budget. Some additional constraints called digraph constraints and maximality need to be satisfied. The digraph constraint imposes that a node must belong to the solution if at least one of its predecessors is in the solution. An alternative of this constraint says that a node must belong to the solution if all its predecessors are in the solution. The maximality constraint ensures that no superset of a feasible solution is also feasible. The combination of these constraints provides four problems. We study their complexity and present some approximation results according to the type of input digraph, such as directed acyclic graphs and oriented trees.     

Approximability and exact resolution of the multidimensional binary vector assignment problem

In this paper we consider the multidimensional binary vector assignment problem. An input of this problem is defined by m disjoint multisets \(V^1, V^2, \ldots , V^m\), each composed of n binary vectors of size p. An output is a set of n disjoint m-tuples of vectors, where each m-tuple is obtained by picking one vector from each multiset \(V^i\). To each m-tuple we associate a p dimensional vector by applying the bit-wise AND operation on the m vectors of the tuple. The objective is to minimize the total number of zeros in these n vectors. We denote this problem by Open image in new window , and the restriction of this problem where every vector has at most c zeros by Open image in new window . Open image in new window was only known to be Open image in new window -hard, even for Open image in new window . We show that, assuming the unique games conjecture, it is Open image in new window -hard to Open image in new window -approximate Open image in new window for any fixed Open image in new window and Open image in new window . This result is tight as any solution is a Open image in new window -approximation. We also prove without assuming UGC that Open image in new window is Open image in new window -hard even for Open image in new window . Finally, we show that Open image in new window is polynomial-time solvable for fixed Open image in new window (which cannot be extended to Open image in new window ).     

Relation between the skew-rank of an oriented graph and the independence number of its underlying graph

An oriented graph \(G^\sigma \) is a digraph without loops or multiple arcs whose underlying graph is G. Let \(S\left( G^\sigma \right) \) be the skew-adjacency matrix of \(G^\sigma \) and \(\alpha (G)\) be the independence number of G. The rank of \(S(G^\sigma )\) is called the skew-rank of \(G^\sigma \), denoted by \(sr(G^\sigma )\). Wong et al. (Eur J Comb 54:76–86, 2016) studied the relationship between the skew-rank of an oriented graph and the rank of its underlying graph. In this paper, the correlation involving the skew-rank, the independence number, and some other parameters are considered. First we show that \(sr(G^\sigma )+2\alpha (G)\geqslant 2|V_G|-2d(G)\), where \(|V_G|\) is the order of G and d(G) is the dimension of cycle space of G. We also obtain sharp lower bounds for \(sr(G^\sigma )+\alpha (G),\, sr(G^\sigma )-\alpha (G)\), \(sr(G^\sigma )/\alpha (G)\) and characterize all corresponding extremal graphs.     

A simpler PTAS for connected <Emphasis Type="Italic">k</Emphasis>-path vertex cover in homogeneous wireless sensor network

Because of its application in the field of security in wireless sensor networks, k-path vertex cover (\(\hbox {VCP}_k\)) has received a lot of attention in recent years. Given a graph \(G=(V,E)\), a vertex set \(C\subseteq V\) is a k-path vertex cover (\(\hbox {VCP}_k\)) of G if every path on k vertices has at least one vertex in C, and C is a connected k-path vertex cover of G (\(\hbox {CVCP}_k\)) if furthermore the subgraph of G induced by C is connected. A homogeneous wireless sensor network can be modeled as a unit disk graph. This paper presents a new PTAS for \(\hbox {MinCVCP}_k\) on unit disk graphs. Compared with previous PTAS given by Liu et al., our method not only simplifies the algorithm and reduces the time-complexity, but also simplifies the analysis by a large amount.     

Minimum 2-distance coloring of planar graphs and channel assignment

A 2-distance k-coloring of a graph G is a proper k-coloring such that any two vertices at distance two get different colors. \(\chi _{2}(G)\)=min{k|G has a 2-distance k-coloring}. Wegner conjectured that for each planar graph G with maximum degree \(\Delta \), \(\chi _2(G) \le 7\) if \(\Delta \le 3\), \(\chi _2(G) \le \Delta +5\) if \(4\le \Delta \le 7\) and \(\chi _2(G) \le \lfloor \frac{3\Delta }{2}\rfloor +1\) if \(\Delta \ge 8\). In this paper, we prove that: (1) If G is a planar graph with maximum degree \(\Delta \le 5\), then \(\chi _{2}(G)\le 20\); (2) If G is a planar graph with maximum degree \(\Delta \ge 6\), then \(\chi _{2}(G)\le 5\Delta -7\).     

The matching extension problem in general graphs is co-NP-complete

A simple connected graph G with 2n vertices is said to be k-extendable for an integer k with \(0<k<n\) if G contains a perfect matching and every matching of cardinality k in G is a subset of some perfect matching. Lakhal and Litzler (Inf Process Lett 65(1):11–16, 1998) discovered a polynomial algorithm that decides whether a bipartite graph is k-extendable. For general graphs, however, it has been an open problem whether there exists a polynomial algorithm. The new result presented in this paper is that the extendability problem is co-NP-complete.