Source-linked AI summary
On the maximum weight convex problem for some geometric graph-convexities
Fariza Aklouche, Pierre Bergé, Michel Habib
TL;DR
The paper studies maximum-weight convex sets in discrete convex geometry, where the goal is to select a convex vertex set with maximum total weight. It generalizes maximum subsequence methods to laminar trees and establishes linear-time and quadratic-time algorithms for proper interval and interval graphs, respectively.
Problem
The paper studies selecting a convex set with maximum total vertex weight in discrete convex geometry, a problem with applications to polytopes and combinatorial algorithms.
Method
The paper generalizes maximum-weight contiguous-subset techniques to circular nodes and uses inductive dynamic programming over subtrees of PQ-trees.
Results
Linear time solves the maximum convex set problem for proper interval graphs, while O(n^2) time solves it for interval graphs.
Takeaways & Limitations
The results identify efficient algorithms for maximum convex sets on proper interval graphs and interval graphs.
Takeaways & Limitations
The work focuses on PQ-trees rather than developing the suggested adaptations to other typed-laminar tree node types, and leaves several graph-class questions open.
Abstract
from arXiv · showhide
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.
1 Introduction to convexity spaces and geometric convexities
The paper introduces convexity spaces and graph-convexities, then formulates the maximum-weight convex set problem and explains why general instances are difficult.
- A convexity space consists of a ground set and designated convex subsets satisfying closure axioms such as arbitrary intersection and nested-union closure.
- Convex geometries are convexity spaces satisfying the Minkowsky-Krein-Milman property, equivalently the Anti-Exchange Property, and correspond through complements to antimatroids.
- Graph-convexity spaces additionally require every convex set to induce a connected subgraph.
- Examples include geodesic convexity, m3-convexity on HDD-free graphs, and 2-paths-convexity on cocomparability graphs.
- The max weight convex set problem seeks a convex set S maximizing the sum of integer vertex weights, but is NP-hard in general.
- Its difficulty reflects closure forcing the inclusion of negatively weighted vertices and the possible exponential number of convex sets.
2 Maximum-weighted convex sets on graphs
The paper surveys algorithms for maximum-weight convex sets across graph classes and related structures, emphasizing polynomial cases and unresolved complexity boundaries.
- The literature includes efficient algorithms for split, threshold, proper interval, interval, chordal, and tree-related settings.
- For trees with geodesic convexity, dynamic programming achieves O(n log n), improving an earlier O(n^2) algorithm.
- For posets, interval convex sets admit a quadratic-time solution, while ideal optimization reduces to maximum flow.
- In Euclidean convex geometry, the problem is polynomial for d ≤2 and NP-hard for d ≥3.
- Maximum-weight connected subgraph is related but distinct because intersections of connected subgraphs need not be connected.
- The survey identifies trees as an important challenge and summarizes complexity results for graph classes using their natural convex geometries.
3 Maximum sequences of leaves in a laminar tree
The paper generalizes maximum sum subsequence from arrays to typed-laminar trees, where convex leaf sets are contiguous in a valid representation. It develops dynamic programs for circular and PQ-tree structures, obtaining linear height-1 and quadratic PQ-tree algorithms.
- Typed-laminar trees: Typed-laminar trees compactly represent permissible leaf permutations through P, Q, R, and C node types.P-nodes allow arbitrary child order, Q-nodes allow an order or its reverse, R-nodes have one order, and C-nodes allow cyclic orders.
- Problem definition: A laminar convex set is a leaf set contiguous in some valid representation of the typed-laminar tree.The maximum-weight laminar convex set problem assigns integer weights to leaves and seeks the heaviest such set.
- Height-1 trees: A linear-time algorithm solves max weight laminar convex set on typed-laminar trees of height 1.The P-node case selects all positive-weight elements, while R- and Q-node cases reduce to maximum sum subsequence; the C-node case doubles the sequence and maintains bounded contiguous-subset states.
- Height-1 trees: The circular-node dynamic program runs linearly in the doubled array size and returns a maximum-weight subsequence of size at most n before circular adjustment.It maintains Ssofar(A+) and Sright(A+) while scanning the 2n-element array.
- PQ-trees: A PQ-tree dynamic program computes maximum-weight PQ-convex sets by recursively updating four subtree variables.For a node with k children, combining the variables takes O(k^2), and the full recursion takes O(n^2).
- PQ-trees: The PQ-tree computation considers alternative child orders and cases for prefixes, suffixes, and sets spanning multiple subtrees.The algorithm compares the resulting values, and the quadratic process applies to PQ-trees with n vertices.
- Scope: The discussion focuses on PQ-trees, although the authors state that the dynamic programming scheme can be adapted to C- and R-nodes.This leaves those extensions outside the paper’s detailed treatment.
4 Interval graphs
For interval graphs, convex sets correspond to intervals in suitable representations, enabling maximum-weight convex set algorithms via subsequence methods and PQ- or laminar-tree encodings. The paper obtains linear time for proper interval graphs and quadratic time for interval graphs.
- Interval representations: Interval graphs model intersections of intervals on the real line, and their natural graph-convexity is monophonic convexity because interval graphs are chordal.With a given interval representation, a sweep-line scan reduces the problem to maximum sum subsequence.
- Convexity properties: The interception convexity is a convex geometry exactly when its interval operator has the Strong Chvátal Property and the graph has an interception-convexity order.These three conditions are equivalent for every graph.
- Convex-set structure: Every convex set of an interval graph can be associated with an interval in some interval representation.This structural result underlies the reduction from graph convexity to contiguous subsequences.
- Convexity properties: The monophonic convexity has Carathéodory number 2 on interval graphs.The result follows from the proposition associating each convex set with an interval in an interval representation.
- Algorithms: The maximum convex set problem can be solved in linear time for proper interval graphs.Proper interval graphs admit a height-2 typed-laminar-tree representation, so the maximum is computed linearly in that tree.
- Algorithms: A typed-laminar tree encodes all interval representations, allowing the maximum convex set problem to be solved in O(n^2) for interval graphs.The construction combines a PQ-tree with a modular decomposition tree, then applies the interval-convexity structure and the laminar-tree algorithm.
5 Split and threshold graphs
For split graphs under monophonic convexity, positive-weight independent vertices and twin reduction simplify the optimization. Threshold graphs exploit nested neighborhoods to achieve a linear-time algorithm.
- Split graphs: A split graph partitions its vertices into a clique K and an independent set I, with convex sets closed under monophonic convexity.The bipartite edges between K and I may be arbitrary.
- Reductions: Only positive-weight vertices of I need be retained, and positive independent twins can be replaced by one vertex with their summed weight.Independent vertices are extreme for monophonic convexity, supporting the first reduction.
- Reductions: Every subset of K is convex, so the positive-weight vertices of K provide an upper bound on the maximum weighted convex set.This bound follows directly from the clique side of the split partition.
- Threshold graphs: Threshold graphs are split graphs whose independent-vertex neighborhoods are totally ordered by inclusion.This nested-neighborhood structure is the basis for the linear-time algorithm.
- Threshold graphs: Algorithm 3 computes the maximum weight of a convex set in a threshold graph in O(n).The algorithm scans the ordered independent vertices and evaluates candidate convex-set weights while maintaining cumulative quantities.
6 Perspectives
The paper identifies several directions beyond its current polynomial cases, including improved algorithms, the complexity boundary for cocomparability and AT-free graphs, and structural conditions involving modules.
- Algorithmic directions: Future work includes improving algorithms for known polynomial cases such as split, chordal, and Ptolemaic graphs.The paper also asks whether PCR-tree ideas can be generalized to maximum-weight convex sets.
- Open complexity questions: The complexity boundary remains open for cocomparability graphs and AT-free graphs under their respective convexities.The paper suggests polynomiality may hold for cocomparability graphs but is less clear for AT-free graphs.
- Structural directions: A further direction is characterizing interval graph-convexities that interact well with modules as in Lemma 2.This seeks structural conditions supporting module-based reductions.
- Geometric convexities: Bounded Carathéodory number alone does not guarantee polynomiality: maximum-weight convex set is NP-hard for geometric convexity in R^3.The paper therefore asks which additional properties of geometric convexities ensure polynomiality.