A note on conservative costs

Kristóf Bérczi, Erika Renáta Bérczi-Kovács


Let G=(V,E) be an undirected graph and c:E->{-1,+1} a conservative cost function. We show that the problem of determining the maximum number of edges whose cost can be changed from 1 to -1 without violating the conservativeness of c is NP-complete. A similar result about directed graphs is also proved.

Bibtex entry:

AUTHOR = {B{\'e}rczi, Krist{\'o}f and B{\'e}rczi-Kov{\'a}cs Ren{\'a}ta, Erika},
TITLE = {A note on conservative costs},
NOTE= {{\tt egres.elte.hu}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2011},
NUMBER = {QP-2011-06}

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