| Issue |
RAIRO-Theor. Inf. Appl.
Volume 35, Number 3, May/June 2001
|
|
|---|---|---|
| Page(s) | 287 - 309 | |
| DOI | https://doi.org/10.1051/ita:2001121 | |
| Published online | 15 April 2002 | |
On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem
1
Theoretical Statistics and Mathematics Unit,
Indian Statistical Institute, Calcutta 700 035, India; e-mail: res9513@isical.ac.in
2
Theoretical Statistics and Mathematics Unit,
Indian Statistical Institute, Calcutta 700 035, India; e-mail: sikdar@isical.ac.in
Received:
14
February
2001
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
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.