The complexity of degree anonymization by vertex addition. (English) Zbl 1332.68164
Summary: Motivated by applications in privacy-preserving data publishing, we study the problem of making an undirected graph \(k\)-anonymous by adding few vertices (together with some incident edges). That is, after adding these “dummy vertices”, for every vertex degree \(d\) appearing in the resulting graph, there shall be at least \(k\) vertices with degree \(d\). We explore three variants of vertex addition (justified by real-world considerations) and study their (parameterized) computational complexity. We derive mostly intractability results, even for very restricted cases (including trees and bounded-degree graphs) but also obtain some encouraging fixed-parameter tractability results.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C76 | Graph operations (line graphs, products, etc.) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
Keywords:
graph modification; degree-constrained editing; NP-hardness; parameterized complexity; fixed-parameter tractability; kernelizationReferences:
| [1] | Alon, N.; Gutin, G.; Kim, E. J.; Szeider, S.; Yeo, A., Solving MAX-\(r\)-SAT above a tight lower bound, Algorithmica, 61, 3, 638-655 (2011) · Zbl 1242.68118 |
| [2] | Bazgan, C.; Nichterlein, A., Parameterized inapproximability of degree anonymization, (Proceedings of the 9th International Symposium on Parameterized and Exact Computation. Proceedings of the 9th International Symposium on Parameterized and Exact Computation, IPEC ’14. Proceedings of the 9th International Symposium on Parameterized and Exact Computation. Proceedings of the 9th International Symposium on Parameterized and Exact Computation, IPEC ’14, LNCS, vol. 8894 (2014), Springer) · Zbl 1456.68062 |
| [3] | Bilge, L.; Strufe, T.; Balzarotti, D.; Kirda, E., All your contacts are belong to us: automated identity theft attacks on social networks, (Proceedings of the 18th International Conference on World Wide Web. Proceedings of the 18th International Conference on World Wide Web, WWW ’09 (2009), ACM), 551-560 |
| [4] | Bredereck, R.; Hartung, S.; Nichterlein, A.; Woeginger, G. J., The complexity of finding a large subgraph under anonymity constraints, (Proceedings of the 24th International Symposium on Algorithms and Computation. Proceedings of the 24th International Symposium on Algorithms and Computation, ISAAC ’13. Proceedings of the 24th International Symposium on Algorithms and Computation. Proceedings of the 24th International Symposium on Algorithms and Computation, ISAAC ’13, LNCS, vol. 8283 (2013), Springer), 152-162 · Zbl 1329.05276 |
| [5] | Bredereck, R.; Froese, V.; Hartung, S.; Nichterlein, A.; Niedermeier, R.; Talmon, N., The complexity of degree anonymization by vertex addition, (Proceedings of the 10th International Conference on Algorithmic Aspects in Information and Management. Proceedings of the 10th International Conference on Algorithmic Aspects in Information and Management, AAIM ’14. Proceedings of the 10th International Conference on Algorithmic Aspects in Information and Management. Proceedings of the 10th International Conference on Algorithmic Aspects in Information and Management, AAIM ’14, Lecture Notes in Computer Science, vol. 8546 (2014), Springer), 44-55 · Zbl 1445.68153 |
| [6] | Cai, L.; Chen, J.; Downey, R. G.; Fellows, M. R., Advice classes of parameterized tractability, Ann. Pure Appl. Logic, 84, 1, 119-138 (1997) · Zbl 0873.68071 |
| [7] | Casas-Roma, J.; Herrera-Joancomartí, J.; Torra, V., An algorithm for \(k\)-degree anonymity on large networks, (Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM ’13 (2013), ACM Press), 671-675 |
| [8] | Chester, S.; Kapron, B. M.; Ramesh, G.; Srivastava, G.; Thomo, A.; Venkatesh, S., Why Waldo befriended the dummy? \(k\)-Anonymization of social networks with pseudo-nodes, Soc. Netw. Anal. Min., 3, 3, 381-399 (2013) |
| [9] | Chester, S.; Kapron, B. M.; Srivastava, G.; Venkatesh, S., Complexity of social network anonymization, Soc. Netw. Anal. Min., 3, 2, 151-166 (2013) |
| [10] | Clarkson, K. L.; Liu, K.; Terzi, E., Towards identity anonymization in social networks, (Link Mining: Models, Algorithms, and Applications (2010), Springer), 359-385 |
| [11] | Downey, R. G.; Fellows, M. R., Fundamentals of Parameterized Complexity (2013), Springer · Zbl 1358.68006 |
| [12] | Elkind, E.; Faliszewski, P.; Slinko, A., Clone structures in voters’ preferences, (Proceedings of the 13th ACM Conference on Electronic Commerce. Proceedings of the 13th ACM Conference on Electronic Commerce, EC ’12 (2012), ACM), 496-513 |
| [13] | Erdős, P.; Kelly, P., The minimal regular graph containing a given graph, Amer. Math. Monthly, 70, 1074-1075 (1963) |
| [14] | Erdős, P.; Gallai, T., Graphs with prescribed degrees of vertices, Mat. Lapok (N.S.), 11, 264-274 (1960), (in Hungarian) · Zbl 0103.39701 |
| [15] | Fellows, M. R.; Jansen, B. M.P.; Rosamond, F. A., Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity, European J. Combin., 34, 3, 541-566 (2013) · Zbl 1448.68465 |
| [16] | Flum, J.; Grohe, M., Parameterized Complexity Theory (2006), Springer · Zbl 1143.68016 |
| [17] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman · Zbl 0411.68039 |
| [18] | Guo, J.; Niedermeier, R., Invitation to data reduction and problem kernelization, SIGACT News, 38, 1, 31-45 (2007) |
| [19] | Hakimi, S. L., On realizability of a set of integers as degrees of the vertices of a linear graph, I, J. Soc. Ind. Appl. Math., 10, 3, 496-506 (1962) · Zbl 0109.16501 |
| [20] | Hartung, S.; Talmon, N., The complexity of degree anonymization by graph contractions, (Theory and Applications of Models of Computation. Theory and Applications of Models of Computation, LNCS, vol. 9076 (2015), Springer), 260-271 · Zbl 1459.68158 |
| [21] | Hartung, S.; Hoffmann, C.; Nichterlein, A., Improved upper and lower bound heuristics for degree anonymization in social networks, (Proceedings of the 13th International Symposium on Experimental Algorithms. Proceedings of the 13th International Symposium on Experimental Algorithms, SEA ’14. Proceedings of the 13th International Symposium on Experimental Algorithms. Proceedings of the 13th International Symposium on Experimental Algorithms, SEA ’14, LNCS, vol. 8504 (2014), Springer), 376-387 |
| [22] | Hartung, S.; Nichterlein, A.; Niedermeier, R.; Suchỳ, O., A refined complexity analysis of degree anonymization in graphs, Inform. and Comput., 243, 249-262 (2014) · Zbl 1327.68134 |
| [23] | Havel, V., A remark on the existence of finite graphs, Čas. Pěst. Mat., 80, 477-480, 1253 (1955), (in Czech) · Zbl 0068.37202 |
| [24] | Kratsch, S., Recent developments in kernelization: a survey, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 113, 58-97 (2014) · Zbl 1409.68144 |
| [25] | Lenstra, H. W., Integer programming with a fixed number of variables, Math. Oper. Res., 8, 538-548 (1983) · Zbl 0524.90067 |
| [26] | Liu, K.; Terzi, E., Towards identity anonymization on graphs, (ACM SIGMOD International Conference on Management of Data. ACM SIGMOD International Conference on Management of Data, SIGMOD ’08 (2008), ACM), 93-106 |
| [27] | Lu, X.; Song, Y.; Bressan, S., Fast identity anonymization on graphs, (Proceedings of Database and Expert Systems Applications. Proceedings of Database and Expert Systems Applications, DEXA ’12. Proceedings of Database and Expert Systems Applications. Proceedings of Database and Expert Systems Applications, DEXA ’12, LNCS, vol. 7446 (2012), Springer), 281-295 |
| [28] | Lueker, G. S., Two NP-complete problems in nonnegative integer programming (1975), Computer Science Laboratory, Princeton University, technical report |
| [29] | Niedermeier, R., Invitation to Fixed-Parameter Algorithms (2006), Oxford University Press · Zbl 1095.68038 |
| [30] | Niedermeier, R., Reflections on multivariate algorithmics and problem parameterization, (Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science. Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, STACS ’10. Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science. Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, STACS ’10, LIPIcs. Leibniz Int. Proc. Inform., vol. 5 (2010), Schloss Dagstuhl-Leibniz-Zentrum für Informatik), 17-32 · Zbl 1230.68096 |
| [31] | Zhou, B.; Pei, J., The \(k\)-anonymity and \(l\)-diversity approaches for privacy preservation in social networks against neighborhood attacks, Knowl. Inf. Syst., 28, 1, 47-77 (2011) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
