Algorithms and Complexity Group
  • People
  • Research
  • Courses
  • Talks
  • Jobs
  • Contact

Parameterized Analysis in Artificial Intelligence (Research Project)

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

Project Team

Robert Ganian (Principal Investigator)
Cornelius Brand (Research Assistant – Postdoc)
Thekla Hamm (Research Assistant – Doctoral Candidate)
Viktoriia Korchemna (Research Assistant – Doctoral Candidate)

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 six-year 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

2022

24 results
2022
[24]Parameterized Algorithms for Queue Layouts
Sujoy Bhore, Robert Ganian, Fabrizio Montecchiani, Martin Nöllenburg
J. Graph Algorithms Appl., 2022.
Note: to appear
[bibtex]
[23]An efficient algorithm for counting Markov equivalent DAGs
Robert Ganian, Thekla Hamm, Topi Talvitie
Artificial Intelligence, volume 304, pages 103648, 2022.
[bibtex] [pdf] [doi]
[22]Threshold Treewidth and Hypertree Width
Robert Ganian, Andre Schidler, Manuel Sorge, Stefan Szeider
Journal of Artificial Intelligence Research, volume 74, pages 1687–1713, 2022.
[bibtex] [pdf] [doi]
[21]Group Activity Selection with Few Agent Types
Robert Ganian, Sebastian Ordyniak, C. S. Rahul
Algorithmica, 2022.
Note: to appear
[bibtex]
[20]Algorithmic Applications of Tree-Cut Width
Robert Ganian, Eun Jung Kim, Stefan Szeider
SIAM J. Discrete Math., volume 36, number 4, pages 2635–2666, 2022.
[bibtex] [pdf] [doi]
[19]Sum-of-Products with Default Values: Algorithms and Complexity Results
Robert Ganian, Eun Jung Kim, Friedrich Slivovsky, Stefan Szeider
Journal of Artificial Intelligence Research, volume 33, pages 535–552, 2022.
[bibtex] [pdf]
[18]On Covering Segments with Unit Intervals
Dan Bergren, Eduard Eiben, Robert Ganian, Iyad Kanj
SIAM J. Discret. Math., volume 36, number 2, pages 1200–1230, 2022.
[bibtex] [pdf] [doi]
[17]Fine-grained Complexity of Partial Minimum Satisfiability
Ivan Bliznets, Danil Sagunov, Kirill Simonov
Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22 (Lud De Raedt, ed.), pages 1774–1780, 7 2022, International Joint Conferences on Artificial Intelligence Organization.
Note: Main Track
[bibtex] [pdf] [doi]
[16]The Complexity of Temporal Vertex Cover in Small-Degree Graphs
Thekla Hamm, Nina Klobas, George B. Mertzios, Paul G. Spirakis
Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, pages 10193–10201, 2022, AAAI Press.
[bibtex] [pdf]
[15]Parameterised Partially-Predrawn Crossing Number
Thekla Hamm, Petr Hlinený
38th International Symposium on Computational Geometry, SoCG 2022, June 7-10, 2022, Berlin, Germany (Xavier Goaoc, Michael Kerber, eds.), volume 224 of LIPIcs, pages 46:1–46:15, 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[14]Hedonic Diversity Games: A Complexity Picture with More than Two Colors
Robert Ganian, Thekla Hamm, Dusan Knop, Simon Schierreich, Ondrej Suchý
Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, pages 5034–5042, 2022, AAAI Press.
[bibtex] [pdf]
[13]The Complexity of k-Means Clustering when Little is Known
Robert Ganian, Thekla Hamm, Viktoriia Korchemna, Karolina Okrasa, Kirill Simonov
International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA (Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, Sivan Sabato, eds.), volume 162 of Proceedings of Machine Learning Research, pages 6960–6987, 2022, PMLR.
[bibtex] [pdf]
[12]The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width
Robert Ganian, Thekla Hamm, Viktoriia Korchemna, Karolina Okrasa, Kirill Simonov
49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France (Mikolaj Bojanczyk, Emanuela Merelli, David P. Woodruff, eds.), volume 229 of LIPIcs, pages 66:1–66:20, 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[11]Weighted Model Counting with Twin-Width
Robert Ganian, Filip Pokrývka, Andre Schidler, Kirill Simonov, Stefan Szeider
25th International Conference on Theory and Applications of Satisfiability Testing, SAT 2022, August 2-5, 2022, Haifa, Israel (Kuldeep S. Meel, Ofer Strichman, eds.), volume 236 of LIPIcs, pages 15:1–15:17, 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[10]Longest Cycle above Erd\Hos–Gallai Bound
Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, Kirill Simonov
30th Annual European Symposium on Algorithms (ESA 2022), 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
Note: to appear
[bibtex]
[9]Detours in Directed Graphs
Fedor V. Fomin, Petr A. Golovach, William Lochet, Danil Sagunov, Kirill Simonov, Saket Saurabh
39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) (Petra Berenbrink, Benjamin Monmege, eds.), volume 219 of Leibniz International Proceedings in Informatics (LIPIcs), pages 29:1–29:16, 2022, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[8]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.
[bibtex] [pdf]
[7]Finding a Cluster in Incomplete Data
Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak, Stefan Szeider
30th Annual European Symposium on Algorithms (ESA 2022) (Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, Grzegorz Herman, eds.), volume 244 of Leibniz International Proceedings in Informatics (LIPIcs), pages 47:1–47:14, 2022, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[6]The Complexity of Envy-Free Graph Cutting
Argyrios Deligkas, Eduard Eiben, Robert Ganian, Thekla Hamm, Sebastian Ordyniak
Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022 (Luc De Raedt, ed.), pages 237–243, 2022, ijcai.org.
[bibtex] [pdf] [doi]
[5]Testing Upward Planarity of Partial 2-Trees
Steven Chaplick, Emilio Di Giacomo, Fabrizio Frati, Robert Ganian, Chrysanthi N. Raftopoulou, Kirill Simonov
30th International Symposium on Graph Drawing and Network Visualization, GD 2022, September 13-16, 2022, Tokyo, Japan, 2022, Springer Verlag.
Note: to appear
[bibtex]
[4]Parameterized Algorithms for Upward Planarity
Steven Chaplick, Emilio Di Giacomo, Fabrizio Frati, Robert Ganian, Chrysanthi N. Raftopoulou, Kirill Simonov
38th International Symposium on Computational Geometry, SoCG 2022, June 7-10, 2022, Berlin, Germany (Xavier Goaoc, Michael Kerber, eds.), volume 224 of LIPIcs, pages 26:1–26:16, 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[3]FPT Approximation for Fair Minimum-Load Clustering
Sayan Bandyapadhyay, Fedor V. Fomin, Petr A. Golovach, Nidhi Purohit, Kirill Simonov
17th International Symposium on Parameterized and Exact Computation (IPEC 2022), 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
Note: to appear
[bibtex]
[2]Edge-Cut Width: An Algorithmically Driven Analogue of Treewidth Based on Edge Cuts
Cornelius Brand, Esra Ceylan, Robert Ganian, Christian Hatschka, Viktoriia Korchemna
Graph-Theoretic Concepts in Computer Science - 48th International Workshop, WG 2022, Tübingen, Germany, June 22-24, 2022, Revised Selected Papers (Michael A. Bekos, Michael Kaufmann, eds.), volume 13453 of Lecture Notes in Computer Science, pages 98–113, 2022, Springer Verlag.
[bibtex] [pdf] [doi]
[1]Bounding and Computing Obstacle Numbers of Graphs
Martin Balko, Steven Chaplick, Robert Ganian, Siddharth Gupta, Michael Hoffmann, Pavel Valtr, Alexander Wolff
30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany (Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, Grzegorz Herman, eds.), volume 244 of LIPIcs, pages 11:1–11:13, 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]

