Dual parameterization and parameterized approximability of subset graph problems
RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 1, pp. 261-266.

We discuss approximability in FPT-time for the class of subset optimization graph problems where a feasible solution S 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 n-k where n is size of the vertex set and k the standard parameter. We show that under such parameterization, many of these problems, while W[·]-hard, admit parameterized approximation schemata.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2016018
Classification : 68Q15, 68Q17, 68R10, 68W25
Mots clés : Polynomial approximation, parameterized approximation, subset problems
Bonnet, Édouard 1 ; Paschos, Vangelis Th. 2

1 Institute for Computer Science and Control, Hungarian Academy of Sciences (MTA SZTAKI), 1051 Budapest, Hungary.
2 PSL* Research University, Université Paris-Dauphine, LAMSADE, CNRS UMR 7243, Paris, France.
@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

C. Bazgan, B. Escoffier and V. Th. Paschos, 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

L. Cai, 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

M. Demange and V. Th. Paschos, 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).

M.M. Halldórsson, Approximating the minimum maximal independence number. Inform. Process. Lett. 46 (1993) 169–172. | DOI | MR | Zbl

A. Kesselman and K. Kogan, Nonpreemptive scheduling of optical switches. IEEE Trans. Commun. 55 (2007) 1212–1219. | DOI

S. Khot and V. Raman, Parameterized complexity of finding subgraphs with hereditary properties. Theoret. Comput. Sci. 289 (2002) 997–1008. | DOI | MR | Zbl

D. Marx, Parameterized complexity and approximation algorithms. Comput. J. 51 (2008) 60–78. | DOI

C. Sloper and J.A. Telle, An overview of techniques for designing parameterized algorithms. Comput. J. 51 (2008) 122–136. | DOI

V.G. Vizing, On an estimate of the chromatic class of a p-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 :