Changing conservative weightings in bipartite graphs

From Egres Open
Jump to: navigation, search

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?


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].


  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