Some results on the target set selection problem

In this paper we consider a fundamental problem in the area of viral marketing, called Target Set Selection problem. We study the problem when the underlying graph is a block-cactus graph, a chordal graph or a Hamming graph. We show that if G is a block-cactus graph, then the Target Set Selection problem can be solved in linear time, which generalizes Chen’s result (Discrete Math. 23:1400–1415, 2009) for trees, and the time complexity is much better than the algorithm in Ben-Zwi et al. (Discrete Optim., 2010) (for bounded treewidth graphs) when restricted to block-cactus graphs. We show that if the underlying graph G is a chordal graph with thresholds θ(v)≤2 for each vertex v in G, then the problem can be solved in linear time. For a Hamming graph G having thresholds θ(v)=2 for each vertex v of G, we precisely determine an optimal target set S for (G,θ). These results partially answer an open problem raised by Dreyer and Roberts (Discrete Appl. Math. 157:1615–1627, 2009).     

Approximation algorithms for minimum weight partial connected set cover problem

In the Minimum Weight Partial Connected Set Cover problem, we are given a finite ground set \(U\), an integer \(q\le |U|\), a collection \(\mathcal {E}\) of subsets of \(U\), and a connected graph \(G_{\mathcal {E}}\) on vertex set \(\mathcal {E}\), the goal is to find a minimum weight subcollection of \(\mathcal {E}\) which covers at least \(q\) elements of \(U\) and induces a connected subgraph in \(G_{\mathcal {E}}\). In this paper, we derive a “partial cover property” for the greedy solution of the Minimum Weight Set Cover problem, based on which we present (a) for the weighted version under the assumption that any pair of sets in \(\mathcal {E}\) with nonempty intersection are adjacent in \(G_{\mathcal {E}}\) (the Minimum Weight Partial Connected Vertex Cover problem falls into this range), an approximation algorithm with performance ratio \(\rho (1+H(\gamma ))+o(1)\), and (b) for the cardinality version under the assumption that any pair of sets in \(\mathcal {E}\) with nonempty intersection are at most \(d\)-hops away from each other (the Minimum Partial Connected \(k\)-Hop Dominating Set problem falls into this range), an approximation algorithm with performance ratio \(2(1+dH(\gamma ))+o(1)\), where \(\gamma =\max \{|X|:X\in \mathcal {E}\}\), \(H(\cdot )\) is the Harmonic number, and \(\rho \) is the performance ratio for the Minimum Quota Node-Weighted Steiner Tree problem.     

A Branch and Cut solver for the maximum stable set problem

This paper deals with the cutting-plane approach to the maximum stable set problem. We provide theoretical results regarding the facet-defining property of inequalities obtained by a known project-and-lift-style separation method called edge-projection, and its variants. An implementation of a Branch and Cut algorithm is described, which uses edge-projection and two other separation tools which have been discussed for other problems: local cuts (pioneered by Applegate, Bixby, Chvátal and Cook) and mod-k cuts. We compare the performance of this approach to another one by Rossi and Smiriglio (Oper. Res. Lett. 28:63–74, 2001) and discuss the value of the tools we have tested.     

Parameterized dominating set problem in chordal graphs: complexity and lower bound

In this paper, we study the parameterized dominating set problem in chordal graphs. The goal of the problem is to determine whether a given chordal graph G=(V,E) contains a dominating set of size k or not, where k is an integer parameter. We show that the problem is W[1]-hard and it cannot be solved in time unless 3SAT can be solved in subexponential time. In addition, we show that the upper bound of this problem can be improved to when the underlying graph G is an interval graph.     

New analysis and computational study for the planar connected dominating set problem

The connected dominating set (CDS) problem is a well studied NP-hard problem with many important applications. Dorn et al. (Algorithmica 58:790–810 2010) introduce a branch-decomposition based algorithm design technique for NP-hard problems in planar graphs and give an algorithm (DPBF algorithm) which solves the planar CDS problem in \(O(2^{9.822\sqrt{n}}n+n^3)\) time and \(O(2^{8.11\sqrt{n}}n+n^3)\) time, with a conventional method and fast matrix multiplication in the dynamic programming step of the algorithm, respectively. We show that DPBF algorithm solves the planar CDS problem in \(O(2^{9.8\sqrt{n}}n+n^3)\) time with a conventional method and in \(O(2^{8.08\sqrt{n}}n+n^3)\) time with a fast matrix multiplication. For a graph \(G\), let \({\hbox {bw}}(G)\) be the branchwidth of \(G\) and \(\gamma _c(G)\) be the connected dominating number of \(G\). We prove \({\hbox {bw}}(G)\le 2\sqrt{10\gamma _c(G)}+32\). From this result, the planar CDS problem admits an \(O(2^{23.54\sqrt{\gamma _c(G)}}\gamma _c(G)+n^3)\) time fixed-parameter algorithm. We report computational study results on the practical performance of DPBF algorithm, which show that the size of instances can be solved by the algorithm mainly depends on the branchwidth of the instances, coinciding with the theoretical analysis. For graphs with small or moderate branchwidth, the CDS problem instances with size up to a few thousands edges can be solved in a practical time and memory space.     

