Finding large degree-anonymous subgraphs is hard

详细信息    查看全文

• 作者：Cristina Bazgan^a ; ¹ ; ^{bazgan@lamsade.dauphine.fr" class="auth_mail" title="E-mail the corresponding author} ; Robert Bredereck^b ; ² ; ^{robert.bredereck@tu-berlin.de" class="auth_mail" title="E-mail the corresponding author} ; Sepp Hartung^b ; ^{sepp.hartung@tu-berlin.de" class="auth_mail" title="E-mail the corresponding author} ; André ; Nichterlein^b ; ^{andre.nichterlein@tu-berlin.de" class="auth_mail" title="E-mail the corresponding author} ; Gerhard J. Woeginger^c ; ³ ; ^{gwoegi@win.tue.nl" class="auth_mail" title="E-mail the corresponding author}
• 关键词：NP-hardness ; Approximation-hardness ; W-hardness ; Graph algorithms
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：4 April 2016
• 年：2016
• 卷：622
• 期：Complete
• 页码：90-110
• 全文大小：918 K

文摘

A graph is said to be k-anonymous for an integer k  , if for every vertex in the graph there are at least class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516001146&_mathId=si1.gif&_user=111111111&_pii=S0304397516001146&_rdoc=1&_issn=03043975&md5=74d34fdf3dca9b3520b987ffa6142d4a" title="Click to view the MathML source">k−1class="mathContainer hidden">class="mathCode">$k-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 class="smallcaps">Anonym V-Del and class="smallcaps">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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516001146&_mathId=si141.gif&_user=111111111&_pii=S0304397516001146&_rdoc=1&_issn=03043975&md5=f6d19bc11821fc37dabb245f134e91d5" title="Click to view the MathML source">k=2class="mathContainer hidden">class="mathCode">$k=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 class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516001146&_mathId=si3.gif&_user=111111111&_pii=S0304397516001146&_rdoc=1&_issn=03043975&md5=95c8b2b07c8a76c34de492f5f991a9f6">class="imgLazyJSB inlineImage" height="13" width="23" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0304397516001146-si3.gif">class="mathContainer hidden">class="mathCode">$n^{\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$2$}\right.}$ (unless class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516001146&_mathId=si303.gif&_user=111111111&_pii=S0304397516001146&_rdoc=1&_issn=03043975&md5=e77d056314924fa7c0bd9021f0f9779f" title="Click to view the MathML source">P=NPclass="mathContainer hidden">class="mathCode">$\mathrm{P}=\mathrm{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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516001146&_mathId=si5.gif&_user=111111111&_pii=S0304397516001146&_rdoc=1&_issn=03043975&md5=dd8f1239c06621ed0fdb851977d7eb9a" title="Click to view the MathML source">f(s)⋅n^O(1)class="mathContainer hidden">class="mathCode">$f(s)\cdot n^{\mathcal{O}(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 Δ.