Issue Theoret. Informatics Appl. Volume 35, Number 3, May-June 2001 Page(s) 287 - 309 DOI 10.1051/ita:2001121

DOI: 10.1051/ita:2001121


Theoret. Informatics Appl. 35, 287-309 (2001)

On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem

Sounaka Mishra and Kripasindhu Sikdar

Theoretical Statistics and Mathematics Unit, Indian Statistical Institute, Calcutta 700 035, India; (res9513@isical.ac.in, sikdar@isical.ac.in)

(Received February 14, 2001. Accepted August 24, 2001.)

Abstract
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.

AMS Subject: 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

What is OpenURL?