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.
Mots-clés : NP-optimization problems, minimaximal and maximinimal NP-optimization problems, approximation algorithms, hardness of approximation, APX-hardness, AP-reduction, L-reduction, S-reduction
@article{ITA_2001__35_3_287_0,
author = {Mishra, Sounaka and Sikdar, Kripasindhu},
title = {On the hardness of approximating some {NP-optimization} problems related to minimum linear ordering problem},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {287--309},
publisher = {EDP-Sciences},
volume = {35},
number = {3},
year = {2001},
mrnumber = {1869219},
zbl = {1014.68063},
language = {en},
url = {http://www.numdam.org/item/ITA_2001__35_3_287_0/}
}
TY - JOUR AU - Mishra, Sounaka AU - Sikdar, Kripasindhu TI - On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2001 SP - 287 EP - 309 VL - 35 IS - 3 PB - EDP-Sciences UR - http://www.numdam.org/item/ITA_2001__35_3_287_0/ LA - en ID - ITA_2001__35_3_287_0 ER -
%0 Journal Article %A Mishra, Sounaka %A Sikdar, Kripasindhu %T On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2001 %P 287-309 %V 35 %N 3 %I EDP-Sciences %U http://www.numdam.org/item/ITA_2001__35_3_287_0/ %G en %F ITA_2001__35_3_287_0
Mishra, Sounaka; Sikdar, Kripasindhu. On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 3, pp. 287-309. http://www.numdam.org/item/ITA_2001__35_3_287_0/
[1] and, Hardness of approximating problems on cubic graphs, in Proc. 3rd Italian Conf. on Algorithms and Complexity. Springer-Verlag, Lecture Notes in Comput. Sci. 1203 (1997) 288-298. | MR
[2] , and, Fundamental Study: Approximate solution of NP optimization problems. Theoret. Comput. Sci. 150 (1995) 1-55. | MR | Zbl
[3] ,,,, and, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer-Verlag, Berlin Heidelberg (1999). | Zbl
[4] , and, Constant ratio approximations of feedback vertex sets in weighted undirected graphs, in 6th Annual International Symposium on Algorithms and Computation (1995).
[5] , and, The algorithmic use of hypertree structure and maximum neighborhood orderings. Discrete Appl. Math. 82 (1998) 43-77. | MR | Zbl
[6] and, On domination problems for permutation and other graphs. Theoret. Comput. Sci. 54 (1987) 181-198. | MR | Zbl
[7] and, A new heuristic algorithm solving the linear ordering problem. Comput. Optim. Appl. 6 (1996) 191-205. | MR | Zbl
[8] , Efficient algorithms for the domination problems on interval and circular-arc graphs. SIAM J. Comput. 27 (1998) 1671-1694. | MR | Zbl
[9] and, Approximation algorithms for achromatic number, in Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms. ACM-SIAM (1997) 558-563. | MR
[10] ,, and, On the computational complexity of upper fractional domination. Discrete Appl. Math. 27 (1990) 195-207. | MR | Zbl
[11] ,, and, Structures in approximation classes, in 1st. Annu. Int. Conf. on Computing and Combinatorics. Springer-Verlag, Lecture Notes in Comput. Sci. 959 (1995) 539-548. | MR
[12] and, Zero knowledge and the chromatic number. Proc. Comp. Complexity (1996).
[13] , Independent domination in chordal graphs. Oper. Res. Lett. 1 (1982) 134-138. | MR | Zbl
[14] and, Domination in permutation graphs. J. Algorithms 6 (1985) 309-321. | MR | Zbl
[15] , Personal communication (1999).
[16] , and, A cutting plane algorithm for linear ordering problem. Oper. Res. 32 (1984) 1195-1220. | MR | Zbl
[17] , and, On the acyclic subgraph polytope. Math. Programming 33 (1985) 28-42. | MR | Zbl
[18] , Clique is hard to approximate within , in Proc. 37th IEEE Sympo. on Foundation of Comput. Sci. (1996) 627-636. | MR
[19] , Graph Theory. Addition-Wesley, Reading, MA (1969). | MR | Zbl
[20] , Maximum versus minimum invariants for graphs. J. Graph Theory 7 (1983) 275-284. | MR | Zbl
[21] and, The achromatic number of a graph. J. Combin. Theory 8 (1970) 154-161. | MR | Zbl
[22] , Approximating the minimum maximal independence number. Inform. Process. Lett. 46 (1993) 169-172. | MR | Zbl
[23] , On approximating the minimum independent dominating set. Inform. Process. Lett. 37 (1991) 197-200. | MR | Zbl
[24] , On the Approximability of NP-complete Optimization Problems, Ph.D. Thesis. Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm (1992).
[25] , Polynomially bounded minimization problems that are hard to approximate. Nordic J. Comput. 1 (1994) 317-331. | MR | Zbl
[26] ,, and, On syntactic versus computational views of approximability, in Proc. 35th Ann. IEEE Symp. on Foundations of Computer Science (1994) 819-836.
[27] and, On the hardness of approximating minimization problems. J. ACM 41 (1994) 960-981. | MR | Zbl
[28] and, Optimization, Approximation, and Complexity Classes. J. Comput. System Sci. 43 (1991) 425-440. | MR | Zbl
[29] , and, Maximinimal/Minimaximal connectivity in graphs. Ars Combinatoria 21 (1986) 59-70. | MR | Zbl
[30] , Minimaximal and maximinimal optimization problems: A partial order-based approach, Ph.D. Thesis. University of Glasgow (1998).
[31] and, On approximation solutions of linear ordering and related NP-Optimization problems on graphs (Extended Abstract), Electronic Notes in Discrete Mathematics, Vol. 8, edited by H. Broersma, U. Faigle, J. Hurink and S. Pickl. Elsevier Science Publishers (2001), Full version submitted for publication.
[32] and, On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem (extended abstract), edited by J. van Leeuwen et al., IFIP TCS 2000. Lecture Notes in Comput. Sci. 1872 (2000) 186-199. | Zbl
[33] , and, On the nonseparating independent set problem and feedback set problem for graphs with no vertex exceeding three. Discrete Math. 72 (1988) 355-360. | MR | Zbl
