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.     

A quadratic time exact algorithm for continuous connected 2-facility location problem in trees

This paper studies the continuous connected 2-facility location problem (CC2FLP) in trees. Let \(T = (V, E, c, d, \ell , \mu )\) be an undirected rooted tree, where each node \(v \in V\) has a weight \(d(v) \ge 0\) denoting the demand amount of v as well as a weight \(\ell (v) \ge 0\) denoting the cost of opening a facility at v, and each edge \(e \in E\) has a weight \(c(e) \ge 0\) denoting the cost on e and is associated with a function \(\mu (e,t) \ge 0\) denoting the cost of opening a facility at a point x(e, t) on e where t is a continuous variable on e. Given a subset \(\mathcal {D} \subseteq V\) of clients, and a subset \(\mathcal {F} \subseteq \mathcal {P}(T)\) of continuum points admitting facilities where \(\mathcal {P}(T)\) is the set of all the points on edges of T, when two facilities are installed at a pair of continuum points \(x_1\) and \(x_2\) in \(\mathcal {F}\), the total cost involved in CC2FLP includes three parts: the cost of opening two facilities at \(x_1\) and \(x_2\), K times the cost of connecting \(x_1\) and \(x_2\), and the cost of all the clients in \(\mathcal {D}\) connecting to some facility. The objective is to open two facilities at a pair of continuum points in \(\mathcal {F}\) to minimize the total cost, for a given input parameter \(K \ge 1\). This paper focuses on the case of \(\mathcal {D} = V\) and \(\mathcal {F} = \mathcal {P}(T)\). We first study the discrete version of CC2FLP, named the discrete connected 2-facility location problem (DC2FLP), where two facilities are restricted to the nodes of T, and devise a quadratic time edge-splitting algorithm for DC2FLP. Furthermore, we prove that CC2FLP is almost equivalent to DC2FLP in trees, and develop a quadratic time exact algorithm based on the edge-splitting algorithm. Finally, we adapt our algorithms to the general case of \(\mathcal {D} \subseteq V\) and \(\mathcal {F} \subseteq \mathcal {P}(T)\).     

A feasibility approach for constructing combinatorial designs of circulant type

In this work, we propose an optimization approach for constructing various classes of circulant combinatorial designs that can be defined in terms of autocorrelation. The problem is formulated as a so-called feasibility problem having three sets, to which the Douglas–Rachford projection algorithm is applied. The approach is illustrated on three different classes of circulant combinatorial designs: circulant weighing matrices, D-optimal matrices of circulant type, and Hadamard matrices with two circulant cores. Furthermore, we explicitly construct two new circulant weighing matrices, a CW(126, 64) and a CW(198, 100), whose existence was previously marked as unresolved in the most recent version of Strassler’s table.     

A continuous characterization of the maximum vertex-weighted clique in hypergraphs

For a simple graph G on n vertices with adjacency matrix A, Motzkin and Strauss established a remarkable connection between the clique number and the global maximum value of the quadratic programm: \(\textit{max}\{ \mathbf {x}^T A \mathbf {x}\}\) on the standard simplex: \(\{\sum _{i=1}^{n} x_i =1, x_i \ge 0 \}\). In Gibbons et al. (Math Oper Res 122:754–768, 1997), an extension of the Motzkin–Straus formulation was provided for the vertex-weighted clique number of a graph. In this paper, we provide a continuous characterization of the maximum vertex-weighted clique problem for vertex-weighted uniform hypergraphs.     

Blocking Rumor by Cut

In this paper, a rumor blocking problem is studied with an objective function which is neither submodular or supermodular. We will prove that this problem is NP-hard and give a data-dependent approximation with sandwich method. In addition, we show that every set function has a pair of monotone nondecreasing modular functions as upper bound and lower bound, respectively.