Parameterized Inapproximability of Degree Anonymization

摘要: The Degree Anonymity problem arises in the context of combinatorial graph anonymization. It asks, given a \(G\) and two integers \(k\) \(s\), whether can be made k-anonymous with at most \(s\) modifications. Here, is if contains for every vertex least \(k-1\) other vertices same degree. Complementing recent investigations on its computational complexity, we show that this very hard when studied from viewpoints approximation as well parameterized approximation. In particular, optimization variant where one wants to minimize number either edge or deletions there no factor-\(n^{1-\varepsilon }\) running polynomial time unless P = NP, any constant \(0 < \varepsilon \le 1\). For maximize given, factor-\(n^{{1}/{2}-\varepsilon \(f(s) \cdot n^{O(1)}\) W[1] FPT, {1}/{2}\) function \(f\). On positive side, classify general decision version fixed-parameter tractable respect combined parameter solution size maximum