E192-02 - Forschungsbereich Databases and Artificial Intelligence
-
Journal:
Discrete Applied Mathematics
-
ISSN:
0166-218X
-
Date (published):
31-Dec-2018
-
Number of Pages:
6
-
Peer reviewed:
Yes
-
Keywords:
Applied Mathematics; Discrete Mathematics and Combinatorics; parameterized complexity; complexity analysis; treewidth; alliances in graphs; efensive alliance
en
Abstract:
The Defensive Alliance problem has been studied extensively during the last fifteen years, but the question whether it is FPT when parameterized by treewidth has still remained open. We show that this problem is W[1]-hard. This puts it among the few problems that are FPT when parameterized by solution size but not when parameterized by treewidth (unless FPT = W[1]).
en
Project title:
Extending the Answer-Set Programming Paradigm to Decomposed Problem Solving: P25607-N23 (Fonds zur Förderung der wissenschaftlichen Forschung (FWF)) START: Y 698-N23 (Fonds zur Förderung der wissenschaftlichen Forschung (FWF))