Algorithms for the minimum weight k-fold (connected) dominating set problem

In this paper, we study the problem of computing a minimum weight k-fold dominating set (MWkDS) or a minimum weight k-fold connected dominating set (MWkCDS) in a unit ball graph (UBG). Using slab decomposition and dynamic programming, we give two exact algorithms for the computation of MWkDS and MWkCDS which can be executed in polynomial time if the thickness of the graph is bounded above.     

A greedy algorithm for the minimum 2-connected m-fold dominating set problem

To save energy and alleviate interference in a wireless sensor network, connected dominating set (CDS) has been proposed as the virtual backbone. Since nodes may fail due to accidental damage or energy depletion, it is desirable to construct a fault tolerant CDS, which can be modeled as a \(k\)-connected \(m\)-fold dominating set \(((k,m)\)-CDS for short): a subset of nodes \(C\subseteq V(G)\) is a \((k,m)\)-CDS of \(G\) if every node in \(V(G)\setminus C\) is adjacent with at least \(m\) nodes in \(C\) and the subgraph of \(G\) induced by \(C\) is \(k\)-connected.In this paper, we present an approximation algorithm for the minimum \((2,m)\)-CDS problem with \(m\ge 2\). Based on a \((1,m)\)-CDS, the algorithm greedily merges blocks until the connectivity is raised to two. The most difficult problem in the analysis is that the potential function used in the greedy algorithm is not submodular. By proving that an optimal solution has a specific decomposition, we managed to prove that the approximation ratio is \(\alpha +2(1+\ln \alpha )\), where \(\alpha \) is the approximation ratio for the minimum \((1,m)\)-CDS problem. This improves on previous approximation ratios for the minimum \((2,m)\)-CDS problem, both in general graphs and in unit disk graphs.     

A complexity dichotomy and a new boundary class for the dominating set problem

We study the computational complexity of the dominating set problem for hereditary graph classes, i.e., classes of simple unlabeled graphs closed under deletion of vertices. Every hereditary class can be defined by a set of its forbidden induced subgraphs. There are numerous open cases for the complexity of the problem even for hereditary classes with small forbidden structures. We completely determine the complexity of the problem for classes defined by forbidding a five-vertex path and any set of fragments with at most five vertices. Additionally, we also prove polynomial-time solvability of the problem for some two classes of a similar type. The notion of a boundary class is a helpful tool for analyzing the computational complexity of graph problems in the family of hereditary classes. Three boundary classes were known for the dominating set problem prior to this paper. We present a new boundary class for it.     

Algorithmic aspect on the minimum (weighted) doubly resolving set problem of graphs

Journal of Combinatorial Optimization - Let G be a simple graph, where each vertex has a nonnegative weight. A vertex subset S of G is a doubly resolving set (DRS) of G if for every pair of...     

A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs

In the minimum weighted dominating set problem (MWDS), we are given a unit disk graph with non-negative weight on each vertex. The MWDS seeks a subset of the vertices of the graph with minimum total weight such that each vertex of the graph is either in the subset or adjacent to some nodes in the subset. A?weight function is called smooth, if the ratio of the weights of any two adjacent nodes is upper bounded by a constant. MWDS is known to be NP-hard. In this paper, we give the first polynomial time approximation scheme (PTAS) for MWDS with smooth weights on unit disk graphs, which achieves a (1+ε)-approximation for MWDS, for any ε>0.     

The <Emphasis Type="Italic">k</Emphasis>-hop connected dominating set problem: approximation and hardness

Let G be a connected graph and k be a positive integer. A vertex subset D of G is a k-hop connected dominating set if the subgraph of G induced by D is connected, and for every vertex v in G there is a vertex u in D such that the distance between v and u in G is at most k. We study the problem of finding a minimum k-hop connected dominating set of a graph (\({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\)). We prove that \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\) is \(\mathscr {NP}\)-hard on planar bipartite graphs of maximum degree 4. We also prove that \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\) is \(\mathscr {APX}\)-complete on bipartite graphs of maximum degree 4. We present inapproximability thresholds for \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\) on bipartite and on (1, 2)-split graphs. Interestingly, one of these thresholds is a parameter of the input graph which is not a function of its number of vertices. We also discuss the complexity of computing this graph parameter. On the positive side, we show an approximation algorithm for \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\). Finally, when \(k=1\), we present two new approximation algorithms for the weighted version of the problem restricted to graphs with a polynomially bounded number of minimal separators.     

