CS Paper Radar

NP-Hardness and a PTAS for Maximum Interval Multicover, with Applications to Dense Subgraphs

Morteza Alimi, Tobias Mömke, Alexandru Popa, Michael Ruderer

cs.DS ·submitted 2026-11-03 13:37 UTC · v1
theory

Abstract

Given intervals and points on a line, each point with a demand, and a budget $K$, Maximum Interval Multicover asks for at most $K$ intervals that satisfy as many points as possible, a point being satisfied if it lies in at least as many chosen intervals as its demand. One application is committee elections in which each candidate is approved by consecutive voters and voters have individual demands. Xu, Ran and Zhang introduced the problem and gave a $1/2$-approximation; the objective is not submodular when demands exceed one. Li, Tu, Zhang and Cao gave a polynomial-time approximation scheme (PTAS) for the minimization counterpart, unweighted partial interval multicover, and asked for its complexity. We prove that both problems are NP-hard, even for intervals of equal length; as their optima are integers bounded by the input size, neither has a fully polynomial-time approximation scheme unless $\mathrm{P}=\mathrm{NP}$. We then give a PTAS for Maximum Interval Multicover, also for arbitrary nonnegative nondecreasing rewards for the coverage of each point. Building on a decomposition from Nonner's PTAS for Densest $k$-Subgraph on interval graphs, our scheme cuts the line into pieces at a small loss and solves every piece exactly. The key dynamic program handles intervals crossing a common point by choosing an interleaving of their left and right endpoints rather than sweeping along the line; it needs only two counters to track these intervals. The same algorithm yields PTASes on convex bipartite graphs for Bipartite Dense Subgraph, improving on the ratio $2/3$ of Backer and Keil for the subclass of bipartite permutation graphs, and on interval graphs for Maximum $k$-Vertex Cover and weighted clique counts.

Closest papers

Nearest neighbours by meaning across the whole index.

An EPTAS for Max-Cut on Interval Graphs

cs.DS ·2026-11-11 ·Hani Ahmadzadeh, Morteza Alimi
theory similarity 0.71
Abstract

Max-Cut was shown NP-hard on interval graphs by Adhikary, Bose, Mukherjee, and Roy (SoCG 2021). The best previously known approximation ratio for this class, due to Ahn, DeHaan, Kim, and Lee (APPROX 2025), exceeded the Goemans--Williamson ratio of about $0.878$ by only $10^{-34}$. We give a deterministic efficient polynomial-time approximation scheme (EPTAS): for every $\varepsilon\in(0,1)$, a $(1-\varepsilon)$-approximate cut of an unweighted $n$-vertex interval graph can be found in time $2^{O(\varepsilon^{-2}\log^3(2/\varepsilon))}n^2$. The same guarantee and running time hold for Max-Bisection. An FPTAS is impossible unless $\mathrm{P}=\mathrm{NP}$. Our algorithm rests on a structural theorem: every interval graph with $m$ edges can be turned into an interval graph of clique-width $O(\varepsilon^{-2}\log^2(2/\varepsilon))$ by deleting at most $\varepsilon m$ edges. The construction combines endpoint-rank coordinates, length-dependent rounding, and a shifted dyadic hierarchy. Intervals intersecting cell boundaries at their own scales are isolated at small total edge cost; the interactions of remaining long intervals with smaller subproblems can be summarized by counts. The structural theorem also yields a randomized EPTAS via Lampis's scheme for bounded clique-width; our direct dynamic program is deterministic and handles Max-Bisection. Finally, for every $\varepsilon>0$, it is NP-hard to approximate Max-Cut within $84/85+\varepsilon$ on unweighted chordal graphs, which contain interval graphs. Thus an approximation scheme for Max-Cut on chordal graphs would imply $\mathrm{P}=\mathrm{NP}$.

0.41

A PTAS for Constraint Satisfaction Problems on Interval Graphs and Bounded Rank-Width Graphs

cs.DS ·2026-11-12 ·Ian DeHaan, Euiwoong Lee
similarity 0.70
Abstract · 18 pages

