Possible winner problems on partial tournaments: a parameterized study

We study possible winner problems related to the uncovered set and the Banks set on partial tournaments from the viewpoint of parameterized complexity. We first study a problem where given a partial tournament D and a subset X of vertices, we are asked to add some arcs to D such that all vertices in X are included in the uncovered set. We focus on two parameterizations: parameterized by |X| and parameterized by the number of arcs to be added. In addition, we study a parameterized variant of the problem which is to determine whether all vertices of X can be included in the uncovered set by reversing at most k arcs. Finally, we study some parameterizations of a possible winner problem on partial tournaments, where we are given a partial tournament D and a distinguished vertex p, and asked whether D has a maximal transitive subtournament with p being the 0-indegree vertex. These parameterized problems are related to the Banks set. We achieve \(\mathcal {XP}\) results, \(\mathcal {W}\)-hardness results as well as \(\mathcal {FPT}\) results along with a kernelization lower bound for the problems studied in this paper.     

On the best possible competitive ratio for the multislope ski-rental problem

The multislope ski-rental problem is an extension of the classical ski-rental problem, where the player has several lease options besides the pure rent and buy options. In this problem the hardness of an instance, which is the setting of options, significantly affects the player’s performance. There is an algorithm that for a given instance, computes the best possible strategy. However, the output is given as numerical values and therefore the relational nature between an instance and the best possible performance for it has not been known. In this paper we prove that even for the easiest instance, a competitive ratio smaller than \(e/(e - 1) \approx 1.58\) cannot be achieved. More precisely, a tight lower bound on the best possible performance is obtained in a closed form parametrized by the number of options. Furthermore, we establish a matching upper and lower bound on the competitive ratio each for the 3-option and 4-option problems.     

Special cases of the quadratic shortest path problem

The quadratic shortest path problem (QSPP) is the problem of finding a path with prespecified start vertex s and end vertex t in a digraph such that the sum of weights of arcs and the sum of interaction costs over all pairs of arcs on the path is minimized. We first consider a variant of the QSPP known as the adjacent QSPP. It was recently proven that the adjacent QSPP on cyclic digraphs cannot be approximated unless \(\hbox {P}=\hbox {NP}\). Here, we give a simple proof for the same result. We also show that if the quadratic cost matrix is a symmetric weak sum matrix and all s–t paths have the same length, then an optimal solution for the QSPP can be obtained by solving the corresponding instance of the shortest path problem. Similarly, it is shown that the QSPP with a symmetric product cost matrix is solvable in polynomial time. Further, we provide sufficient and necessary conditions for a QSPP instance on a complete symmetric digraph with four vertices to be linearizable. We also characterize linearizable QSPP instances on complete symmetric digraphs with more than four vertices. Finally, we derive an algorithm that examines whether a QSPP instance on the directed grid graph \(G_{pq}\) (\(p,q\ge 2\)) is linearizable. The complexity of this algorithm is \({\mathcal {O}(p^{3}q^{2}+p^{2}q^{3})}\).     

Reconstruction of hidden graphs and threshold group testing

Classical group testing is a search paradigm where the goal is the identification of individual positive elements in a large collection of elements by asking queries of the form “Does a set of elements contain a positive one?”. A graph reconstruction problem that generalizes the classical group testing problem is to reconstruct a hidden graph from a given family of graphs by asking queries of the form “Whether a set of vertices induces an edge”. Reconstruction problems on families of Hamiltonian cycles, matchings, stars and cliques on n vertices have been studied where algorithms of using at most 2nlg?n,(1+o(1))(nlg?n),2n and 2n queries were proposed, respectively. In this paper we improve them to \((1+o(1))(n\lg n),(1+o(1))(\frac{n\lg n}{2}),n+2\lg n\) and n+lg?n, respectively. Threshold group testing is another generalization of group testing which is to identify the individual positive elements in a collection of elements under a more general setting, in which there are two fixed thresholds ? and u, with ?<u, and the response to a query is positive if the tested subset of elements contains at least u positive elements, negative if it contains at most ? positive elements, and it is arbitrarily given otherwise. For the threshold group testing problem with ?=u?1, we show that p positive elements among n given elements can be determined by using O(plg?n) queries, with a matching lower bound.     

