On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem

Sounaka Mishra; Kripasindhu Sikdar

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2001)

  • Volume: 35, Issue: 3, page 287-309
  • ISSN: 0988-3754

Abstract

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

How to cite

top

Mishra, Sounaka, and 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 35.3 (2001): 287-309. <http://eudml.org/doc/92667>.

@article{Mishra2001,
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.},
author = {Mishra, Sounaka, Sikdar, Kripasindhu},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {NP-optimization problems; minimaximal and maximinimal NP-optimization problems; approximation algorithms; hardness of approximation; APX-hardness; AP-reduction; L-reduction; S-reduction; minimum linear ordering problem},
language = {eng},
number = {3},
pages = {287-309},
publisher = {EDP-Sciences},
title = {On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem},
url = {http://eudml.org/doc/92667},
volume = {35},
year = {2001},
}

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
PB - EDP-Sciences
VL - 35
IS - 3
SP - 287
EP - 309
AB - 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.
LA - eng
KW - NP-optimization problems; minimaximal and maximinimal NP-optimization problems; approximation algorithms; hardness of approximation; APX-hardness; AP-reduction; L-reduction; S-reduction; minimum linear ordering problem
UR - http://eudml.org/doc/92667
ER -

References

top
  1. [1] P. Alimonti and V. Kann, 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. MR1488983
  2. [2] G. Ausiello, P. Crescenzi and M. Protasi, Fundamental Study: Approximate solution of NP optimization problems. Theoret. Comput. Sci. 150 (1995) 1-55. Zbl0874.68145MR1357119
  3. [3] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti–Spaccamela and M. Protasi, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer-Verlag, Berlin Heidelberg (1999). Zbl0937.68002
  4. [4] V. Bafna, P. Berman and T. Fujito, Constant ratio approximations of feedback vertex sets in weighted undirected graphs, in 6th Annual International Symposium on Algorithms and Computation (1995). 
  5. [5] A. Brandstädt, V.D. Chepoi and F.F. Dragan, The algorithmic use of hypertree structure and maximum neighborhood orderings. Discrete Appl. Math. 82 (1998) 43-77. Zbl0893.05018MR1610005
  6. [6] A. Brandstädt and D. Kratsch, On domination problems for permutation and other graphs. Theoret. Comput. Sci. 54 (1987) 181-198. Zbl0641.68100MR919590
  7. [7] S. Chanas and P. Kobylański, A new heuristic algorithm solving the linear ordering problem. Comput. Optim. Appl. 6 (1996) 191-205. Zbl0860.90100MR1398267
  8. [8] M.S. Chang, Efficient algorithms for the domination problems on interval and circular-arc graphs. SIAM J. Comput. 27 (1998) 1671-1694. Zbl0911.05051MR1622646
  9. [9] A. Chaudhary and S. Vishwanathan, Approximation algorithms for achromatic number, in Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms. ACM-SIAM (1997) 558-563. Zbl1321.68494MR1447703
  10. [10] G.A. Cheston, G. Fricke, S.T. Hedetniemi and D.P. Jacobs, On the computational complexity of upper fractional domination. Discrete Appl. Math. 27 (1990) 195-207. Zbl0717.05068MR1058945
  11. [11] P. Crescenzi, V. Kann, R. Silvestri and L. Trevisan, Structures in approximation classes, in 1st. Annu. Int. Conf. on Computing and Combinatorics. Springer-Verlag, Lecture Notes in Comput. Sci. 959 (1995) 539-548. Zbl0932.68137MR1450157
  12. [12] U. Feige and J. Kilian, Zero knowledge and the chromatic number. Proc. Comp. Complexity (1996). Zbl0921.68089
  13. [13] M. Fraber, Independent domination in chordal graphs. Oper. Res. Lett. 1 (1982) 134-138. Zbl0495.05053MR687354
  14. [14] M. Fraber and J.M. Keil, Domination in permutation graphs. J. Algorithms 6 (1985) 309-321. Zbl0598.05056MR800722
  15. [15] T. Fujito, Personal communication (1999). 
  16. [16] M. Grötschel, M. Jünger and G. Reinelt, A cutting plane algorithm for linear ordering problem. Oper. Res. 32 (1984) 1195-1220. Zbl0554.90077MR775257
  17. [17] M. Grötschel, M. Jünger and G. Reinelt, On the acyclic subgraph polytope. Math. Programming 33 (1985) 28-42. Zbl0577.05034MR809747
  18. [18] J. Håstad, Clique is hard to approximate within n 1 - ϵ , in Proc. 37th IEEE Sympo. on Foundation of Comput. Sci. (1996) 627-636. MR1450661
  19. [19] F. Harary, Graph Theory. Addition-Wesley, Reading, MA (1969). Zbl0182.57702MR256911
  20. [20] F. Harary, Maximum versus minimum invariants for graphs. J. Graph Theory 7 (1983) 275-284. Zbl0515.05053MR710904
  21. [21] F. Harary and S. Hedetniemi, The achromatic number of a graph. J. Combin. Theory 8 (1970) 154-161. Zbl0195.25702MR253930
  22. [22] M.M. Halldórsson, Approximating the minimum maximal independence number. Inform. Process. Lett. 46 (1993) 169-172. Zbl0778.68041MR1229204
  23. [23] R.W. Irving, On approximating the minimum independent dominating set. Inform. Process. Lett. 37 (1991) 197-200. Zbl0713.68033MR1095707
  24. [24] V. Kann, 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. [25] V. Kann, Polynomially bounded minimization problems that are hard to approximate. Nordic J. Comput. 1 (1994) 317-331. Zbl0817.68082MR1335251
  26. [26] S. Khanna, R. Motwani, M. Sudan and U. Vazirani, On syntactic versus computational views of approximability, in Proc. 35th Ann. IEEE Symp. on Foundations of Computer Science (1994) 819-836. Zbl0915.68068
  27. [27] C. Lund and M. Yannakakis, On the hardness of approximating minimization problems. J. ACM 41 (1994) 960-981. Zbl0814.68064MR1371491
  28. [28] C.H. Papadimitriou and M. Yannakakis, Optimization, Approximation, and Complexity Classes. J. Comput. System Sci. 43 (1991) 425-440. Zbl0765.68036MR1135471
  29. [29] K. Peters, R. Laskar and S.T. Hedetniemi, Maximinimal/Minimaximal connectivity in graphs. Ars Combinatoria 21 (1986) 59-70. Zbl0602.05044MR846681
  30. [30] D.F. Manlove, Minimaximal and maximinimal optimization problems: A partial order-based approach, Ph.D. Thesis. University of Glasgow (1998). 
  31. [31] S. Mishra and K. Sikdar, 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. Zbl1014.68063
  32. [32] S. Mishra and K. Sikdar, 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. Zbl1010.90523MR1869219
  33. [33] S. Ueno, Y. Kajtani and S. Gotoh, On the nonseparating independent set problem and feedback set problem for graphs with no vertex exceeding three. Discrete Math. 72 (1988) 355-360. Zbl0678.05026MR975556

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.