We present a polynomial-time approximation scheme (PTAS) for all Boolean arity-two maximum constraint satisfaction problems (Boolean Max-2-CSP) where the constraint graph is either interval or has bounded rank-width. This class of problems includes, for example, Max-Cut, Max-DiCut, Max-2-Lin(2), and Max-2-SAT. In particular, this settles the approximability of Max-Cut on interval graphs. To achieve these results, we show the following. 1. For any $\varepsilon > 0$, there is an $n^{\mathcal O(r \varepsilon^{-2})}$-time $(1 - \varepsilon$)-approximation for Boolean Max-2-CSP on graphs of rank-width at most $r$. 2. There is a polynomial-time algorithm that, for any interval graph $G = (V, E)$ and $\varepsilon > 0$, finds a subgraph $H = (V, F)$ of $G$ such that $|F| \geq (1 - \varepsilon) |E|$ and $H$ has rank-width at most $\operatorname{poly}(\varepsilon^{-1})$. Our techniques additionally extend to all bounded-alphabet arity-two max CSPs.

0.28

On the maximum weight convex problem for some geometric graph-convexities

cs.DS ·2026-08-31 ·Fariza Aklouche, Pierre Bergé, Michel Habib
survey similarity 0.66
Abstract · Full version of the extended abstract presented at conference COSI 2025, Bejaia, Algeria

For a given geometric graph-convexity on a graph $G$ equipped with a weight function on the vertices with value in $\mathbb{Z}$, the Max Weight Convex Set problem consists in determining the convex set $S$ with maximum weight (sum of the weight of the vertices in $S$). Although the problem is NP-complete in general, it remains polynomial for particular cases. After a survey of known results, our main contribution uses a generalisation of the maximum subsequence problem to laminar trees. Then we derive a linear algorithm for proper interval graphs and a quadratic one for interval graphs. Both improve the state of the art.

0.38

Partial Interval Multicover Is NP-Complete Even for Unit Intervals

cs.DM ·2026-10-30 ·Mingchao Zhou, Yingli Ran, Lei Zhao, Xiangzhi Tu, Zhao Zhang
theory similarity 0.66
Abstract

For a interval family $\calI$, a point set $X\subseteq\mathbb R$, demands $d:X\to\Z_{\ge0}$, and $p\in\Z_{\ge0}$, partial interval multicover asks for a subfamily $S\subseteq\calI$ minimizing $|S|$ subject to $$ |\{x\in X:\dep_S(x)\ge d(x)\}|\ge p, \qquad \dep_S(x)=|\{I\in S:x\in I\}|. $$ We prove that the unweighted decision problem is NP-complete even for unit intervals, answering the open question in~\cite{Li2026}.

0.26

Scheduling with Mandatory Breaks: NP-Hardness and an Additive-One Approximation

cs.DS ·2026-09-28 ·Shreyas Ghildiyal, Muralidhara V N
similarity 0.64
Abstract

In classical fixed-interval scheduling, each job of a given set must be processed during a prescribed time interval. The goal is to assign each job to exactly one machine such that no two jobs assigned to the same machine overlap in their interiors, and the number of machines used is minimized. Without further constraints this is interval graph coloring and is solvable in polynomial time through greedy approaches. We study a variant in which every used machine must remain idle during a contiguous \emph{break} of prescribed length $x$ somewhere in the scheduling horizon. We show that this additional constraint makes the problem hard, except when $x\le1$. First, for every fixed $x\ge2$, deciding whether $k$ machines suffice for the assignment of a given set of jobs is NP-complete, even when all coordinates are bounded linearly in the number of jobs, so machine minimization is strongly NP-hard. Second, for $x=1$, we give a polynomial-time algorithm that solves the problem exactly. Finally, we give a deterministic polynomial-time algorithm that, on every feasible instance, outputs a schedule using at most $\OPT+1$ machines, where $\OPT$ is the true minimum. Unless $\mathrm{P}=\mathrm{NP}$, no polynomial-time algorithm guarantees $\OPT$ machines for any fixed $x\ge2$, so the additive guarantee of one is best possible.

0.07

A Better-Than-$3$ Approximation Algorithm for Demand Matching via Knapsack Intersection LP and Contention Resolution

