• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Aide
  • Connexion
  • Langue 
    • Français
    • English
Consulter le document 
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
JavaScript is disabled for your browser. Some features of this site may not work without it.

Afficher

Toute la baseCentres de recherche & CollectionsAnnée de publicationAuteurTitreTypeCette collectionAnnée de publicationAuteurTitreType

Mon compte

Connexion

Enregistrement

Statistiques

Documents les plus consultésStatistiques par paysAuteurs les plus consultés
Thumbnail - Request a copy

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érence
Date
2014
Titre du colloque
9th International Symposium, IPEC 2014
Date du colloque
2014-09
Ville du colloque
Wroclaw
Pays du colloque
Poland
Titre de l'ouvrage
Parameterized and Exact Computation
Auteurs de l’ouvrage
Cygan, Marek; Heggernes, Pinar
Éditeur
Springer
Ville d’édition
Cham
Isbn
978-3-319-13523-6
Nombre de pages
343
Pages
75-84
Identifiant publication
10.1007/978-3-319-13524-3_7
Métadonnées
Afficher la notice complète
Auteur(s)
Bazgan, Cristina
Laboratoire 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 approximation
JEL
C44 - Operations Research; Statistical Decision Theory

Publications associées

Affichage des éléments liés par titre et auteur.

  • Vignette de prévisualisation
    Parameterized Inapproximability of Target Set Selection and Generalizations 
    Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2014) Communication / Conférence
  • Vignette de prévisualisation
    Parameterized Inapproximability of Target Set Selection and Generalizations 
    Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2014) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    Parameterized Approximability of Maximizing the Spread of Influence in Networks 
    Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2013) Communication / Conférence
  • Vignette de prévisualisation
    Parameterized approximability of maximizing the spread of influence in networks 
    Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2014) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    Finding large degree-anonymous subgraphs is hard 
    Bazgan, Cristina; Bredereck, Robert; Hartung, Sepp; Nichterlein, André; Woeginger, Gerhard (2016) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Tél. : 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo