• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

Finding large degree-anonymous subgraphs is hard

Bazgan, Cristina; Bredereck, Robert; Hartung, Sepp; Nichterlein, André; Woeginger, Gerhard (2016), Finding large degree-anonymous subgraphs is hard, Theoretical Computer Science, 622, p. 90-110. 10.1016/j.tcs.2016.02.004

Type
Article accepté pour publication ou publié
Date
2016
Journal name
Theoretical Computer Science
Volume
622
Publisher
Elsevier
Pages
90-110
Publication identifier
10.1016/j.tcs.2016.02.004
Metadata
Show full item record
Author(s)
Bazgan, Cristina
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Bredereck, Robert
Department of Software Engineering and Theoretical Computer Science [SWT - TUB]
Hartung, Sepp
Department of Software Engineering and Theoretical Computer Science [SWT - TUB]
Nichterlein, André
Department of Software Engineering and Theoretical Computer Science [SWT - TUB]
Woeginger, Gerhard
Department of mathematics and computing science [Eindhoven]
Abstract (EN)
A graph is said to be k-anonymous for an integer k, if for every vertex in the graph there are at least k−1k−1 other vertices with the same degree. We examine the computational complexity of making a given undirected graph k-anonymous either through at most s vertex deletions or through at most s edge deletions; the corresponding problem variants are denoted by Anonym V-Del and Anonym E-Del. We present a variety of hardness results, most of them hold for both problems. The two variants are intractable from the parameterized as well as from the approximation point of view. In particular, we show that both variants remain NP-hard on very restricted graph classes like trees even if k=2k=2. We further prove that both variants are W[1]-hard with respect to the combined parameter solutions size s and anonymity level k . With respect to approximability, we obtain hardness results showing that neither variant can be approximated in polynomial time within a factor better than View the MathML sourcen12 (unless P=NPP=NP). Furthermore, for the optimization variants where the solution size s is given and the task is to maximize the anonymity level k , this inapproximability result even holds if we allow a running time of f(s)⋅nO(1)f(s)⋅nO(1) for any computable function f. On the positive side, we classify both problem variants as fixed-parameter tractable with respect to the combined parameter solution size s and maximum degree Δ.
Subjects / Keywords
Complexity; NP-hardness; Approximation-hardness; W-hardness; Graph algorithms
JEL
C44 - Operations Research; Statistical Decision Theory

Related items

Showing items related by title and author.

  • Thumbnail
    A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths 
    Bazgan, Cristina; Nichterlein, André; Niedermeier, Rolf (2015) Communication / Conférence
  • Thumbnail
    A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths 
    Bazgan, Cristina; Fluschnik, Till; Nichterlein, André; Niedermeier, Rolf; Stahlberg, Maximilian (2019) Article accepté pour publication ou publié
  • Thumbnail
    Parameterized Inapproximability of Degree Anonymization 
    Bazgan, Cristina; Nichterlein, André (2014) Communication / Conférence
  • Thumbnail
    How to Get a Degree-Anonymous Graph Using Minimum Number of Edge Rotations 
    Bazgan, Cristina; Cazals, Pierre; Chlebíková, Janka (2020) Communication / Conférence
  • Thumbnail
    Parameterized Inapproximability of Target Set Selection and Generalizations 
    Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2014) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo