The Parameterized Complexity of Network Microaggregation
Abstract
Microaggregation is a classical statistical disclosure control technique which requires the input data to be partitioned into clusters while adhering to specified size constraints. We provide novel exact algorithms and lower bounds for the task of microaggregating a given network while considering both unrestricted and connected clusterings, and analyze these from the perspective of the parameterized complexity paradigm. Altogether, our results assemble a complete complexity-theoretic picture for the network microaggregation problem with respect to the most natural parameterizations of the problem, including input-specified parameters capturing the size and homogeneity of the clusters as well as the treewidth and vertex cover number of the network.
Cite
Text
Blazej et al. "The Parameterized Complexity of Network Microaggregation." AAAI Conference on Artificial Intelligence, 2023. doi:10.1609/AAAI.V37I5.25771Markdown
[Blazej et al. "The Parameterized Complexity of Network Microaggregation." AAAI Conference on Artificial Intelligence, 2023.](https://mlanthology.org/aaai/2023/blazej2023aaai-parameterized/) doi:10.1609/AAAI.V37I5.25771BibTeX
@inproceedings{blazej2023aaai-parameterized,
title = {{The Parameterized Complexity of Network Microaggregation}},
author = {Blazej, Václav and Ganian, Robert and Knop, Dusan and Pokorný, Jan and Schierreich, Simon and Simonov, Kirill},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2023},
pages = {6262-6270},
doi = {10.1609/AAAI.V37I5.25771},
url = {https://mlanthology.org/aaai/2023/blazej2023aaai-parameterized/}
}