a1 Theoretical Statistics and Mathematics Unit, Indian Statistical Institute, Calcutta 700 035, India; e-mail: email@example.com
a2 Theoretical Statistics and Mathematics Unit, Indian Statistical Institute, Calcutta 700 035, India; e-mail: firstname.lastname@example.org
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.
(Received February 14 2001)
(Accepted August 24 2001)
(Online publication April 15 2002)
Mathematics Subject Classification: