CS Paper Radar

An EPTAS for Max-Cut on Interval Graphs

Hani Ahmadzadeh, Morteza Alimi

cs.DS ·submitted 2026-11-11 22:34 UTC · v1
theory

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}$.

Closest papers

Nearest neighbours by meaning across the whole index.

Exact Tie-Breaking and Tight Degree Bounds for Minimum-Degree Greedy on Interval Graphs

cs.DS ·2026-11-01 ·Ruize Zhao
similarity 0.71
Abstract · 23 pages, 3 figures

We study tie-breaking in the minimum-degree greedy algorithm (MDG) for maximum independent set on interval graphs. Given an interval representation of an $n$-vertex graph, we compute the largest and smallest output sizes and construct executions attaining them in $O(n^3)$ time and $O(n^2)$ space. For maximum degree at most four, favorable tie-breaking gives a tight guarantee of $3/4$. For every maximum-degree bound of at least five, the guarantee drops to $2/3$. Both bounds are tight even on connected unit interval graphs whose output size is independent of tie-breaking. Together with the known optimality of favorable tie-breaking for maximum degree at most three, these results give a complete classification by degree bound.

0.17

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.71
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

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

cs.DS ·2026-11-03 ·Morteza Alimi, Tobias Mömke, Alexandru Popa, Michael Ruderer
theory similarity 0.71
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.

0.29

Single-Exponential FPT Algorithms for Minimum Bisection and Matching Cut via a New Unbreakable Decomposition

cs.DS ·2026-11-04 ·Soh Kumabe
similarity 0.69
Abstract

Minimum Bisection asks whether the vertices of a graph can be partitioned into two parts whose sizes differ by at most one and with at most k edges between the two parts. Cygan, Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saurabh (SICOMP 2019) gave the first fixed-parameter algorithm, which runs in O*(2^(O(k^3))) time, by introducing an unbreakable decomposition. Cygan, Komosa, Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saurabh, and Wahlström (TALG 2021) strengthened the decomposition and improved the running time to O*(2^(O(k log k))). However, whether the running time could be improved to single-exponential remained open. In this paper, we give a deterministic O*(2^(O(k)))-time algorithm for Minimum Bisection. Our algorithm also counts all feasible bisections. To obtain an O*(2^(O(k)))-time algorithm, we introduce two new techniques. First, we give a new algorithm that computes a (2k,k)-edge-unbreakable decomposition with adhesion at most 2k in O*(2^(O(k))) time by relaxing the unbreakability and adhesion guarantees of the decomposition in (TALG 2021). Second, we improve the running time of the dynamic program over the decomposition from O*(2^(O(k log k))) to O*(2^(O(k))) using important cuts, inclusion-exclusion, and formal logarithms and exponentials. Together with color coding, the same techniques give a deterministic O*(2^(O(k)))-time algorithm for Matching Cut, which asks for a cut whose crossing edges form a matching. This improves the O*(2^(O(k log k)))-time algorithm of Aravind and Saxena (IWOCA 2021).

0.46

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.68
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

Improved Approximation and Hardness Results for the Monitoring Edge-Geodetic Set Problem

cs.DS ·2026-10-20 ·Davide Bilò, Giordano Colli, Stefano Leucci
theory similarity 0.67
Abstract · 18 pages, 4 figures