The mixed evacuation problem

A dynamic network introduced by Ford and Fulkerson is a directed graph with capacities and transit times on its arcs. The quickest transshipment problem is one of the most fundamental problems in dynamic networks. In this problem, we are given sources and sinks. Then the goal of this problem is to find a minimum time limit such that we can send the right amount of flow from sources to sinks. In this paper, we introduce a variant of this problem called the mixed evacuation problem. This problem models an emergent situation in which people can evacuate on foot or by car. The goal is to organize such a mixed evacuation so that an efficient evacuation can be achieved. In this paper, we study this problem from the theoretical and practical viewpoints. In the first part, we prove the polynomial-time solvability of this problem in the case where the number of sources and sinks is not large, and also prove the polynomial-time solvability and computational hardness of its variants with integer constraints. In the second part, we apply our model to the case study of Minabe town in Wakayama prefecture, Japan.     

Solving the minimum M-dominating set problem by a continuous optimization approach based on DC programming and DCA

We propose a new optimization approach based on DC (Difference of Convex functions) programming and DCA (DC Algorithm) to the so-called Minimum M-Dominating Set problem in graphs. This problem is beforehand re-casted as a polyhedral DC program with the help of exact penalty in DC programming. The related DCA is original and computer efficient because it consists of solving a few linear programs and converges after a finite number of iterations to an integer solution while working in a continuous domain. Numerical simulations show the efficiency and robustness of DCA and its superiority with respect to standard methods.     

The maximum dispersion problem

In the maximum dispersion problem, a given set of objects has to be partitioned into a number of groups. Each object has a non-negative weight and each group has a target weight, which may be different for each group. In addition to meeting the target weight of each group, all objects assigned to the same group should be as dispersed as possible with respect to some distance measure between pairs of objects. Potential applications for this problem come from such diverse fields as the problem of creating study groups or the design of waste collection systems. We develop and compare two different (mixed-) integer linear programming formulations for the problem. We also study a specific relaxation that enables us to derive tight bounds that improve the effectiveness of the formulations. Thereby, we obtain an upper bound by finding in an auxiliary graph subsets of given size with minimal diameter. A lower bound is derived based on the relation of the optimal solution of the relaxation to the chromatic number of a series of auxiliary graphs. Finally, we propose an exact solution scheme for the maximum dispersion problem and present extensive computational experiments to assess its efficiency.     

The loss-averse newsvendor problem

Newsvendor models are widely used in the literature, and usually based upon the assumption of risk neutrality. This paper uses loss aversion to model manager's decision-making behavior in the single-period newsvendor problem. We find that if shortage cost is not negligible, then a loss-averse newsvendor may order more than a risk-neutral newsvendor. We also find that the loss-averse newsvendor's optimal order quantity may increase in wholesale price and decrease in retail price, which can never occur in the risk-neutral newsvendor model.     

The subdivision-constrained routing requests problem

We are given a digraph D=(V,A;w), a length (delay) function w:A→R ⁺, a positive integer d and a set $\mathcal{P}=\{(s_{i},t_{i};B_{i}) | i=1,2,\ldots,k\}$ of k requests, where s _i ∈V is called as the ith source node, t _i ∈V is called the ith sink node and B _i is called as the ith length constraint. For a given positive integer d, the subdivision-constrained routing requests problem (SCRR, for short) is to find a directed subgraph D′=(V′,A′) of D, satisfying the two constraints: (1) Each request (s _i ,t _i ;B _i ) has a path P _i from s _i to t _i in D′ with length $w(P_{i})=\sum_{e\in P_{i}} w(e)$ no more than B _i ; (2) Insert some nodes uniformly on each arc e∈A′ to ensure that each new arc has length no more than d. The objective is to minimize the total number of the nodes inserted on the arcs in A′. We obtain the following three main results: (1) The SCRR problem is at least as hard as the set cover problem even if each request has the same source s, i.e., s _i =s for each i=1,2,…,k; (2) For each request (s,t;B), we design a dynamic programming algorithm to find a path from s to t with length no more than B such that the number of the nodes inserted on such a path is minimized, and as a corollary, we present a k-approximation algorithm to solve the SCRR problem for any k requests; (3) We finally present an optimal algorithm for the case where $\mathcal{P}$ contains all possible requests (s _i ,t _i ) in V×V and B _i is equal to the length of the shortest path in D from s _i to t _i . To the best of our knowledge, this is the first time that the dynamic programming algorithm within polynomial time in (2) is designed for a weighted optimization problem while previous optimal algorithms run in pseudo-polynomial time.