cs.DS cs.DMmath.CO ·2026-09-15 ·Michel X. Goemans, Yuchong Pan
theory similarity 0.63
Abstract

The demand matching problem generalizes both the knapsack problem and the $b$-matching problem. In this problem, each edge of a graph has a demand and a weight, and each vertex has a capacity. The goal is to find a maximum weight subset of edges such that, at each vertex, the total demand of the incident selected edges does not exceed the vertex capacity. Parekh [IPCO 2011] proved that, if each edge is individually feasible, the natural LP relaxation for demand matching has integrality gap at most $3$, yielding a $3$-approximation algorithm. This bound is tight for the natural LP relaxation, matching the lower bound of Shepherd and Vetta [Math. Oper. Res. 2007]. We present a randomized $(3/2 + \sqrt{2} + \varepsilon) \approx (2.914 + \varepsilon)$-approximation algorithm for the demand matching problem for every $\varepsilon > 0$, giving the first approximation ratio strictly better than $3$. For bipartite graphs, we obtain a randomized $(2 + \varepsilon)$-approximation algorithm for every $\varepsilon > 0$. Both algorithms run in time polynomial in $1/\varepsilon$ and the input length. Our algorithms use a strengthened LP relaxation based on intersecting the integral knapsack polytopes associated with the vertices, together with a multiple-choice generalization. As a key ingredient, we prove the existence of a $(q, 1/(1+q))$-balanced contention resolution scheme for the integral knapsack polytope for every $q \in [0, 1]$, which may be of independent interest. The balance guarantee $1/(1+q)$ is tight in the worst case over all knapsack instances.

0.23

A Reusable Framework for Robust Approximation Algorithms in the Interval Uncertainty Model

cs.DS ·2026-09-10 ·Ralf Klasing, Tobias Mömke, Émile Naquin
theory similarity 0.62
Abstract

Robust optimization under interval uncertainty aims to compute solutions that perform well on a range of scenarios that are described by interval-constrained costs. In this paper, we revisit a framework introduced by Ganesh, Maggs and Panigrahi in 2020 to study the robust optimization of NP-hard problems under interval uncertainty. We start by generalizing a result in the $\ell=0$ case, which transforms a category of approximation algorithms into a robust approximation algorithm. Furthermore, in the general case, we provide a theorem that turns any local search-based approximation algorithm into a robust approximation algorithm under three newly formalized conditions over the moves of the local search algorithm. We then use this result to present the first robust approximation algorithm for Weighted $k$-Set Cover, the third NP-hard problem known to admit a robust approximation, and the first since the publication of Ganesh, Maggs and Panigrahi's paper.

0.12

Multiobjective Hypergraph Min-Cut in Quasi-Polynomial Time

cs.DS ·2026-09-03 ·Karthekeyan Chandrasekaran, Chandra Chekuri, Weihao Zhu
similarity 0.62
Abstract

We study the multiobjective hypergraph min-cut problem: Given a hypergraph $H=(V,E)$ and $k$ cost functions $c_1, c_2, \ldots, c_k:E\to\mathbb{Z}_{\ge 0}$, the goal is to find a non-empty proper subset $U\subsetneq V$ of vertices with minimum $\max_{i\in [k]} c_i(δ(U))$. When $k$ is part of input, the problem is NP-hard (even in graphs). We focus on fixed-constant $k$ setting (e.g., $k=1, 2, 3, \ldots$). Single-objective hypergraph min-cut as well as multiobjective graph min-cut for a constant number of objectives admit polynomial-time algorithms. In contrast to these special cases, the complexity of multiobjective hypergraph min-cut remains open even for $k=2$. Known techniques fail to extend due to structural differences between graphs and hypergraphs. For $k$-objective hypergraph min-cut when $k$ is a fixed constant, we design a randomized PTAS, and two different randomized quasi-polynomial time algorithms. As an application of our $2$-objective hypergraph min-cut results, we obtain a quasi-polynomial time approximation scheme (QPTAS) for hypergraph connectivity interdiction. AI tools were used to iterate and refine the algorithmic ideas underlying this work.

0.25