EDP Sciences Journals List
Home Document
Subscriber Authentication Point
Issue RAIRO-Theor. Inf. 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?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.
  • If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
  • You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
  • You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.