dc.contributor.author Bazgan, Cristina dc.contributor.author Nichterlein, André dc.date.accessioned 2017-01-11T10:53:32Z dc.date.available 2017-01-11T10:53:32Z dc.date.issued 2014 dc.identifier.uri https://basepub.dauphine.fr/handle/123456789/16149 dc.description in Springer series Lecture Notes in Computer Science, vol. 8894 en dc.language.iso en en dc.subject Anonymization en dc.subject Parameterized approximation en dc.subject.ddc 003 en dc.subject.classificationjel C.C4.C44 en dc.title Parameterized Inapproximability of Degree Anonymization en dc.type Communication / Conférence dc.description.abstracten 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. en dc.identifier.citationpages 75-84 en dc.relation.ispartoftitle Parameterized and Exact Computation en dc.relation.ispartofeditor Cygan, Marek dc.relation.ispartofeditor Heggernes, Pinar dc.relation.ispartofpublname Springer en dc.relation.ispartofpublcity Cham en dc.relation.ispartofdate 2014-12 dc.relation.ispartofpages 343 en dc.relation.ispartofurl 10.1007/978-3-319-13524-3 en dc.contributor.countryeditoruniversityother GERMANY dc.subject.ddclabel Recherche opérationnelle en dc.relation.ispartofisbn 978-3-319-13523-6 en dc.relation.conftitle 9th International Symposium, IPEC 2014 en dc.relation.confdate 2014-09 dc.relation.confcity Wroclaw en dc.relation.confcountry Poland en dc.relation.forthcoming non en dc.identifier.doi 10.1007/978-3-319-13524-3_7 en dc.description.ssrncandidate non en dc.description.halcandidate oui en dc.description.readership recherche en dc.description.audience International en dc.relation.Isversionofjnlpeerreviewed non en dc.relation.Isversionofjnlpeerreviewed non en dc.date.updated 2017-01-11T10:48:30Z hal.person.labIds 989 hal.person.labIds 84325 hal.identifier hal-01431827 *
﻿

## Files in this item

FilesSizeFormatView

There are no files associated with this item.