Maximum negatable set in bipartite matching covered graphs

G. Sanjith


In an undirected graph G=(V,E) with a conservative weighting w:E->{1, -1}, the problem of determining the maximum number of edges whose weight can be changed from 1 to -1 retaining the conservativeness of the weighting is known to be NP-complete. We show that this problem is polynomially tractable for bipartite matching-covered graphs. We also note that the directed version of this problem remains NP-complete for oriented bipartite matching-covered graphs.

Bibtex entry:

AUTHOR = {Sanjith, G.},
TITLE = {Maximum negatable set in bipartite matching covered graphs},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2012},
NUMBER = {TR-2012-11}

Last modification: 13.3.2018. Please email your comments to Tamás Király!