We study the \emph{Monitoring Edge-Geodetic Set} problem (MEG-Set), which asks for a minimum-cardinality set $M$ of vertices of an undirected graph $G$ of $n$ vertices such that every edge of $G$ belongs to all shortest paths between some pair of vertices in $M$. We present new approximation and hardness results for MEG-Set. On the positive side, we design a deterministic polynomial-time $O(n^{1/3}\log^{2/3}n)$-approximation algorithm, improving upon the previously best-known $O(\sqrt{n\log n})$ approximation ratio. On the negative side, for every constant $\varepsilon \in (0,1)$, we prove that the problem admits no polynomial-time $\big(2^{\log^{1-\varepsilon} n}\big)$-approximation algorithm, unless $\mathsf{NP}\subseteq \mathsf{DTIME}(n^{\operatorname{polylog} n})$. This substantially improves upon the previously known logarithmic inapproximability bound. We also prove that \megset is $\mathsf{NP}$-hard on planar $2$-degenerate graphs, whereas $\mathsf{NP}$-hardness was previously known for $1$-apex $2$-degenerate graphs. We conclude by observing a connection between monitoring edge-geodetic sets and subsetwise distance preservers, i.e., subgraphs that preserve distances between all pairs of vertices in $S\subseteq V(G)$. Specifically, we show that any upper bound on the size of the latter yields a lower bound on the size of the former.

0.23

A Linear-Time Approximation Scheme for the Densest Subgraph Problem

cs.DS ·2026-08-11 ·Elena Grigorescu, Mehrshad Taziki
similarity 0.66
Abstract

In the undirected \emph{Densest Subgraph Problem (DSG)} the goal is to output a subset $S$ of vertices of a given graph $G$ that maximizes the quantity $|E(S)|/|S|$, where $E(S)$ is the set of edges in the subgraph induced by $S$. The problem is well studied in both theory and practice, and it admits natural efficient exact algorithms, as well as near-linear time algorithms with a $(1-\varepsilon)$ approximation ratio. However, all previously-known approximation schemes incur logarithmic factors in the size of the graph or other parameters of the graph. This raises the question of whether a linear time $(1-\varepsilon)$-approximation can be obtained for all $\varepsilon>0$. We answer this question affirmatively by providing a $(1-\varepsilon)$-approximation algorithm running in time $O\left(\frac{n+m}{\varepsilon^3}\log \frac{1}{\varepsilon}\right)$, where $m$ and $n$ are respectively the number of edges and vertices of $G$. To the best of our knowledge, this is the first truly linear-time approximation scheme for the problem (when $\varepsilon>0$ is a constant). Our algorithm uses assignments arising from a flow-based formulation together with a structural carving lemma. This lemma allows us to progressively carve "sparse" parts of the graph while nearly preserving the densest subgraph, allowing us to shift heavy computations to smaller instances, which eventually yields the mentioned runtime. Our framework also yields a $(1/2 -\varepsilon)$-approximation for the \emph{Densest At-Least-$k$ Subgraph Problem}, where in addition to maximizing the density, we require the subgraph to have at least $k$ vertices. Our algorithm runs in time $O\left( \frac{(n+m) \log^2 n \log \frac{1}{\varepsilon}}{\varepsilon} \right)$. This nearly matches the known $1/2$ approximation hardness while running in near-linear time.

0.04

Polynomial Kernels for Interval Completion

cs.DS cs.CC ·2026-10-07 ·Zimo Sheng, Tian Bai, Mingyu xiao
similarity 0.66
Abstract

An interval graph is the intersection graph of a family of intervals on the real line. \textsc{Interval Completion} asks whether a given graph can be transformed into an interval graph by adding at most $k$ edges. Although the problem is fixed-parameter tractable when parameterized by $k$, whether it admits a polynomial kernel has long been an open question. We resolve this question by giving the first polynomial kernel for \textsc{Interval Completion}. Our main contribution is a parameter-preserving polynomial-time reduction from \textsc{Interval Completion} to \textsc{Odd Cycle Transversal} (OCT). Combining this reduction with the known randomized and deterministic polynomial kernels for OCT and a polynomial-time reduction back to \textsc{Interval Completion}, we obtain a randomized kernel with $\widetilde O(k^{18})$ vertices and $\widetilde O(k^{36})$ edges, and a deterministic kernel with $O(k^{36})$ vertices and $O(k^{72})$ edges. Here, $\widetilde O$ suppresses polylogarithmic factors in $k$.

0.10