Rank-respecting augmentation of hypergraphs with negamodular constraints

From Egres Open
Jump to: navigation, search

Given a crossing negamodular function [math]R:2^V\to \mathbb{Z}[/math] such that [math]R(X)\ne 1[/math] for every [math]X\subseteq V[/math] and a hypergraph [math]G_0=(V,\mathcal{E}_0)[/math], find a hypergraph [math]G=(V,\mathcal{E})[/math] of minimum total size such that [math]d_G(X)\ge R(X)-d_{G_0}(X)[/math] holds for every [math]X\subseteq V[/math] and the rank of [math]G[/math] does not exceed the rank of [math]G_0[/math].


This problem is open for graphs (i.e. when [math]G_0[/math] is a graph).