The Parameterized Complexity of Finding Concise Local Explanations
Authors: Sebastian Ordyniak, Giacomo Paesani, Stefan Szeider
IJCAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we provide the first study of the computation complexity of computing small anchors. We show that the exact computation of small anchors is NP-hard. Based on this insight, we roll out a systematic investigation of the parameterized complexity of this problem by taking various properties of the sought-for anchor or structural properties of the input data in terms of problem parameters into account. Our results draw a detailed complexity-landscape of the problem (see Figure 1), indicating regions where the problem is 1. fixed-parameter tractable (i.e., solvable in uniform polynomial time for fixed parameter values), 2. XP-tractable (i.e., solvable in nonuniform-polynomial time for fixed parameter values), and 3. para NP-hard (remains NP-hard even for fixed parameter values). |
| Researcher Affiliation | Academia | Sebastian Ordyniak1 , Giacomo Paesani1 and Stefan Szeider2 1University of Leeds, UK 2Algorithms and Complexity Group, TU Wien, Vienna, Austria {s.ordyniak, g.paesani}@leeds.ac.uk, sz@ac.tuwien.ac.at |
| Pseudocode | No | The paper describes algorithms (e.g., dynamic programming for rank-width), but it does not include any clearly labeled 'Pseudocode' or 'Algorithm' blocks with structured steps. |
| Open Source Code | No | The paper does not provide any statement or link indicating the availability of open-source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not describe experiments involving training on datasets. The example data in Figure 3 is illustrative, not a dataset for training. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments requiring train/validation/test dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not report on experiments, thus no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and focuses on computational complexity proofs and algorithm design, not on empirical implementation. Therefore, it does not list specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not include details about an experimental setup, such as hyperparameters or training settings. |