CS Paper Radar

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

Fariza Aklouche, Pierre Bergé, Michel Habib

cs.DS ·submitted 2026-08-31 13:01 UTC · v1
survey

Abstract

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.

Comment
Full version of the extended abstract presented at conference COSI 2025, Bejaia, Algeria

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

An EPTAS for Max-Cut on Interval Graphs

cs.DS ·2026-11-11 ·Hani Ahmadzadeh, Morteza Alimi
theory similarity 0.68
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

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

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

Sub-polynomial parameterized complexity of $k$-core

cs.CC ·2026-09-21 ·Yan S. Couto, Cristina G. Fernandes
theory similarity 0.63
Abstract

The $k$-core of a graph is its (unique) largest subgraph with minimum degree at least $k$. For any $k \geq 3$, deciding whether a given vertex belongs to the $k$-core is a P-complete problem, meaning that it is inherently sequential and highly unlikely to admit efficient parallel algorithms, even on graphs of maximum degree $k+1$. This paper investigates alternative parameterizations of the $k$-core problem to identify conditions under which it can be placed into sub-polynomial complexity classes. We prove that the problem is in para-NC$^{2+ε}$ when parameterized by treewidth, and in para-NC$^3$ when parameterized by $k$ on chordal graphs. Furthermore, we introduce a novel NC$^{3}$ algorithm for interval graphs when $k = \mathcal{O}(\lg v(G))$, which relies on an improved parameterization by pathwidth. Finally, we establish corresponding lower bounds, demonstrating that, even with these parameterizations, computing the $k$-core remains L-hard, meaning it requires at least logarithmic space. These findings explore the boundary of parallel tractability for the $k$-core problem by highlighting the graph parameters that make it inherently sequential.

0.23

Approximation Algorithms for Maximum-Weight Degree-Bounded Forests

cs.DS math.CO ·2026-11-01 ·Theophile Thiery, Vera Traub, Nicola Widmer
publishedtheory similarity 0.62
Abstract · to appear in SOSA 2027

In the maximum-weight degree-bounded forest problem, we are given a graph with nonnegative edge weights and a degree upper bound on each vertex. The objective is to find a maximum-weight forest satisfying the degree bounds. We show that this problem admits a simple $2$-approximation via the greedy algorithm. This already improves over the best-known guarantees obtained via a reduction to weighted $3$-matroid parity, and sets a baseline to improve upon. Our main result is an $\frac{8}{5}$-approximation algorithm for the maximum-weight degree-bounded forest problem. For the special case of uniform degree bounds, our algorithm achieves an approximation ratio of $\frac{3}{2}$. It computes two sets of edges, each of which we then restrict to a feasible solution in an optimal way, and finally returns the better of the two resulting solutions. To obtain the initial two edge sets, we first relax the degree bounds and leverage an algorithm by Lau and Singh [JACM'15] for degree-bounded spanning trees, and second we relax the forest constraints and employ an algorithm for maximum-weight $b$-matchings.

0.39

Solving problems in RDV Graphs faster and easier

cs.DS ·2026-10-20 ·Therese Biedl, Günter Rote
similarity 0.61
Abstract · 20 pages, 2 appendices, 4 figures

In interval graphs and many generalizations thereof, problems such as Matching, Independent Set, and Dominating Set can be solved with simple greedy algorithms in linear (i.e., $O(m+n)$) time. However, it is sometimes possible to improve on this runtime if a suitable representation as intersection graph is given; for example it is possible to find a minimum dominating set in an interval graph in $O(n)$ time. We study RDV graphs, a generalization of interval graphs, namely, the intersection graphs of directed paths in a rooted tree. It was known that the above three problems can be solved in $O(n\log n)$ time if a suitably small representation is given. In this paper, we reduce the runtime to $O(n)$. Furthermore, while the previous results used non-trivial operations such as range-minimum queries and ray-shooting queries, we need nothing more complicated than lists and (for Matching) a Union-Find data structure.

0.22

Sharp lower bounds for weighted bisections of graphs with bounded maximum degree

cs.DM math.CO ·2026-11-17 ·Stefanie Gerke, Gregory Gutin, Anders Yeo, Yacong Zhou
theory similarity 0.60
Abstract

A bisection of a graph is a partition of its vertex set into two parts the sizes of which differ by at most one. We prove that every finite simple graph of maximum degree at most an odd positive integer $k$, with arbitrary nonnegative real edge weights, has a bisection of weight at least $(k+1)/(2k)$ times its total edge weight. The corresponding bound $(k+2)/(2(k+1))$ for even $k$ follows immediately. Both coefficients are best possible. Somewhat surprisingly, these are exactly the sharp coefficients known for maximum weighted cuts, despite the additional balance requirement.

0.19