Optimal Surveillance of Covert Networks by Minimizing Inverse Geodesic Length
Authors: Serge Gaspers, Kamran Najeebullah533-540
AAAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We perform an extensive complexity analysis of the problem. We show that MINIGL-ED is NP-complete and cannot be solved in subexponential time even when restricted to bipartite and split graphs under standard assumptions. In terms of parameterized complexity we show that the problem is W[1]-hard with respect to parameter tree-width. On the positive side we provide FPT algorithms for MINIGL-ED with respect to parameter target inverse geodesic length T and vertex cover τ. We also provide FPT algorithms parameterized by twin cover number and neighborhood diversity when combined with the deletion budget k. |
| Researcher Affiliation | Academia | Serge Gaspers, Kamran Najeebullah UNSW Sydney, Australia, and Data61, CSIRO, Australia sergeg@cse.unsw.edu.au, kamran.najeebullah@data61.csiro.au |
| Pseudocode | Yes | Algorithm 1: MINIGL-ED parameterized Γ + k. |
| Open Source Code | No | The paper is theoretical and focuses on complexity analysis and algorithm design. It does not mention providing open-source code for the described algorithms. |
| Open Datasets | No | The paper references "Covert networks (UCINET Software 2017)" in Table 1, stating that "Our choice of parameters is motivated by real-word datasets (see Table 1)". This indicates the datasets informed theoretical parameter choices, not that they were used for empirical training in this paper. No access information is provided for data used in experiments, as no experiments were conducted. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments, therefore, it does not mention training, validation, or test dataset splits. |
| Hardware Specification | No | The paper does not report on experiments or empirical evaluations; thus, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper focuses on theoretical complexity and algorithm design and does not describe an implementation or empirical evaluation, thus no specific software dependencies with version numbers are mentioned. |
| Experiment Setup | No | The paper is theoretical and does not describe experiments; therefore, it does not provide details about an experimental setup, hyperparameters, or training settings. |