On the independent set interdiction problem

Gholam Hassan Shirdel, Nasrin Kahkeshani


The purpose of the independent set interdiction problem in the weighted graph $G$ is to determine a set of vertices $R^*$ such that the weight of the maximum independent set in $G-R^*$ is minimized. We define an approximate solution for this problem. Then, an upper bound for the relative error of this problem is obtained. We show that the limit of the relative error of the independent set interdiction problem in some subclasses of the generalized Petersen graphs is zero as the number of vertices tends to infinity.


Independent set, interdiction, generalized Petersen graph

Full Text:


DOI: http://dx.doi.org/10.5614/ejgta.2015.3.2.2


  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats