Finding large degreeanonymous subgraphs is hard
Bazgan, Cristina; Bredereck, Robert; Hartung, Sepp; Nichterlein, André; Woeginger, Gerhard (2016), Finding large degreeanonymous subgraphs is hard, Theoretical Computer Science, 622, p. 90110. 10.1016/j.tcs.2016.02.004
Type
Article accepté pour publication ou publiéDate
2016Journal name
Theoretical Computer ScienceVolume
622Publisher
Elsevier
Pages
90110
Publication identifier
Metadata
Show full item recordAuthor(s)
Bazgan, CristinaLaboratoire 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 kanonymous 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 kanonymous either through at most s vertex deletions or through at most s edge deletions; the corresponding problem variants are denoted by Anonym VDel and Anonym EDel. 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 NPhard 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 fixedparameter tractable with respect to the combined parameter solution size s and maximum degree Δ.Subjects / Keywords
Complexity; NPhardness; Approximationhardness; Whardness; Graph algorithmsRelated items
Showing items related by title and author.

Bazgan, Cristina; Nichterlein, André; Niedermeier, Rolf (2015) Communication / Conférence

Bazgan, Cristina; Fluschnik, Till; Nichterlein, André; Niedermeier, Rolf; Stahlberg, Maximilian (2019) Article accepté pour publication ou publié

Bazgan, Cristina; Nichterlein, André (2014) Communication / Conférence

Bazgan, Cristina; Cazals, Pierre; Chlebíková, Janka (2020) Communication / Conférence

Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2014) Communication / Conférence