×

On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem. (English) Zbl 1014.68063

Summary: 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 Hastad 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.

MSC:

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68R01 General topics of discrete mathematics in relation to computer science
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI Numdam Numdam EuDML

References:

[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 . MR 1488983
[2] G. Ausiello , P. Crescenzi and M. Protasi , Fundamental Study: Approximate solution of NP optimization problems . Theoret. Comput. Sci. 150 ( 1995 ) 1 - 55 . MR 1357119 | Zbl 0874.68145 · Zbl 0874.68145 · doi:10.1016/0304-3975(94)00291-P
[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 ). Zbl 0937.68002 · Zbl 0937.68002
[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] 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 . MR 1610005 | Zbl 0893.05018 · Zbl 0893.05018 · doi:10.1016/S0166-218X(97)00125-X
[6] A. Brandstädt and D. Kratsch , On domination problems for permutation and other graphs . Theoret. Comput. Sci. 54 ( 1987 ) 181 - 198 . MR 919590 | Zbl 0641.68100 · Zbl 0641.68100 · doi:10.1016/0304-3975(87)90128-9
[7] S. Chanas and P. Kobylański , A new heuristic algorithm solving the linear ordering problem . Comput. Optim. Appl. 6 ( 1996 ) 191 - 205 . MR 1398267 | Zbl 0860.90100 · Zbl 0860.90100 · doi:10.1007/BF00249646
[8] M.S. Chang , Efficient algorithms for the domination problems on interval and circular-arc graphs . SIAM J. Comput. 27 ( 1998 ) 1671 - 1694 . MR 1622646 | Zbl 0911.05051 · Zbl 0911.05051 · doi:10.1137/S0097539792238431
[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 . MR 1447703 · Zbl 1051.05076
[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 . MR 1058945 | Zbl 0717.05068 · Zbl 0717.05068 · doi:10.1016/0166-218X(90)90065-K
[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 . MR 1450157 · Zbl 0932.68137
[12] U. Feige and J. Kilian , Zero knowledge and the chromatic number . Proc. Comp. Complexity ( 1996 ). · Zbl 0921.68089
[13] M. Fraber , Independent domination in chordal graphs . Oper. Res. Lett. 1 ( 1982 ) 134 - 138 . MR 687354 | Zbl 0495.05053 · Zbl 0495.05053 · doi:10.1016/0167-6377(82)90015-3
[14] M. Fraber and J.M. Keil , Domination in permutation graphs . J. Algorithms 6 ( 1985 ) 309 - 321 . MR 800722 | Zbl 0598.05056 · Zbl 0598.05056 · doi:10.1016/0196-6774(85)90001-X
[15] T. Fujito , Personal communication (1999).
[16] M. Grötschel , M. Jünger and G. Reinelt , A cutting plane algorithm for linear ordering problem . Oper. Res. 32 ( 1984 ) 1195 - 1220 . MR 775257 | Zbl 0554.90077 · Zbl 0554.90077 · doi:10.1287/opre.32.6.1195
[17] M. Grötschel , M. Jünger and G. Reinelt , On the acyclic subgraph polytope . Math. Programming 33 ( 1985 ) 28 - 42 . MR 809747 | Zbl 0577.05034 · Zbl 0577.05034 · doi:10.1007/BF01582009
[18] J. Håstad , Clique is hard to approximate within \(n^{1-\epsilon }\) , in Proc. 37th IEEE Sympo. on Foundation of Comput. Sci. ( 1996 ) 627 - 636 . MR 1450661
[19] F. Harary , Graph Theory . Addition-Wesley, Reading, MA ( 1969 ). MR 256911 | Zbl 0182.57702 · Zbl 0182.57702
[20] F. Harary , Maximum versus minimum invariants for graphs . J. Graph Theory 7 ( 1983 ) 275 - 284 . MR 710904 | Zbl 0515.05053 · Zbl 0515.05053 · doi:10.1002/jgt.3190070302
[21] F. Harary and S. Hedetniemi , The achromatic number of a graph . J. Combin. Theory 8 ( 1970 ) 154 - 161 . MR 253930 | Zbl 0195.25702 · Zbl 0195.25702 · doi:10.1016/S0021-9800(70)80072-2
[22] M.M. Halldórsson , Approximating the minimum maximal independence number . Inform. Process. Lett. 46 ( 1993 ) 169 - 172 . MR 1229204 | Zbl 0778.68041 · Zbl 0778.68041 · doi:10.1016/0020-0190(93)90022-2
[23] R.W. Irving , On approximating the minimum independent dominating set . Inform. Process. Lett. 37 ( 1991 ) 197 - 200 . MR 1095707 | Zbl 0713.68033 · Zbl 0713.68033 · doi:10.1016/0020-0190(91)90188-N
[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] V. Kann , Polynomially bounded minimization problems that are hard to approximate . Nordic J. Comput. 1 ( 1994 ) 317 - 331 . MR 1335251 | Zbl 0817.68082 · Zbl 0817.68082
[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 . · Zbl 0915.68068
[27] C. Lund and M. Yannakakis , On the hardness of approximating minimization problems . J. ACM 41 ( 1994 ) 960 - 981 . MR 1371491 | Zbl 0814.68064 · Zbl 0814.68064 · doi:10.1145/185675.306789
[28] C.H. Papadimitriou and M. Yannakakis , Optimization , Approximation, and Complexity Classes. J. Comput. System Sci. 43 ( 1991 ) 425 - 440 . MR 1135471 | Zbl 0765.68036 · Zbl 0765.68036 · doi:10.1016/0022-0000(91)90023-X
[29] K. Peters , R. Laskar and S.T. Hedetniemi , Maximinimal/Minimaximal connectivity in graphs . Ars Combinatoria 21 ( 1986 ) 59 - 70 . MR 846681 | Zbl 0602.05044 · Zbl 0602.05044
[30] D.F. Manlove , Minimaximal and maximinimal optimization problems: A partial order-based approach , Ph.D. Thesis. University of Glasgow ( 1998 ).
[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. · Zbl 1014.68063
[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 . MR 1869219 | Zbl 1010.90523 · Zbl 1010.90523
[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 . MR 975556 | Zbl 0678.05026 · Zbl 0678.05026 · doi:10.1016/0012-365X(88)90226-9
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.