Two extremal problems related to orders

We consider two extremal problems related to total orders on all subsets of \({\mathbb N}\). The first one is to maximize the Lagrangian of hypergraphs among all hypergraphs with m edges for a given positive integer m. In 1980’s, Frankl and Füredi conjectured that for a given positive integer m, the r-uniform hypergraph with m edges formed by taking the first m r-subsets of \({\mathbb N}\) in the colex order has the largest Lagrangian among all r-uniform hypergraphs with m edges. We provide some partial results for 4-uniform hypergraphs to this conjecture. The second one is for a given positive integer m, how to minimize the cardinality of the union closure families generated by edge sets of the r-uniform hypergraphs with m edges. Leck, Roberts and Simpson conjectured that the union closure family generated by the first m r-subsets of \({\mathbb N}\) in order U has the minimum cardinality among all the union closure families generated by edge sets of the r-uniform hypergraphs with m edges. They showed that the conjecture is true for graphs. We show that a similar result holds for non-uniform hypergraphs whose edges contain 1 or 2 vertices.     

ILP formulation of the degree-constrained minimum spanning hierarchy problem

Given a connected edge-weighted graph G and a positive integer B, the degree-constrained minimum spanning tree problem (DCMST) consists in finding a minimum cost spanning tree of G such that the degree of each vertex in the tree is less than or equal to B. This problem, which has been extensively studied over the last few decades, has several practical applications, mainly in networks. However, some applications do not especially impose a subgraph as a solution. For this purpose, a more flexible so-called hierarchy structure has been proposed. Hierarchy, which can be seen as a generalization of trees, is defined as a homomorphism of a tree in a graph. In this paper, we discuss the degree-constrained minimum spanning hierarchy (DCMSH) problem which is NP-hard. An integer linear program (ILP) formulation of this new problem is given. Properties of the solution are analysed, which allows us to add valid inequalities to the ILP. To evaluate the difference of cost between trees and hierarchies, the exact solution of DCMST and z problems are compared. It appears that, in sparse random graphs, the average percentage of improvement of the cost varies from 20 to 36% when the maximal authorized degree of vertices B is equal to 2, and from 11 to 31% when B is equal to 3. The improvement increases as the graph size increases.     

Cha n nel assig nme n t problem a nd n-fold t-separa ted $$L(j_1,j_2,\ldo ts,j_m)$$-labeli ng of graphs

This paper considers the channel assignment problem in mobile communications systems. Suppose there are many base stations in an area, each of which demands a number of channels to transmit signals. The channels assigned to the same base station must be separated in some extension, and two channels assigned to two different stations that are within a distance must be separated in some other extension according to the distance between the two stations. The aim is to assign channels to stations so that the interference is controlled within an acceptable level and the spectrum of channels used is minimized. This channel assignment problem can be modeled as the multiple t-separated \(L(j_1,j_2,\ldots ,j_m)\)-labeling of the interference graph. In this paper, we consider the case when all base stations demand the same number of channels. This case is referred as n-fold t-separated \(L(j_1,j_2,\ldots ,j_m)\)-labeling of a graph. This paper first investigates the basic properties of n-fold t-separated \(L(j_1,j_2,\ldots ,j_m)\)-labelings of graphs. And then it focuses on the special case when \(m=1\). The optimal n-fold t-separated L(j)-labelings of all complete graphs and almost all cycles are constructed. As a consequence, the optimal n-fold t-separated \(L(j_1,j_2,\ldots ,j_m)\)-labelings of the triangular lattice and the square lattice are obtained for the case \(j_1=j_2=\cdots =j_m\). This provides an optimal solution to the corresponding channel assignment problems with interference graphs being the triangular lattice and the square lattice, in which each base station demands a set of n channels that are t-separated and channels from two different stations at distance at most m must be \(j_1\)-separated. We also study a variation of n-fold t-separated \(L(j_1,j_2,\ldots ,j_m)\)-labeling, namely, n-fold t-separated consecutive \(L(j_1,j_2,\ldots ,j_m)\)-labeling. And present the optimal n-fold t-separated consecutive L(j)-labelings of all complete graphs and cycles.     

The popular matching and condensation problems under matroid constraints

The popular matching problem introduced by Abraham, Irving, Kavitha, and Mehlhorn is a matching problem in which there exist applicants and posts, and applicants have preference lists over posts. A matching M is said to be popular, if there exists no other matching N such that the number of applicants that prefer N to M is larger than the number of applicants that prefer M to N. The goal of this problem is to decide whether there exists a popular matching, and find a popular matching if one exists. In this paper, we first consider a matroid generalization of the popular matching problem with strict preference lists, and give a polynomial-time algorithm for this problem. In the second half of this paper, we consider the problem of transforming a given instance of a matroid generalization of the popular matching problem with strict preference lists by deleting a minimum number of applicants so that it has a popular matching. This problem is a matroid generalization of the popular condensation problem with strict preference lists introduced by Wu, Lin, Wang, and Chao. By using the results in the first half, we give a polynomial-time algorithm for this problem.     

Towards the price of leasing online

We consider online optimization problems in which certain goods have to be acquired in order to provide a service or infrastructure. Classically, decisions for such problems are considered as final: one buys the goods. However, in many real world applications, there is a shift away from the idea of buying goods. Instead, leasing is often a more flexible and lucrative business model. Research has realized this shift and recently initiated the theoretical study of leasing models (Anthony and Gupta in Proceedings of the integer programming and combinatorial optimization: 12th International IPCO Conference, Ithaca, NY, USA, June 25–27, 2007; Meyerson in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23–25 Oct 2005, Pittsburgh, PA, USA, 2005; Nagarajan and Williamson in Discret Optim 10(4):361–370, 2013) We extend this line of work and suggest a more systematic study of leasing aspects for a class of online optimization problems. We provide two major technical results. We introduce the leasing variant of online set multicover and give an \(O\left( \log (mK)\log n\right) \)-competitive algorithm (with n, m, and K being the number of elements, sets, and leases, respectively). Our results also imply improvements for the non-leasing variant of online set cover. Moreover, we extend results for the leasing variant of online facility location. Nagarajan and Williamson (Discret Optim 10(4):361–370, 2013) gave an \(O\left( K\log n\right) \)-competitive algorithm for this problem (with n and K being the number of clients and leases, respectively). We remove the dependency on n (and, thereby, on time). In general, this leads to a bound of \(O\left( l_{\text {max}} \log l_{\text {max}} \right) \) (with the maximal lease length \(l_{\text {max}} \)). For many natural problem instances, the bound improves to \(O\left( K^2\right) \).     

An approximation algorithm for the <Emphasis Type="Italic">k</Emphasis>-level capacitated facility location problem

We consider the k-level capacitated facility location problem (k-CFLP), which is a natural variant of the classical facility location problem and has applications in supply chain management. We obtain the first (combinatorial) approximation algorithm with a performance factor of \(k+2+\sqrt{k^{2}+2k+5}+\varepsilon\) (ε>0) for this problem.     

A tighter insertion-based approximation of the crossing number

Let G be a planar graph and F a set of additional edges not yet in G. The multiple edge insertion problem (MEI) asks for a drawing of \(G+F\) with the minimum number of pairwise edge crossings, such that the subdrawing of G is plane. Finding an exact solution to MEI is NP-hard for general F. We present the first polynomial time algorithm for MEI that achieves an additive approximation guarantee—depending only on the size of F and the maximum degree of G, in the case of connected G. Our algorithm seems to be the first directly implementable one in that realm, too, next to the single edge insertion. It is also known that an (even approximate) solution to the MEI problem would approximate the crossing number of the F-almost-planar graph \(G+F\), while computing the crossing number of \(G+F\) exactly is NP-hard already when \(|F|=1\). Hence our algorithm induces new, improved approximation bounds for the crossing number problem of F-almost-planar graphs, achieving constant-factor approximation for the large class of such graphs of bounded degrees and bounded size of F.     

Incremental Facility Location Problem and Its Competitive Algorithms

We consider the incremental version of the k-Facility Location Problem, which is a common generalization of the facility location and the k-median problems. The objective is to produce an incremental sequence of facility sets F ₁?F ₂?????F _n , where each F _k contains at most k facilities. An incremental facility sequence or an algorithm producing such a sequence is called c -competitive if the cost of each F _k is at most c times the optimum cost of corresponding k-facility location problem, where c is called competitive ratio. In this paper we present two competitive algorithms for this problem. The first algorithm produces competitive ratio 8α, where α is the approximation ratio of k-facility location problem. By recently result (Zhang, Theor. Comput. Sci. 384:126–135, 2007), we obtain the competitive ratio \(16+8\sqrt{3}+\epsilon\). The second algorithm has the competitive ratio Δ+1, where Δ is the ratio between the maximum and minimum nonzero interpoint distances. The latter result has its self interest, specially for the small metric space with Δ≤8α?1.     

On nonlinear multi-covering problems

In this paper we define the exact k-coverage problem, and study it for the special cases of intervals and circular-arcs. Given a set system consisting of a ground set of n points with integer demands \(\{d_0,\dots ,d_{n-1}\}\) and integer rewards, subsets of points, and an integer k, select up to k subsets such that the sum of rewards of the covered points is maximized, where point i is covered if exactly \(d_i\) subsets containing it are selected. Here we study this problem and some related optimization problems. We prove that the exact k-coverage problem with unbounded demands is NP-hard even for intervals on the real line and unit rewards. Our NP-hardness proof uses instances where some of the natural parameters of the problem are unbounded (each of these parameters is linear in the number of points). We show that this property is essential, as if we restrict (at least) one of these parameters to be a constant, then the problem is polynomial time solvable. Our polynomial time algorithms are given for various generalizations of the problem (in the setting where one of the parameters is a constant).     

An improved parameterized algorithm for the <Emphasis Type="Italic">p</Emphasis>-cluster vertex deletion problem

In the p-Cluster Vertex Deletion problem, we are given a graph \(G=(V,E)\) and two parameters k and p, and the goal is to determine if there exists a subset X of at most k vertices such that the removal of X results in a graph consisting of exactly p disjoint maximal cliques. Let \(r=p/k\). In this paper, we design a branching algorithm with time complexity \(O(\alpha ^k+|V||E|)\), where \(\alpha \) depends on r and has a rough upper bound \(\min \{1.618^{1+r},2\}\). With a more precise analysis, we show that \(\alpha =1.28\cdot 3.57^{r}\) for \(r\le 0.219\); \(\alpha =(1-r)^{r-1}r^{-r}\) for \(0.219< r<1/2\); and \(\alpha =2\) for \(r\ge 1/2\), respectively. Our algorithm also works with the same time complexity for the variant that the number of clusters is at most p. Our result improves the previous best time complexity \(O^*(1.84^{p+k})\) and implies that for fixed p the problem can be solved as efficiently as Vertex Cover.     

Approximation and hardness results for label cut and related problems

We investigate a natural combinatorial optimization problem called the Label Cut problem. Given an input graph G with a source s and a sink t, the edges of G are classified into different categories, represented by a set of labels. The labels may also have weights. We want to pick a subset of labels of minimum cardinality (or minimum total weight), such that the removal of all edges with these labels disconnects s and t. We give the first non-trivial approximation and hardness results for the Label Cut problem. Firstly, we present an \(O(\sqrt{m})\)-approximation algorithm for the Label Cut problem, where m is the number of edges in the input graph. Secondly, we show that it is NP-hard to approximate Label Cut within \(2^{\log ^{1-1/\log\log^{c}n}n}\) for any constant c<1/2, where n is the input length of the problem. Thirdly, our techniques can be applied to other previously considered optimization problems. In particular we show that the Minimum Label Path problem has the same approximation hardness as that of Label Cut, simultaneously improving and unifying two known hardness results for this problem which were previously the best (but incomparable due to different complexity assumptions).     

Efficient approximation algorithms for computing <Emphasis Type="Italic">k</Emphasis> disjoint constrained shortest paths

