Parameterized Analysis in Artificial Intelligence (Research Project)

• Funding organization: The Austrian Science Funds, FWF
• Project number: Y 1329 START-Programm (ParAI)

Project Team

Picture credits: Soeren Nickel, 2020

Research Statement

Parameterized complexity theory is a well-established paradigm used for the fine-grained analysis of computational problems. Such analysis can provide efficient algorithms for these problems by exploiting subtle structural properties of relevant inputs, as well as powerful lower bounds that rule out efficient algorithms even for severely restricted instances. Parameterized complexity analysis has found great success across numerous fields of computer science, with notable examples including graph algorithms, computational geometry, database theory, computational logic and constraint satisfaction. In the highly prominent fields of artificial intelligence (AI) and machine learning (ML) – areas which have become an ubiquitous part of today's society – we see a distinct lack of foundational research targeting the fine-grained, parameterized complexity of fundamental problems. The goal of this project is to change this.

A Parameterized Toolbox for Problems in AI and ML

One main objective of this project is the development of new innovative tools and machinery that allows us to apply the parameterized complexity framework in this setting. Indeed, most of the existing tools developed in parameterized complexity theory are designed to work in the setting of discrete problems on graphs. On the other hand, many problems of interest in AI and ML do not admit straightforward graph representations and/or contain non-discrete components. The development of the required tools will then go hand in hand with obtaining new algorithms and matching lower bounds for the studied problems.

Publications

16 results

2022
[16]	An Efficient Algorithm for Counting Markov Equivalent DAGs Robert Ganian, Thekla Hamm, Topi Talvitie Artificial Intelligence, 2022. Note: to appear [bibtex]
[15]	Sum-of-Products with Default Values: Algorithms and Complexity Results Robert Ganian, Eun Jung Kim, Friedrich Slivovsky, Stefan Szeider Journal Artificial Intelligence Research, 2022. Note: to appear [bibtex]
[14]	On Covering Segments with Unit Intervals Dan Bergren, Eduard Eiben, Robert Ganian, Iyad Kanj SIAM J. Discrete Math., 2022. Note: to appear [bibtex]
[13]	Hedonic Diversity Games: A Complexity Picture with More than Two Colors Robert Ganian, Thekla Hamm, Dušan Knop, Šimon Schierreich, Ondrej Suchý Proceeding of AAAI-22, the Thirty-Sixth AAAI Conference on Artificial Intelligence, 2022, AAAI Press. Note: to appear [bibtex]
[12]	A Unifying Framework for Characterizing and Computing Width Measures Eduard Eiben, Robert Ganian, Thekla Hamm, Lars Jaffke, O-joung Kwon 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Note: to appear [bibtex] [pdf]
2021
[11]	Measuring what matters: A hybrid approach to dynamic programming with treewidth Eduard Eiben, Robert Ganian, Thekla Hamm, O-joung Kwon J. Comput. Syst. Sci., volume 121, pages 57–75, 2021. [bibtex] [pdf]
[10]	New Width Parameters for SAT and Sharp-SAT Robert Ganian, Stefan Szeider Artificial Intelligence, volume 295, pages 103460, 2021. [bibtex] [pdf] [doi]
[9]	On Structural Parameterizations of the Edge Disjoint Paths Problem Robert Ganian, Sebastian Ordyniak, M. S. Ramanujan Algorithmica, volume 83, number 6, pages 1605–1637, 2021. [bibtex] [pdf]
[8]	On Strict (Outer-)Confluent Graphs Henry Förster, Robert Ganian, Fabian Klute, Martin Nöllenburg J. Graph Algorithms Appl., 2021. Note: to appear [bibtex] [pdf]
[7]	The complexity landscape of deciompositional parameters for ILP: Programs with Few Global Variables and Constraints Pavel Dvorák, Eduard Eiben, Robert Ganian, Dušan Knop, Sebastian Ordyniak Artificial Intelligence, 2021. Note: to appear [bibtex]
[6]	The Complexity of Bayesian Network Learning: Revisiting the Superstructure Robert Ganian, Viktoriia Korchemna Proceedings of NeurIPS 2021, the Thirty-fifth Conference on Neural Information Processing Systems, 2021. Note: to appear [bibtex]
[5]	The Complexity of Object Association in Multiple Object Tracking Robert Ganian, Thekla Hamm, Sebastian Ordyniak Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Virtual Event, February 2-9, 2021, pages 1388–1396, 2021, AAAI Press. [bibtex] [pdf]
[4]	Crossing-Optimal Extension of Simple Drawings Robert Ganian, Thekla Hamm, Fabian Klute, Irene Parada, Birgit Vogtenhuber 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference) (Nikhil Bansal, Emanuela Merelli, James Worrell, eds.), volume 198 of LIPIcs, pages 72:1–72:17, 2021, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. [bibtex] [pdf]
[3]	The Parameterized Complexity of Clustering Incomplete Data Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak, Stefan Szeider Proceeding of AAAI-21, the Thirty-Fifth AAAI Conference on Artificial Intelligence, pages 7296–7304, 2021, AAAI Press. [bibtex] [pdf]
[2]	The Parameterized Complexity of Connected Fair Division Argyrios Deligkas, Eduard Eiben, Robert Ganian, Thekla Hamm, Sebastian Ordyniak Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021 (Zhi-Hua Zhou, ed.), pages 139–145, 2021, ijcai.org. [bibtex] [pdf]
[1]	Graphs with two moplexes are more than perfect Clement Dallard, Robert Ganian, Meike Hatzel, Matjaz Krnc, Martin Milanic Proceedings of the 11th Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS 2021), 2021, Elsevier. Note: to appear [bibtex]