2021

13 results
2021
[13]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]
[12]New Width Parameters for SAT and Sharp-SAT
Robert Ganian, Stefan Szeider
Artificial Intelligence, volume 295, pages 103460, 2021.
[bibtex] [pdf] [doi]
[11]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]
[10]On Strict (Outer-)Confluent Graphs
Henry Förster, Robert Ganian, Fabian Klute, Martin Nöllenburg
J. Graph Algorithms Appl., 2021.
[bibtex] [pdf]
[9]The complexity landscape of decompositional 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.
[bibtex] [pdf]
[8]Computing Kemeny Rankings from d-Euclidean Preferences
Thekla Hamm, Martin Lackner, Anna Rapberger
Algorithmic Decision Theory - 7th International Conference, ADT 2021, Toulouse, France, November 3-5, 2021, Proceedings, volume 13023 of Lecture Notes in Computer Science, pages 147–161, 2021, Springer Verlag.
[bibtex]
[7]The Complexity of Bayesian Network Learning: Revisiting the Superstructure
Robert Ganian, Viktoriia Korchemna
Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual (Marc'Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, Jennifer Wortman Vaughan, eds.), pages 430–442, 2021.
[bibtex] [pdf]
[6]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]
[5]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]
[4]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]
[3]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]
[2]Graphs with two moplexes
Clément Dallard, Robert Ganian, Meike Hatzel, Matjaz Krnc, Martin Milanic
Proceedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium, LAGOS 2021, 2021, Elsevier.
[bibtex] [pdf]
[1]Worbel: Aggregating Point Labels into Word Clouds
Sujoy Bhore, Robert Ganian, Guangping Li, Martin Nollenburg, Jules Wulms
Proceedings of the International Conference on Advances in Geographic Information Systems 2021 (ACM SIGSPATIAL 2021), 2021.
[bibtex] [pdf]

News

  • New FWF ESPRIT Postdocs

    New FWF ESPRIT Postdocs

    2022-11-09
    Leroy Chew and Alexis de Colnet just joined the Algorithms and Complexity group as PIs of their own FWF ESPRIT …Read More »
  • Best student paper award at DIAGRAMS 2022

    Best student paper award at DIAGRAMS 2022

    2022-10-01
    Alexander Dobler received the Best Student Paper Award at the 13th International Conference on the Theory and Application of Diagrams …Read More »
  • Robert Ganian promoted to Associate Professor

    Robert Ganian promoted to Associate Professor

    2022-07-01
    Effective as of today, Robert Ganian is promoted to a tenured Associate Professor at the Algorithms and Complexity group. Congratulations, …Read More »
  • Best paper award at EvoCOP 2022

    Best paper award at EvoCOP 2022

    2022-05-24
    Jonas Mayerhofer, Markus Kirchweger, Marc Huber, and Günther Raidl received the best paper award for their work A Beam Search …Read More »
  • New PhD: Guangping Li

    New PhD: Guangping Li

    2022-05-13
    Guangping Li successfully defended her PhD thesis “An Algorithmic Study of Practical Map Labeling” on May 13, 2022. Congratulations, Dr. …Read More »

News archive

All news for 2015, 2016, 2017, 2018, 2019, 2020, 2021 and 2022.
TU Wien Informatics
Offenlegung (§25 MedienG) Inhaber der Website ist das Institut für Logic and Computation an der Technischen Universität Wien, 1040 Wien. Die TU Wien distanziert sich von den Inhalten aller extern gelinkten Seiten und übernimmt diesbezüglich keine Haftung. – Disclaimer – Datenschutzerklärung
Log in requires cookies.