QP-2011-06

A note on conservative costs

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



Abstract

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:

@techreport{egresqp-11-06,
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!