Show simple item record

Parameterized Inapproximability of Degree Anonymization

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorBazgan, Cristina
hal.structure.identifierDepartment of Software Engineering and Theoretical Computer Science [SWT - TUB]
dc.contributor.authorNichterlein, André
dc.date.accessioned2017-01-11T10:53:32Z
dc.date.available2017-01-11T10:53:32Z
dc.date.issued2014
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16149
dc.descriptionin Springer series Lecture Notes in Computer Science, vol. 8894en
dc.language.isoenen
dc.subjectAnonymizationen
dc.subjectParameterized approximationen
dc.subject.ddc003en
dc.subject.classificationjelC.C4.C44en
dc.titleParameterized Inapproximability of Degree Anonymizationen
dc.typeCommunication / Conférence
dc.description.abstractenThe 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.citationpages75-84en
dc.relation.ispartoftitleParameterized and Exact Computationen
dc.relation.ispartofeditorCygan, Marek
dc.relation.ispartofeditorHeggernes, Pinar
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityChamen
dc.relation.ispartofdate2014-12
dc.relation.ispartofpages343en
dc.relation.ispartofurl10.1007/978-3-319-13524-3en
dc.contributor.countryeditoruniversityotherGERMANY
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-319-13523-6en
dc.relation.conftitle9th International Symposium, IPEC 2014en
dc.relation.confdate2014-09
dc.relation.confcityWroclawen
dc.relation.confcountryPolanden
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-319-13524-3_7en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2017-01-11T10:48:30Z
hal.identifierhal-01431827*
hal.version1*
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record