The Parameterized Complexity of Network Microaggregation
Authors: Václav Blažej, Robert Ganian, Dušan Knop, Jan Pokorný, Šimon Schierreich, Kirill Simonov
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. We initiate the comprehensive study of the complexity of both NMA and CNMA. While both problems are easily seen to be NP-complete in their full generality, in many scenarios of interest the instances we deal with have specific structural properties and the natural question that arises is whether one can exploit such properties to obtain exact algorithms with good runtime guarantees. To provide a comprehensive answer to this question, we turn to the parameterized complexity paradigm (Downey and Fellows 2013; Cygan et al. 2015). |
| Researcher Affiliation | Academia | 1Faculty of Information Technology, Czech Technical University in Prague, Prague, Czechia 2Algorithms and Complexity Group, Technische Universit at Wien, Vienna, Austria 3Hasso Plattner Institute, University of Potsdam, Postdam, Germany |
| Pseudocode | No | The paper describes algorithms and proof sketches but does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide an explicit statement about releasing source code for the described methodology or a direct link to a code repository. |
| Open Datasets | No | The paper is theoretical, focusing on algorithms and complexity analysis for graph problems. It does not mention using any datasets for training or provide access information for a publicly available dataset. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical validation with datasets, hence no information regarding training/test/validation dataset splits is provided. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithmic complexity, not empirical experiments. Therefore, it does not specify any hardware used for running experiments. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithmic complexity, not practical implementation. Therefore, it does not provide specific ancillary software details with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithmic complexity. It does not describe empirical experiments, and thus no experimental setup details like hyperparameters or system-level training settings are provided. |