We discuss approximability in FPT-time for the class of subset optimization graph problems where a feasible solution is a subset of the vertex set of the input graph. This class encompasses many well-known problems, such as min dominating set, min vertex cover, max independent set, min feedback vertex set. We study approximability of such problems with respect to the dual parameter where is size of the vertex set and the standard parameter. We show that under such parameterization, many of these problems, while W[]-hard, admit parameterized approximation schemata.
Accepté le :
DOI : 10.1051/ro/2016018
Mots-clés : Polynomial approximation, parameterized approximation, subset problems
@article{RO_2017__51_1_261_0,
author = {Bonnet, \'Edouard and Paschos, Vangelis Th.},
title = {Dual parameterization and parameterized approximability of subset graph problems},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {261--266},
publisher = {EDP-Sciences},
volume = {51},
number = {1},
year = {2017},
doi = {10.1051/ro/2016018},
zbl = {1362.68290},
mrnumber = {3605903},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro/2016018/}
}
TY - JOUR AU - Bonnet, Édouard AU - Paschos, Vangelis Th. TI - Dual parameterization and parameterized approximability of subset graph problems JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2017 SP - 261 EP - 266 VL - 51 IS - 1 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2016018/ DO - 10.1051/ro/2016018 LA - en ID - RO_2017__51_1_261_0 ER -
%0 Journal Article %A Bonnet, Édouard %A Paschos, Vangelis Th. %T Dual parameterization and parameterized approximability of subset graph problems %J RAIRO - Operations Research - Recherche Opérationnelle %D 2017 %P 261-266 %V 51 %N 1 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2016018/ %R 10.1051/ro/2016018 %G en %F RO_2017__51_1_261_0
Bonnet, Édouard; Paschos, Vangelis Th. Dual parameterization and parameterized approximability of subset graph problems. RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 1, pp. 261-266. doi : 10.1051/ro/2016018. http://www.numdam.org/articles/10.1051/ro/2016018/
J. Alber and R. Niedermeier, Improved tree decomposition based algorithms for domination-like problems. In Proc. Latin American Symposium on Theoretical Informatics, LATIN’02. Vol. 2286 of Lect. Notes Comput. Sci., edited by S. Rajsbaum. Springer-Verlag (2002) 613–628. | MR | Zbl
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 (1999). | MR | Zbl
, and , Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness. Theoret. Comput. Sci. 339 (2005) 272–292. | DOI | MR | Zbl
D. Bertsimas, C.-P. Teo and R. Vohra, On dependent randomized rounding algorithms. In Proc. International Conference on Integer Programming and Combinatorial Optimization, IPCO’96. Vol. 1084 of Lect. Notes Comput. Sci.. Springer-Verlag (1996) 330–344. | MR
H.L. Bodlaender, B.M.P. Jansen and S. Kratsch, Preprocessing for treewidth: a combinatorial analysis through kernelization. In Proc. 38th ICALP. Vol. 6755 of Lect. Notes Comput. Sci. Springer (2011). | MR | Zbl
N. Bourgeois, K. Dabrowski, M. Demange and V. Th. Paschos, Playing with parameters: structural parameterization in graphs. Preprint (2013). | arXiv
, Parameter complexity of cardinality constrained optimization problems. Comput. J. 51 (2008) 102–121. | DOI
L. Cai and X. Huang, Fixed-parameter approximation: conceptual framework and approximability results. In Proc. International Workshop on Parameterized and Exact Computation, IWPEC’06, Vol. 4169 of Lect. Notes Comput. Sci., edited by H.L. Bodlaender and M.A. Langston. Springer-Verlag (2006) 96–108. | MR | Zbl
M. Cesati, Compendium of parameterized problems. Available at http://cesati.sprg.uniroma2.it/research/compendium/.
Y. Chen, M. Grohe and M. Grüber, On parameterized approximability. In Proc. International Workshop on Parameterized and Exact Computation, IWPEC’06. Vol. 4169 of Lect. Notes Comput. Sci., edited by H.L. Bodlaender and M.A. Langston. Springer-Verlag (2006) 109–120. | MR | Zbl
and , On an approximation measure founded on the links between optimization and polynomial approximation theory. Theoret. Comput. Sci. 158 (1996) 117–141. | DOI | MR | Zbl
R.G. Downey and M.R. Fellows, Parameterized complexity. Monographs in Computer Science. Springer, New York (1999). | MR | Zbl
R.G. Downey, M.R. Fellows and C. McCartin, Parameterized approximation problems. In Proc. International Workshop on Parameterized and Exact Computation, IWPEC’06. Vol. 4169 of Lect. Notes Comput. Sci., edited by H.L. Bodlaender and M.A. Langston. Springer-Verlag (2006) 121–129. | MR | Zbl
H. Fernau, Parameterized algorithms: a graph-theoretic approach. Habilitationsschrift, Universität Tübingen (2005).
, Approximating the minimum maximal independence number. Inform. Process. Lett. 46 (1993) 169–172. | DOI | MR | Zbl
and , Nonpreemptive scheduling of optical switches. IEEE Trans. Commun. 55 (2007) 1212–1219. | DOI
and , Parameterized complexity of finding subgraphs with hereditary properties. Theoret. Comput. Sci. 289 (2002) 997–1008. | DOI | MR | Zbl
, Parameterized complexity and approximation algorithms. Comput. J. 51 (2008) 60–78. | DOI
and , An overview of techniques for designing parameterized algorithms. Comput. J. 51 (2008) 122–136. | DOI
, On an estimate of the chromatic class of a -graph. Diskret. Analiz. 3 (1964) 25–30. | MR
G.J. Woeginger, Exact algorithms for NP-hard problems: a survey. In Combinatorial Optimization – Eureka! You shrink!. Vol. 2570 of Lect. Notes Comput. Sci., edited by M. Juenger, G. Reinelt and G. Rinaldi. Springer-Verlag (2003) 185–207. | MR | Zbl
D. Zuckerman, Linear degree extractors and the inapproximability of max clique and chromatic number. In Proc. STOC’06 (2006) 681–690. | MR | Zbl
Cité par Sources :
