On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem
Sounaka Mishra; Kripasindhu Sikdar
RAIRO - Theoretical Informatics and Applications (2010)
- Volume: 35, Issue: 3, page 287-309
- ISSN: 0988-3754
Access Full Article
topAbstract
topHow to cite
topMishra, Sounaka, and Sikdar, Kripasindhu. "On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem." RAIRO - Theoretical Informatics and Applications 35.3 (2010): 287-309. <http://eudml.org/doc/222064>.
@article{Mishra2010,
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},
keywords = {NP-optimization problems; Minimaximal and maximinimal
NP-opt- imization problems; Approximation algorithms; Hardness of approximation;
APX-hardness; AP-reduction; L-reduction; S-reduction.; minimum linear ordering problem},
language = {eng},
month = {3},
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/222064},
volume = {35},
year = {2010},
}
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
DA - 2010/3//
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-opt- imization problems; Approximation algorithms; Hardness of approximation;
APX-hardness; AP-reduction; L-reduction; S-reduction.; minimum linear ordering problem
UR - http://eudml.org/doc/222064
ER -
References
top- 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.
- G. Ausiello, P. Crescenzi and M. Protasi, Fundamental Study: Approximate solution of NP optimization problems. Theoret. Comput. Sci.150 (1995) 1-55.
- 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).
- 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).
- 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.
- A. Brandstädt and D. Kratsch, On domination problems for permutation and other graphs. Theoret. Comput. Sci.54 (1987) 181-198.
- S. Chanas and P. Kobylanski, A new heuristic algorithm solving the linear ordering problem. Comput. Optim. Appl.6 (1996) 191-205.
- M.S. Chang, Efficient algorithms for the domination problems on interval and circular-arc graphs. SIAM J. Comput.27 (1998) 1671-1694.
- 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.
- 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.
- 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.
- U. Feige and J. Kilian, Zero knowledge and the chromatic number. Proc. Comp. Complexity (1996).
- M. Fraber, Independent domination in chordal graphs. Oper. Res. Lett.1 (1982) 134-138.
- M. Fraber and J.M. Keil, Domination in permutation graphs. J. Algorithms6 (1985) 309-321.
- T. Fujito, Personal communication (1999).
- M. Grötschel, M. Jünger and G. Reinelt, A cutting plane algorithm for linear ordering problem. Oper. Res.32 (1984) 1195-1220.
- M. Grötschel, M. Jünger and G. Reinelt, On the acyclic subgraph polytope. Math. Programming33 (1985) 28-42.
- J. Håstad, Clique is hard to approximate within n1-ε, in Proc. 37th IEEE Sympo. on Foundation of Comput. Sci. (1996) 627-636.
- F. Harary, Graph Theory. Addition-Wesley, Reading, MA (1969).
- F. Harary, Maximum versus minimum invariants for graphs. J. Graph Theory7 (1983) 275-284.
- F. Harary and S. Hedetniemi, The achromatic number of a graph. J. Combin. Theory8 (1970) 154-161.
- M.M. Halldórsson, Approximating the minimum maximal independence number. Inform. Process. Lett.46 (1993) 169-172.
- R.W. Irving, On approximating the minimum independent dominating set. Inform. Process. Lett.37 (1991) 197-200.
- 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).
- V. Kann, Polynomially bounded minimization problems that are hard to approximate. Nordic J. Comput.1 (1994) 317-331.
- 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.
- C. Lund and M. Yannakakis, On the hardness of approximating minimization problems. J. ACM41 (1994) 960-981.
- C.H. Papadimitriou and M. Yannakakis, Optimization, Approximation, and Complexity Classes. J. Comput. System Sci.43 (1991) 425-440.
- K. Peters, R. Laskar and S.T. Hedetniemi, Maximinimal/Minimaximal connectivity in graphs. Ars Combinatoria21 (1986) 59-70.
- D.F. Manlove, Minimaximal and maximinimal optimization problems: A partial order-based approach, Ph.D. Thesis. University of Glasgow (1998).
- 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.
- 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.
- 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.
NotesEmbed ?
topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.