کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418036 | 681602 | 2015 | 10 صفحه PDF | دانلود رایگان |
We address the max min vertex cover problem, which is the maximization version of the well studied min independent dominating set problem, known to be NP-hard and highly inapproximable in polynomial time. We present tight approximation results for this problem on general graphs, namely a polynomial approximation algorithm which guarantees an n−12 approximation ratio, while showing that unless P=NP, the problem is inapproximable within ratio nε−(12) for any strictly positive εε. We also analyze the problem on various restricted classes of graphs, on which we show polynomiality or constant-approximability of the problem. Finally, we show that the problem is fixed-parameter tractable with respect to the size of an optimal solution, to treewidth and to the size of a maximum matching.
Journal: Discrete Applied Mathematics - Volume 196, 11 December 2015, Pages 62–71