The complexity of finding a large subgraph under anonymity constraints

R. Bredereck, S. Hartung, A. Nichterlein, G.J. Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

10 Citations (Scopus)

Abstract

We define and analyze an anonymization problem in undirected graphs, which is motivated by certain privacy issues in social networks. The goal is to remove a small number of vertices from the graph such that in the resulting subgraph every occurring vertex degree occurs many times. We prove that the problem is NP-hard for trees, and also for a number of other highly structured graph classes. Furthermore we provide polynomial time algorithms for other graph classes (like threshold graphs), and thereby establish a sharp borderline between hard and easy cases of the problem. Finally we perform a parametrized analysis, and we concisely characterize combinations of natural parameters that allow FPT algorithms.
Original languageEnglish
Title of host publicationAlgorithms and Computation (24th International Symposium, ISAAC 2013, Hong Kong, December 16-18, 2013. Proceedings)
EditorsL. Cai, S.-W. Chen, T.-W. Lam
Place of PublicationBerlin
PublisherSpringer
Pages152-162
ISBN (Print)978-3-642-45029-7
DOIs
Publication statusPublished - 2013
Eventconference; 24th International Symposium on Algorithms and Computatio; 2013-12-16; 2013-12-18 -
Duration: 16 Dec 201318 Dec 2013

Publication series

NameLecture Notes in Computer Science
Volume8283
ISSN (Print)0302-9743

Conference

Conferenceconference; 24th International Symposium on Algorithms and Computatio; 2013-12-16; 2013-12-18
Period16/12/1318/12/13
Other24th International Symposium on Algorithms and Computatio

Fingerprint

Dive into the research topics of 'The complexity of finding a large subgraph under anonymity constraints'. Together they form a unique fingerprint.

Cite this