Changing conservative weightings in bipartite graphs

Definitions and mathematical statement

Let $G=(A\sqcup B,E)$ be a finite bipartite graph. A weighting $w:E\to\{-1,1\}$ is conservative when every simple cycle $C$ satisfies \[ \sum_{e\in E(C)}w(e)\ge0. \] This is a condition on simple undirected cycles; it is not a prohibition on negative closed walks that immediately traverse an edge and return. Write $E_+=\{e:w(e)=1\}$.

For $F\subseteq E_+$, change the sign of the edges of $F$, leaving every other weight fixed. The resulting weighting $w_F$ is conservative exactly when \[ 2|F\cap E(C)|\le\sum_{e\in E(C)}w(e) \quad\text{for every simple cycle }C. \] Given a conservative input weighting, can one compute in polynomial time the largest possible value of $|F|$ and construct a maximizing set?

The selected signs must be changed simultaneously; a largest feasible set is sought, rather than a set to which no additional edge can be added. The formulation permits all bipartite input graphs, including disconnected ones. Bridges lie on no cycle and hence impose no cycle obstruction to a sign change. Although feasibility is expressed using every cycle, an efficient algorithm must avoid enumerating an exponentially large cycle family in general.

Short English statement

How many positive edges of a conservatively weighted bipartite graph can be made negative while keeping every cycle's total weight nonnegative?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000010 (AMR-029-0010), 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: Changing conservative weightings in bipartite graphs. Original source indexed by AMR-029-0010. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Changing conservative weightings in bipartite graphs. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Changing_conservative_weightings_in_bipartite_graphs.