Parameterized Inapproximability of Degree Anonymization
Bazgan, Cristina; Nichterlein, André (2014), Parameterized Inapproximability of Degree Anonymization, dans Cygan, Marek; Heggernes, Pinar, Parameterized and Exact Computation, Springer : Cham, p. 75-84. 10.1007/978-3-319-13524-3_7
Type
Communication / ConférenceDate
2014Titre du colloque
9th International Symposium, IPEC 2014Date du colloque
2014-09Ville du colloque
WroclawPays du colloque
PolandTitre de l'ouvrage
Parameterized and Exact ComputationAuteurs de l’ouvrage
Cygan, Marek; Heggernes, PinarÉditeur
Springer
Ville d’édition
Cham
Isbn
978-3-319-13523-6
Nombre de pages
343Pages
75-84
Identifiant publication
Métadonnées
Afficher la notice complèteAuteur(s)
Bazgan, CristinaLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Nichterlein, André
Department of Software Engineering and Theoretical Computer Science [SWT - TUB]
Résumé (EN)
The Degree Anonymity problem arises in the context of combinatorial graph anonymization. It asks, given a graph G and two integers k and s, whether G can be made k-anonymous with at most s modifications. Here, a graph is k-anonymous if the graph contains for every vertex at least k−1 other vertices of the same degree. Complementing recent investigations on its computational complexity, we show that this problem is very hard when studied from the viewpoints of approximation as well as parameterized approximation. In particular, for the optimization variant where one wants to minimize the number of either edge or vertex deletions there is no factor-n1−ε approximation running in polynomial time unless P = NP, for any constant 0<ε≤1. For the variant where one wants to maximize k and the number s of either edge or vertex deletions is given, there is no factor-n1/2−ε approximation running in time f(s)⋅nO(1) unless W[1] = FPT, for any constant 0<ε≤1/2 and any function f. On the positive side, we classify the general decision version as fixed-parameter tractable with respect to the combined parameter solution size s and maximum degree.Mots-clés
Anonymization; Parameterized approximationPublications associées
Affichage des éléments liés par titre et auteur.
-
Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2014) Communication / Conférence
-
Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2014) Article accepté pour publication ou publié
-
Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2013) Communication / Conférence
-
Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2014) Article accepté pour publication ou publié
-
Bazgan, Cristina; Bredereck, Robert; Hartung, Sepp; Nichterlein, André; Woeginger, Gerhard (2016) Article accepté pour publication ou publié