QP-2011-06

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:

@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}

}