On the maximum weight convex problem for some geometric graph-convexities
2026-08-31 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study a problem where you want to find a group of connected nodes in a weighted graph that has the largest total weight, under certain rules called geometric graph-convexity. While this problem is usually very hard to solve, they focus on special types of graphs called interval and proper interval graphs. By linking the problem to a known sequence problem on tree structures, the authors create faster algorithms than before. Their methods run in linear time for proper interval graphs and quadratic time for interval graphs.
Geometric graph-convexityMax Weight Convex Set problemWeighted graphNP-completeInterval graphProper interval graphLaminar treesMaximum subsequence problemPolynomial algorithm
Authors
Fariza Aklouche, Pierre Bergé, Michel Habib
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.