# Changing conservative weightings in bipartite graphs

Let *G=(A,B;E)* be a bipartite graph, and [math]w:E \to \{1,-1\}[/math] a conservative weighting. Can we determine in polynomial time the maximum number of positive edges that can be negated so that the weighting remains conservative?

## Remarks

We can decide whether a weighting is conservative (and compute the distance of two nodes) using minimum weight T-joins. Conservative weightings of bipartite graphs have the following characterization:

**Theorem ^{[1]}.** The weighting [math]w:E \to \{1,-1\}[/math] is conservative if and only if there is a partition [math]\{X_1,\dots,X_k\}[/math] of [math]A \cup B[/math] such that for every

*i*every component of [math](A \cup B)\setminus X_i[/math] is entered by at most one negative edge.

In general graphs, the problem proved to be NP-complete ^{[2]}.

## References

- ↑ A. Frank, A. Sebő, É. Tardos,
*Covering directed and odd cuts*, Mathematical Programming Studies 22 (1984), 99-112. DOI link, Author link - ↑ K. Bérczi and E.R. Kovács,
*A note on conservative costs*, EGRES Quick Proof no. 2011-06