Complexity of Optimally Defending and Attacking a Network

AAAI 2018 pp. 8026-8027

doi:10.1609/AAAI.V32I1.11354 /aaai/2018/najeebullah2018aaai-complexity/

Abstract

We consider single-agent, two-agent turn-taking and cooperative security games with Inverse Geodesic Length (IGL) as utility metric. We focus on the single-agent vertex deletion problem corresponding to IGL called MinIGL. Specifically, given a graph G, a budget k and a target inverse geodesic length T, does there exist a subset of vertices S of size k such that by deleting S the graph induced on the remaining vertices in G has IGL at most T. We cite our recently published work to report the results on the computational and parameterized complexity of MinIGL. Furthermore, we briefly state the problems we are interested to study in future.

PDF AAAI Semantic Scholar

Cite

Text

Najeebullah. "Complexity of Optimally Defending and Attacking a Network." AAAI Conference on Artificial Intelligence, 2018. doi:10.1609/AAAI.V32I1.11354

Markdown

[Najeebullah. "Complexity of Optimally Defending and Attacking a Network." AAAI Conference on Artificial Intelligence, 2018.](https://mlanthology.org/aaai/2018/najeebullah2018aaai-complexity/) doi:10.1609/AAAI.V32I1.11354

BibTeX

@inproceedings{najeebullah2018aaai-complexity,
  title     = {{Complexity of Optimally Defending and Attacking a Network}},
  author    = {Najeebullah, Kamran},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2018},
  pages     = {8026-8027},
  doi       = {10.1609/AAAI.V32I1.11354},
  url       = {https://mlanthology.org/aaai/2018/najeebullah2018aaai-complexity/}
}