Local edge-connectivity augmentation of a hypergraph with fixed rank

Definitions and mathematical statement

Fix an integer $q\ge2$. Let $H_0=(V,\mathcal E_0)$ be a finite hypergraph whose edges have size at most $q$, and let $r(x,y)=r(y,x)$ be prescribed nonnegative integer demands for distinct vertices. For a hypergraph $H$, define \[ \lambda_H(x,y)=\min_{x\in X,\ y\notin X} |\{E\in\mathcal E(H):E\cap X\ne\varnothing, E\setminus X\ne\varnothing\}|. \] Indexed parallel hyperedges are counted separately. This is the least number of hyperedges whose deletion separates $x$ and $y$.

Can one find, in polynomial time for each fixed $q$, an undirected loopless multigraph $G$ on $V$ minimizing $|E(G)|$ subject to \[ \lambda_{H_0+G}(x,y)\ge r(x,y) \quad(x\ne y)? \] The added objects are ordinary two-vertex edges, while the original hyperedges are retained. The rank bound $q$ is a fixed constant, not an input parameter on which the exponent of the polynomial must be uniform.

Demands and any multiplicities may be encoded in binary; the output may give edge multiplicities in binary as well. This avoids requiring an exponentially long list of identical added edges. The objective counts added edge copies, not the number of endpoint pairs used. The optimization must meet all pairwise demands in one augmentation.

Short English statement

Can minimum edge augmentation for prescribed pairwise connectivity be solved efficiently when the original hyperedges have a fixed maximum size?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000049 (AMR-029-0049), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Egres Open - List of open problems, Open-problem page: Local edge-connectivity augmentation of a hypergraph with fixed rank. Original source indexed by AMR-029-0049. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Local edge-connectivity augmentation of a hypergraph with fixed rank. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Local_edge-connectivity_augmentation_of_a_hypergraph_with_fixed_rank.