# Changing conservative weightings in bipartite graphs

Jump to: navigation, search

Let G=(A,B;E) be a bipartite graph, and $w:E \to \{1,-1\}$ 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 $w:E \to \{1,-1\}$ is conservative if and only if there is a partition $\{X_1,\dots,X_k\}$ of $A \cup B$ such that for every i every component of $(A \cup B)\setminus X_i$ is entered by at most one negative edge.

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

## References

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