On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem
Theoretical Statistics and Mathematics Unit,
Indian Statistical Institute, Calcutta 700 035, India; e-mail: firstname.lastname@example.org
2 Theoretical Statistics and Mathematics Unit, Indian Statistical Institute, Calcutta 700 035, India; e-mail: email@example.com
Accepted: 24 August 2001
We study hardness of approximating several minimaximal and maximinimal NP-optimization problems related to the minimum linear ordering problem (MINLOP). MINLOP is to find a minimum weight acyclic tournament in a given arc-weighted complete digraph. MINLOP is APX-hard but its unweighted version is polynomial time solvable. We prove that MIN-MAX-SUBDAG problem, which is a generalization of MINLOP and requires to find a minimum cardinality maximal acyclic subdigraph of a given digraph, is, however, APX-hard. Using results of Håstad concerning hardness of approximating independence number of a graph we then prove similar results concerning MAX-MIN-VC (respectively, MAX-MIN-FVS) which requires to find a maximum cardinality minimal vertex cover in a given graph (respectively, a maximum cardinality minimal feedback vertex set in a given digraph). We also prove APX-hardness of these and several related problems on various degree bounded graphs and digraphs.
Mathematics Subject Classification: 68Q17 / 68R01 / 68W25
Key words: NP-optimization problems / Minimaximal and maximinimal NP-opt- imization problems / Approximation algorithms / Hardness of approximation / APX-hardness / AP-reduction / L-reduction / S-reduction.
© EDP Sciences, 2001