In the Maximum Independent Set problem we are asked to find a set of pairwise nonadjacent vertices in a given graph with the maximum possible cardinality. In general graphs, this classical problem is known to be NPhard and hard to approximate within a factor of n1−ε for any ε > 0. Due to this, investigating the complexity of Maximum Independent Set in various graph classes in hope of finding better tractability results is an active research direction.
In Hfree graphs, that is, graphs not containing a fixed graph H as an induced subgraph, the problem is known to remain NPhard and APXhard whenever H contains a cycle, a vertex of degree at least four, or two vertices of degree at least three in one connected component. For the remaining cases, where every component of H is a path or a subdivided claw, the complexity of Maximum Independent Set remains widely open, with only a handful of polynomialtime solvability results for small graphs H such as P5, P6, the claw, or the fork.
We prove that for every such “possibly tractable” graph H there exists an algorithm that, given an Hfree graph G and an accuracy parameter ε > 0, finds an independent set in G of cardinality within a factor of (1 – ε) of the optimum in time exponential in a polynomial of log  V(G)  and ε−1. That is, we show that for every graph H for which Maximum Independent Set is not known to be APXhard in Hfree graphs, the problem admits a quasipolynomial time approximation scheme in this graph class. Our algorithm works also in the more general weighted setting, where the input graph is supplied with a weight function on vertices and we are maximizing the total weight of an independent set.
more »
« less
The Replenishment Schedule to Minimize Peak Storage Problem: The Gap Between the Continuous and Discrete Versions of the Problem
The replenishment storage problem (RSP) is to minimize the storage capacity requirement for a deterministic demand, multiitem inventory system, where each item has a given reorder size and cycle length. We consider the discrete RSP, where reorders can only take place at an integer time unit within the cycle. Discrete RSP was shown to be NPhard for constant joint cycle length (the least common multiple of the length of all individual cycles). We show here that discrete RSP is weakly NPhard for constant joint cycle length and prove that it is strongly NPhard for nonconstant joint cycle length. For constant joint cyclelength discrete RSP, we further present a pseudopolynomial time algorithm that solves the problem optimally and the first known fully polynomial time approximation scheme (FPTAS) for the singlecycle RSP. The scheme is utilizing a new integer programming formulation of the problem that is introduced here. For the strongly NPhard RSP with nonconstant joint cycle length, we provide a polynomial time approximation scheme (PTAS), which for any fixed [Formula: see text], provides a linear time [Formula: see text] approximate solution. The continuous RSP, where reorders can take place at any time within a cycle, seems (with our results) to be easier than the respective discrete problem. We narrow the previously known complexity gap between the continuous and discrete versions of RSP for the multicycle RSP (with either constant or nonconstant cycle length) and the singlecycle RSP with constant cycle length and widen the gap for singlecycle RSP with nonconstant cycle length. For the multicycle case and constant joint cycle length, the complexity status of continuous RSP is open, whereas it is proved here that the discrete RSP is weakly NPhard. Under our conjecture that the continuous RSP is easier than the discrete one, this implies that continuous RSP on multicycle and constant joint cycle length (currently of unknown complexity status) is at most weakly NPhard.
more »
« less
 Award ID(s):
 1760102
 NSFPAR ID:
 10357236
 Date Published:
 Journal Name:
 Operations Research
 Volume:
 67
 Issue:
 5
 ISSN:
 0030364X
 Page Range / eLocation ID:
 1345 to 1361
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Given a set of points P and axisaligned rectangles R in the plane, a point p ∈ P is called exposed if it lies outside all rectangles in R. In the maxexposure problem, given an integer parameter k, we want to delete k rectangles from R so as to maximize the number of exposed points. We show that the problem is NPhard and assuming plausible complexity conjectures is also hard to approximate even when rectangles in R are translates of two fixed rectangles. However, if R only consists of translates of a single rectangle, we present a polynomialtime approximation scheme. For general rectangle range space, we present a simple O(k) bicriteria approximation algorithm; that is by deleting O(k2) rectangles, we can expose at least Ω(1/k) of the optimal number of points.more » « less

