RAIRO - Theoretical Informatics and Applications

Table of Contents - May 2001 - Volume 35, Issue 03  

Research Article

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

Mishra, Sounakaa1 and Sikdar, Kripasindhua2

a1 Theoretical Statistics and Mathematics Unit, Indian Statistical Institute, Calcutta 700 035, India; e-mail: res9513@isical.ac.in

a2 Theoretical Statistics and Mathematics Unit, Indian Statistical Institute, Calcutta 700 035, India; e-mail: sikdar@isical.ac.in

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.

(Received February 14 2001)

(Accepted August 24 2001)

(Online publication April 15 2002)

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.

Mathematics Subject Classification:

  • 68Q17;
  • 68R01;
  • 68W25