On the Complexity of the Upper r-Tolerant Edge Cover Problem

摘要

We consider the problem of computing edge covers that are tolerant to a certain number of edge deletions. We call the problem of finding a minimum such cover r-TOLERANT EDGE COVER (r-EC) and the problem of finding a maximum minimal such cover Upper r-EC. We present several NP-hardness and inapproximability results for UPPER r-EC and for some of its special cases.