Let \(G=(V,\, E)\) be a given directed graph in which every edge e is associated with two nonnegative costs: a weight w(e) and a length l(e). For a pair of specified distinct vertices \(s,\, t\in V\), the k-(edge) disjoint constrained shortest path (kCSP) problem is to compute k (edge) disjoint paths between s and t, such that the total length of the paths is minimized and the weight is bounded by a given weight budget \(W\in \mathbb {R}_{0}^{+}\). The problem is known to be \({\mathcal {NP}}\)-hard, even when \(k=1\) (Garey and Johnson in Computers and intractability, 1979). Approximation algorithms with bifactor ratio \(\left( 1\,+\,\frac{1}{r},\, r\left( 1\,+\,\frac{2(\log r\,+\,1)}{r}\right) (1\,+\,\epsilon )\right) \) and \((1\,+\,\frac{1}{r},\,1\,+\,r)\) have been developed for \(k=2\) in Orda and Sprintson (IEEE INFOCOM, pp. 727–738, 2004) and Chao and Hong (IEICE Trans Inf Syst 90(2):465–472, 2007), respectively. For general k, an approximation algorithm with ratio \((1,\, O(\ln n))\) has been developed for a weaker version of kCSP, the k bi-constraint path problem which is to compute k disjoint st-paths satisfying a given length constraint and a weight constraint simultaneously (Guo et al. in COCOON, pp. 325–336, 2013). This paper first gives an approximation algorithm with bifactor ratio \((2,\,2)\) for kCSP using the LP-rounding technique. The algorithm is then improved by adopting a more sophisticated method to round edges. It is shown that for any solution output by the improved algorithm, there exists a real number \(0\le \alpha \le 2\) such that the weight and the length of the solution are bounded by \(\alpha \) times and \(2-\alpha \) times of that of an optimum solution, respectively. The key observation of the ratio proof is to show that the fractional edges, in a basic solution against the proposed linear relaxation of kCSP, exactly compose a graph in which the degree of every vertex is exactly two. At last, by a novel enhancement of the technique in Guo et al. (COCOON, pp. 325–336, 2013), the approximation ratio is further improved to \((1,\,\ln n)\).     

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.     

Approximation algorithms for the bus evacuation problem

We consider the bus evacuation problem. Given a positive integer B, a bipartite graph G with parts S and \(T \cup \{r\}\) in a metric space and functions \(l_i :S \rightarrow {\mathbb {Z}}_+\) and \({u_j :T \rightarrow \mathbb {Z}_+ \cup \{\infty \}}\), one wishes to find a set of B walks in G. Every walk in B should start at r and finish in T and r must be visited only once. Also, among all walks, each vertex i of S must be visited at least \(l_i\) times and each vertex j of T must be visited at most \(u_j\) times. The objective is to find a solution that minimizes the length of the longest walk. This problem arises in emergency planning situations where the walks correspond to the routes of B buses that must transport each group of people in S to a shelter in T, and the objective is to evacuate the entire population in the minimum amount of time. In this paper, we prove that approximating this problem by less than a constant is \(\text{ NP }\)-hard and present a 10.2-approximation algorithm. Further, for the uncapacitated BEP, in which \(u_j\) is infinity for each j, we give a 4.2-approximation algorithm.     

Some extremal results on the colorful monochromatic vertex-connectivity of a graph

A path in a vertex-colored graph is called a vertex-monochromatic path if its internal vertices have the same color. A vertex-coloring of a graph is a monochromatic vertex-connection coloring (MVC-coloring for short), if there is a vertex-monochromatic path joining any two vertices in the graph. For a connected graph G, the monochromatic vertex-connection number, denoted by mvc(G), is defined to be the maximum number of colors used in an MVC-coloring of G. These concepts of vertex-version are natural generalizations of the colorful monochromatic connectivity of edge-version, introduced by Caro and Yuster (Discrete Math 311:1786–1792, 2011). In this paper, we mainly investigate the Erd?s–Gallai-type problems for the monochromatic vertex-connection number mvc(G) and completely determine the exact value. Moreover, the Nordhaus–Gaddum-type inequality for mvc(G) is also given.     

FPT-algorithms for some problems related to integer programming

This paper studies a new version of the location problem called the mixed center location problem. Let P be a set of n points in the plane. We first consider the mixed 2-center problem, where one of the centers must be in P, and we solve it in \(O(n^2\log n)\) time. Second, we consider the mixed k-center problem, where m of the centers are in P, and we solve it in \(O(n^{m+O(\sqrt{k-m})})\) time. Motivated by two practical constraints, we propose two variations of the problem. Third, we present a 2-approximation algorithm and three heuristics solving the mixed k-center problem (\(k>2\)).