The emergence of the InternetofThings (IoT) has inspired numerous new applications. However, due to the limited resources in current IoT infrastructures and the stringent qualityofservice requirements of the applications, providing computing and communication supports for the applications is becoming increasingly difficult. In this paper, we consider IoT applications that receive continuous data streams from multiple sources in the network, and study joint application placement and data routing to support all data streams with both bandwidth and delay guarantees. We formulate the application provisioning problem both for a single application and for multiple applications, with both cases proved to be NPhard. For the case with a single application, we propose a fully polynomialtime approximation scheme. For the multiapplication scenario, if the applications can be parallelized among multiple distributed instances, we propose a fully polynomialtime approximation scheme; for general nonparallelizable applications, we propose a randomized algorithm and analyze its performance. Simulations show that the proposed algorithms greatly improve the qualityofservice of the IoT applications compared to the heuristics.more » « less

Establishing the complexity of {\em Bounded Distance Decoding} for ReedSolomon codes is a fundamental open problem in coding theory, explicitly asked by Guruswami and Vardy (IEEE Trans. Inf. Theory, 2005). The problem is motivated by the large current gap between the regime when it is NPhard, and the regime when it is efficiently solvable (i.e., the Johnson radius). We show the first NPhardness results for asymptotically smaller decoding radii than the maximum likelihood decoding radius of Guruswami and Vardy. Specifically, for ReedSolomon codes of length $N$ and dimension $K=O(N)$, we show that it is NPhard to decode more than $ NK c\frac{\log N}{\log\log N}$ errors (with $c>0$ an absolute constant). Moreover, we show that the problem is NPhard under quasipolynomialtime reductions for an error amount $> NK c\log{N}$ (with $c>0$ an absolute constant). An alternative natural reformulation of the Bounded Distance Decoding problem for ReedSolomon codes is as a {\em Polynomial Reconstruction} problem. In this view, our results show that it is NPhard to decide whether there exists a degree $K$ polynomial passing through $K+ c\frac{\log N}{\log\log N}$ points from a given set of points $(a_1, b_1), (a_2, b_2)\ldots, (a_N, b_N)$. Furthermore, it is NPhard under quasipolynomialtime reductions to decide whether there is a degree $K$ polynomial passing through $K+c\log{N}$ many points. These results follow from the NPhardness of a generalization of the classical Subset Sum problem to higher moments, called {\em Moments Subset Sum}, which has been a known open problem, and which may be of independent interest. We further reveal a strong connection with the wellstudied ProuhetTarryEscott problem in Number Theory, which turns out to capture a main barrier in extending our techniques. We believe the ProuhetTarryEscott problem deserves further study in the theoretical computer science community.more » « less

We study the Doptimal Data Fusion (DDF) problem, which aims to select new data points, given an existing Fisher information matrix, so as to maximize the logarithm of the determinant of the overall Fisher information matrix. We show that the DDF problem is NPhard and has no constantfactor polynomialtime approximation algorithm unless P = NP. Therefore, to solve the DDF problem effectively, we propose two convex integerprogramming formulations and investigate their corresponding complementary and Lagrangiandual problems. Leveraging the concavity of the objective functions in the two proposed convex integerprogramming formulations, we design an exact algorithm, aimed at solving the DDF problem to optimality. We further derive a family of submodular valid inequalities and optimality cuts, which can significantly enhance the algorithm performance. We also develop scalable randomizedsampling and localsearch algorithms with provable performance guarantees. Finally, we test our algorithms using realworld data on the new phasormeasurementunits placement problem for modern power grids, considering the existing conventional sensors. Our numerical study demonstrates the efficiency of our exact algorithm and the scalability and highquality outputs of our approximation algorithms. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: Y. Li and W. Xie were supported in part by Division of Civil, Mechanical and Manufacturing Innovation [Grant 2046414] and Division of Computing and Communication Foundations [Grant 2246417]. J. Lee was supported in part by Air Force Office of Scientific Research [Grants FA95501910175 and FA95502210172]. M. Fampa was supported in part by Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grants 305444/20190 and 434683/20183]. Supplemental Material: The ecompanion is available at https://doi.org/10.1287/ijoc.2022.0235 .more » « less