Finding large degree-anonymous subgraphs is hard
| Autor: | Cristina Bazgan, Robert Bredereck, Sepp Hartung, Gerhard J. Woeginger, André Nichterlein |
|---|---|
| Přispěvatelé: | Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Department of Software Engineering and Theoretical Computer Science (SWT - TUB), Technische Universität Berlin (TU), Department of mathematics and computing science [Eindhoven], Eindhoven University of Technology [Eindhoven] (TU/e), Discrete Mathematics |
| Rok vydání: | 2016 |
| Předmět: |
Discrete mathematics
General Computer Science Degree (graph theory) Computational complexity theory Parameterized complexity Complexity 0102 computer and information sciences 02 engineering and technology W-hardness 01 natural sciences Theoretical Computer Science Vertex (geometry) Running time Combinatorics Computable function 010201 computation theory & mathematics NP-hardness 0202 electrical engineering electronic engineering information engineering [INFO]Computer Science [cs] 020201 artificial intelligence & image processing Graph algorithms Approximation-hardness Time complexity Mathematics Anonymity |
| Zdroj: | Theoretical Computer Science Theoretical Computer Science, Elsevier, 2016, 622, ⟨10.1016/j.tcs.2016.02.004⟩ Theoretical Computer Science, 622, 90-110. Elsevier |
| ISSN: | 0304-3975 1879-2294 |
| DOI: | 10.1016/j.tcs.2016.02.004 |
| Popis: | International audience; 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 Δ. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect