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)
  • Grant DOI: 10.55776/Y1329

Project Team

Robert Ganian (Principal Investigator)
Phuc Hung Hoang (Research Assistant – Postdoc)
Simon Wietheger (Research Assistant – Doctoral Candidate)
Mathis Rocton (Affiliated Team Member - Doctoral Candidate)
Liana Khazaliya (Affiliated Team Member - 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

2025

14 results
2025
[14]Extending Orthogonal Planar Graph Drawings Is Fixed-Parameter Tractable
Sujoy Bhore, Robert Ganian, Liana Khazaliya, Fabrizio Montecchiani, Martin Nöllenburg
J. Comput. Geom., 2025.
Note: to appear
[bibtex]
[13]Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
Benjamin Bergougnoux, Vera Chekan, Robert Ganian, Mamadou Moustapha Kanté, Matthias Mnich, Sang-il Oum, Michał Pilipczuk, Erik Jan van Leeuwen
ACM Trans. Comput. Theory, 2025.
Note: to appear
[bibtex]
[12]Training One-Dimensional Graph Neural Networks is NP-Hard
Robert Ganian, Mathis Rocton, Simon Wietheger
Proceedings of the 13th International Conference on Learning Representations, ICLR 2025, 2025, OpenReview.net.
Note: to appear
[bibtex]
[11]The Computational Complexity of Positive Non-Clashing Teaching in Graphs
Robert Ganian, Liana Khazaliya, Fionn McInerney, Mathis Rocton
Proceedings of the 13th International Conference on Learning Representations, ICLR 2025, 2025, OpenReview.net.
Note: to appear
[bibtex]
[10]Parameterized Complexity of Caching in Networks
Robert Ganian, Fionn Mc Inerney, Dimitra Tsigkari
AAAI 2025: The 39th Annual AAAI Conference on Artificial Intelligence, 2025.
Note: to appear
[bibtex]
[9]A Minor-Testing Approach for Coordinated Motion Planning with Sliding Robots
Eduard Eiben, Robert Ganian, Iyad Kanj, M.S. Ramanujan
41st International Symposium on Computational Geometry, SoCG 2025, 2025, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
Note: to appear
[bibtex]
[8]Approximate Evaluation of Quantitative Second Order Queries
Jan Dreier, Robert Ganian, Thekla Hamm
Fortieth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2025.
Note: to appear
[bibtex] [pdf]
[7]The Peculiarities of Extending Queue Layouts
Thomas Depian, Simon Dominik Fink, Robert Ganian, Martin Nöllenburg
Graph-Theoretic Concepts in Computer Science - 51st International Workshop, WG 2025, 2025.
[bibtex]
[6]Pathways to Tractability for Geometric Thickness
Thomas Depian, Simon Dominik Fink, Alexander Firbas, Robert Ganian, Martin Nöllenburg
SOFSEM 2025: Theory and Practice of Computer Science - 50th International Conference on Current Trends in Theory and Practice of Computer Science, 2025.
Note: to appear
[bibtex]
[5]Parameterized Algorithms for Multiagent Pathfinding on Trees
Argyrios Deligkas, Eduard Eiben, Robert Ganian, Iyad Kanj, M.S. Ramanujan
Proceedings of the 24th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2025, 2025, International Foundation for Autonomous Agents and Multiagent Systems.
Note: to appear
[bibtex]
[4]Routing Few Robots in a Crowded Network
Argyrios Deligkas, Eduard Eiben, Robert Ganian, Iyad Kanj, Dominik Leko, Ramanujan M. Sridharan
Algorithms and Data Structures - 19th International Symposium, WADS 2025, 2025.
Note: to appear
[bibtex]
[3]The Complexity of Extending Fair Allocations of Indivisible Goods
Argyrios Deligkas, Eduard Eiben, Robert Ganian, Tiger Lily Goldsmith, Stavros Ioannidis
AAAI 2025: The 39th Annual AAAI Conference on Artificial Intelligence, 2025.
Note: to appear
[bibtex]
[2]A Structural Complexity Analysis of Hierarchical Task Network Planning
Cornelius Brand, Robert Ganian, Fionn McInerney, Simon Wietheger
Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2025,, 2025, ijcai.org.
Note: to appear
[bibtex]
[1]Crossing and Independent Families among Polygons
Anna Brötzner, Robert Ganian, Thekla Hamm, Fabian Klute, Irene Parada
Algorithms and Data Structures - 19th International Symposium, WADS 2025, 2025.
Note: to appear
[bibtex]

2024

27 results
2024
[27]Bounding and Computing Obstacle Numbers of Graphs
Martin Balko, Steven Chaplick, Robert Ganian, Siddharth Gupta, Michael Hoffmann, Pavel Valtr, Alexander Wolff
SIAM J. Discret. Math., volume 38, number 2, pages 1537–1565, 2024.
[bibtex] [pdf] [doi]
[26]Slim Tree-Cut Width
Robert Ganian, Viktoriia Korchemna
Algorithmica, volume 86, number 8, pages 2714–2738, 2024.
[bibtex] [pdf] [doi]
[25]The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width
Robert Ganian, Thekla Hamm, Viktoriia Korchemna, Karolina Okrasa, Kirill Simonov
ACM Trans. Algorithms, volume 20, number 3, pages 19, 2024.
[bibtex] [pdf] [doi]
[24]Smash and grab: The 0*6 scoring game on graphs
Éric Duchêne, Valentin Gledel, Sylvain Gravier, Fionn Mc Inerney, Mehdi Mhalla, Aline Parreau
Theor. Comput. Sci., volume 990, pages 114417, 2024.
[bibtex] [pdf] [doi]
[23]Fixed-Parameter Algorithms for Computing RAC Drawings of Graphs
Cornelius Brand, Robert Ganian, Sebastian Röder, Florian Schager
J. Graph Algorithms Appl., 2024.
Note: to appear
[bibtex]
[22]The Complexity of Optimizing Atomic Congestion
Cornelius Brand, Robert Ganian, Subrahmanyam Kalyanasundaram, Fionn Mc Inerney
Artif. Intell., 2024.
Note: to appear
[bibtex]
[21]Conflict-Free Coloring: Graphs of Bounded Clique-Width and Intersection Graphs
Sriram Bhyravarapu, Tim A. Hartmann, Hung P. Hoang, Subrahmanyam Kalyanasundaram, I. Vinod Reddy
Algorithmica, volume 86, number 7, pages 2250–2288, 2024.
[bibtex] [pdf] [doi]
[20]Revisiting Causal Discovery from a Complexity-Theoretic Perspective
Robert Ganian, Viktoriia Korchemna, Stefan Szeider
Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, IJCAI-24 (Kate Larson, ed.), pages 3377–3385, 8 2024, International Joint Conferences on Artificial Intelligence Organization.
Note: Main Track
[bibtex] [doi]
[19]Near-Tight Runtime Guarantees for Many-Objective Evolutionary Algorithms
Simon Wietheger, Benjamin Doerr
Parallel Problem Solving from Nature - PPSN XVIII - 18th International Conference, PPSN 2024, Hagenberg, Austria, September 14-18, 2024, Proceedings, Part IV (Michael Affenzeller, Stephan M. Winkler, Anna V. Kononova, Heike Trautmann, Tea Tusar, Penousal Machado, Thomas Bäck, eds.), volume 15151 of Lecture Notes in Computer Science, pages 153–168, 2024, Springer Verlag.
[bibtex] [pdf] [doi]
[18]Crossing Number Is NP-Hard for Constant Path-Width (And Tree-Width)
Petr Hlinený, Liana Khazaliya
35th International Symposium on Algorithms and Computation, ISAAC 2024, December 8-11, 2024, Sydney, Australia (Julián Mestre, Anthony Wirth, eds.), volume 322 of LIPIcs, pages 40:1–40:15, 2024, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[17]Generating All Invertible Matrices by Row Operations
Petr Gregor, Hung P. Hoang, Arturo Merino, Ondrej Micka
35th International Symposium on Algorithms and Computation, ISAAC 2024, December 8-11, 2024, Sydney, Australia (Julián Mestre, Anthony Wirth, eds.), volume 322 of LIPIcs, pages 35:1–35:14, 2024, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[16]The Parameterized Complexity Landscape of the Unsplittable Flow Problem
Robert Ganian, Mathis Rocton, Daniel Unterberger
Graph-Theoretic Concepts in Computer Science - 48th International Workshop, WG 2024, Spik, Slovenia, June 19-21, 2024, Revised Selected Papers, 2024, Springer Verlag.
Note: to appear
[bibtex]
[15]A Tight Subexponential-Time Algorithm for Two-Page Book Embedding
Robert Ganian, Haiko Müller, Sebastian Ordyniak, Giacomo Paesani, Mateusz Rychlicki
51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia (Karl Bringmann, Martin Grohe, Gabriele Puppis, Ola Svensson, eds.), volume 297 of LIPIcs, pages 68:1–68:18, 2024, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[14]Problems in NP Can Admit Double-Exponential Lower Bounds When Parameterized by Treewidth or Vertex Cover
Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, Prafullkumar Tale
51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia (Karl Bringmann, Martin Grohe, Gabriele Puppis, Ola Svensson, eds.), volume 297 of LIPIcs, pages 66:1–66:19, 2024, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[13]The Complexity of Fair Division of Indivisible Items with Externalities
Argyrios Deligkas, Eduard Eiben, Viktoriia Korchemna, Simon Schierreich
Thirty-Eighth AAAI Conference on Artificial Intelligence, AAAI 2024, Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence, IAAI 2024, Fourteenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2014, February 20-27, 2024, Vancouver, Canada (Michael J. Wooldridge, Jennifer G. Dy, Sriraam Natarajan, eds.), pages 9653–9661, 2024, AAAI Press.
[bibtex] [pdf] [doi]
[12]Exact Algorithms for Clustered Planarity with Linear Saturators
Giordano Da Lozzo, Robert Ganian, Siddharth Gupta, Bojan Mohar, Sebastian Ordyniak, Meirav Zehavi
35th International Symposium on Algorithms and Computation, ISAAC 2024, 2024, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex]
[11]The Parameterized Complexity of Extending Stack Layouts
Thomas Depian, Simon Dominik Fink, Robert Ganian, Martin Nöllenburg
Graph Drawing and Network Visualization - 31st International Symposium, GD 2024, 2024, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
Note: to appear
[bibtex]
[10]Parameterized Algorithms for Coordinated Motion Planning: Minimizing Energy
Argyrios Deligkas, Eduard Eiben, Robert Ganian, Iyad Kanj, M. S. Ramanujan
51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia (Karl Bringmann, Martin Grohe, Gabriele Puppis, Ola Svensson, eds.), volume 297 of LIPIcs, pages 53:1–53:18, 2024, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[9]The k-Opt Algorithm for the Traveling Salesman Problem Has Exponential Running Time for k \(\geq\) 5
Sophia Heimann, Hung P. Hoang, Stefan Hougardy
51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia (Karl Bringmann, Martin Grohe, Gabriele Puppis, Ola Svensson, eds.), volume 297 of LIPIcs, pages 84:1–84:18, 2024, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[8]Non-Clashing Teaching Maps for Balls in Graphs
Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel
The Thirty Seventh Annual Conference on Learning Theory, June 30 - July 3, 2023, Edmonton, Canada (Shipra Agrawal, Aaron Roth, eds.), volume 247 of Proceedings of Machine Learning Research, pages 840–875, 2024, PMLR.
[bibtex] [pdf]
[7]Hot off the Press: The First Proven Performance Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem
Sacha Cerf, Benjamin Doerr, Benjamin Hebras, Yakob Kahane, Simon Wietheger
Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO 2024, Melbourne, VIC, Australia, July 14-18, 2024 (Xiaodong Li, Julia Handl, eds.), pages 27–28, 2024, ACM.
[bibtex] [pdf] [doi]
[6]Counting Vanishing Matrix-Vector Products
Cornelius Brand, Viktoriia Korchemna, Kirill Simonov, Michael Skotnica
WALCOM: Algorithms and Computation - 18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024, Kanazawa, Japan, March 18-20, 2024, Proceedings (Ryuhei Uehara, Katsuhisa Yamanaka, Hsu-Chun Yen, eds.), volume 14549 of Lecture Notes in Computer Science, pages 335–349, 2024, Springer Verlag.
[bibtex] [pdf] [doi]
[5]The Complexity of Optimizing Atomic Congestion
Cornelius Brand, Robert Ganian, Subrahmanyam Kalyanasundaram, Fionn Mc Inerney
Thirty-Eighth AAAI Conference on Artificial Intelligence, AAAI 2024, Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence, IAAI 2024, Fourteenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2014, February 20-27, 2024, Vancouver, Canada (Michael J. Wooldridge, Jennifer G. Dy, Sriraam Natarajan, eds.), pages 20044–20052, 2024, AAAI Press.
[bibtex] [pdf] [doi]
[4]Enumerating Minimal Solution Sets for Metric Graph Problems
Benjamin Bergougnoux, Oscar Defrain, Fionn Mc Inerney
Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Gozd Martuljek, Slovenia, June 19-21, 2024, Revised Selected Papers (Daniel Král, Martin Milanic, eds.), volume 14760 of Lecture Notes in Computer Science, pages 50–64, 2024, Springer Verlag.
[bibtex] [pdf] [doi]
[3]Hypergraph Dualization with FPT-delay Parameterized by the Degeneracy and Dimension
Valentin Bartier, Oscar Defrain, Fionn Mc Inerney
Combinatorial Algorithms - 35th International Workshop, IWOCA 2024, Ischia, Italy, July 1-3, 2024, Proceedings (Adele Anna Rescigno, Ugo Vaccaro, eds.), volume 14764 of Lecture Notes in Computer Science, pages 111–125, 2024, Springer Verlag.
[bibtex] [pdf] [doi]
[2]Twin-Width Meets Feedback Edges and Vertex Integrity
Jakub Balabán, Robert Ganian, Mathis Rocton
19th International Symposium on Parameterized and Exact Computation, IPEC 2024, 2024, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
Note: to appear
[bibtex]
[1]Computing Twin-Width Parameterized by the Feedback Edge Number
Jakub Balabán, Robert Ganian, Mathis Rocton
41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024, March 12-14, 2024, Clermont-Ferrand, France (Olaf Beyersdorff, Mamadou Moustapha Kanté, Orna Kupferman, Daniel Lokshtanov, eds.), volume 289 of LIPIcs, pages 7:1–7:19, 2024, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]

2023

23 results
2023
[23]Group Activity Selection with Few Agent Types
Robert Ganian, Sebastian Ordyniak, C. S. Rahul
Algorithmica, volume 85, number 5, pages 1111–1155, 2023.
[bibtex] [pdf] [doi]
[22]Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters
Esther Galby, Liana Khazaliya, Fionn Mc Inerney, Roohani Sharma, Prafullkumar Tale
SIAM J. Discrete Math., 2023.
Note: to appear
[bibtex]
[21]Hedonic diversity games: A complexity picture with more than two colors
Robert Ganian, Thekla Hamm, Dusan Knop, Simon Schierreich, Ondrej Suchy
Artif. Intell., volume 325, pages 104017, 2023.
[bibtex] [pdf] [doi]
[20]On the parameterized complexity of clustering problems for incomplete data
Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak, Stefan Szeider
Journal of Computer and System Sciences, volume 134, pages 1–19, 2023.
[bibtex] [doi]
[19]Parameterized complexity of envy-free resource allocation in social networks
Eduard Eiben, Robert Ganian, Thekla Hamm, Sebastian Ordyniak
Artif. Intell., volume 315, pages 103826, 2023.
[bibtex] [pdf] [doi]
[18]Sample compression schemes for balls in graphs
Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel, Yann Vaxès
SIAM J. Discrete Math., 2023.
Note: to appear
[bibtex]
[17]Maximizing Social Welfare in Score-Based Social Distance Games
Robert Ganian, Thekla Hamm, Dusan Knop, Sanjukta Roy, Simon Schierreich, Ondrej Suchý
Proceedings Nineteenth conference on Theoretical Aspects of Rationality and Knowledge, TARK 2023, Oxford, United Kingdom, 28-30th June 2023 (Rineke Verbrugge, ed.), volume 379 of EPTCS, pages 272–286, 2023.
[bibtex] [pdf] [doi]
[16]Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
Benjamin Bergougnoux, Vera Chekan, Robert Ganian, Mamadou Moustapha Kanté, Matthias Mnich, Sang-il Oum, Michał Pilipczuk, Erik Jan van Leeuwen
31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands (Inge Li Gørtz, Martin Farach-Colton, Simon J. Puglisi, Grzegorz Herman, eds.), volume 274 of LIPIcs, pages 18:1–18:18, 2023, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[15]Structure-Aware Lower Bounds and Broadening the Horizon of Tractability for QBF
Johannes Klaus Fichte, Robert Ganian, Markus Hecher, Friedrich Slivovsky, Sebastian Ordyniak
Thirty-Eighth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1–14, 2023.
[bibtex] [pdf] [doi]
[14]A Structural Complexity Analysis of Synchronous Dynamical Systems
Eduard Eiben, Robert Ganian, Thekla Hamm, Viktoriia Korchemna
Thirty-Seventh AAAI Conference on Artificial Intelligence, AAAI 2023, Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence, IAAI 2023, Thirteenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2023, Washington, DC, USA, February 7-14, 2023 (Brian Williams, Yiling Chen, Jennifer Neville, eds.), pages 6313–6321, 2023, AAAI Press.
[bibtex] [pdf]
[13]The Computational Complexity of Concise Hypersphere Classification
Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak, Stefan Szeider
Proceedings of the 40th International Conference on Machine Learning, ICML 2023, pages 9060–9070, 2023, PMLR.
[bibtex] [pdf]
[12]From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem
Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak, Stefan Szeider
18th International Symposium on Parameterized and Exact Computation, IPEC 2023, September 6-8, 2023, Amsterdam, The Netherlands (Neeldhara Misra, Magnus Wahlström, eds.), volume 285 of LIPIcs, pages 16:1–16:14, 2023, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[11]The Parameterized Complexity of Coordinated Motion Planning
Eduard Eiben, Robert Ganian, Iyad Kanj
39th International Symposium on Computational Geometry, SoCG 2023, June 12-15, 2023, Dallas, Texas, USA (Erin W. Chambers, Joachim Gudmundsson, eds.), volume 258 of LIPIcs, pages 28:1–28:16, 2023, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[10]Consistency Checking Problems: A Gateway to Parameterized Sample Complexity
Robert Ganian, Liana Khazaliya, Kirill Simonov
18th International Symposium on Parameterized and Exact Computation, IPEC 2023, September 6-8, 2023, Amsterdam, The Netherlands (Neeldhara Misra, Magnus Wahlström, eds.), volume 285 of LIPIcs, pages 18:1–18:17, 2023, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[9]A Polyhedral Perspective on Tropical Convolutions
Cornelius Brand, Martin Koutecký, Alexandra Lassota
Combinatorial Algorithms - 34th International Workshop, IWOCA 2023, Tainan, Taiwan, June 7-10, 2023, Proceedings (Sun-Yuan Hsieh, Ling-Ju Hung, Chia-Wei Lee, eds.), volume 13889 of Lecture Notes in Computer Science, pages 111–122, 2023, Springer Verlag.
[bibtex] [pdf] [doi]
[8]Upward and Orthogonal Planarity are W[1]-Hard Parameterized by Treewidth
Bart M. P. Jansen, Liana Khazaliya, Philipp Kindermann, Giuseppe Liotta, Fabrizio Montecchiani, Kirill Simonov
Graph Drawing and Network Visualization - 31st International Symposium, GD 2023, Isola delle Femmine, Palermo, Italy, September 20-22, 2023, Revised Selected Papers, Part II (Michael A. Bekos, Markus Chimani, eds.), volume 14466 of Lecture Notes in Computer Science, pages 203–217, 2023, Springer Verlag.
[bibtex] [pdf] [doi]
[7]Fast Convolutions for Near-Convex Sequences
Cornelius Brand, Alexandra Lassota
34th International Symposium on Algorithms and Computation, ISAAC 2023, December 3-6, 2023, Kyoto, Japan (Satoru Iwata, Naonori Kakimura, eds.), volume 283 of LIPIcs, pages 16:1–16:16, 2023, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[6]Deterministic Constrained Multilinear Detection
Cornelius Brand, Viktoriia Korchemna, Michael Skotnica
48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28 to September 1, 2023, Bordeaux, France (Jérôme Leroux, Sylvain Lombardy, David Peleg, eds.), volume 272 of LIPIcs, pages 25:1–25:14, 2023, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[5]A Parameterized Theory of PAC Learning
Cornelius Brand, Robert Ganian, Kirill Simonov
Thirty-Seventh AAAI Conference on Artificial Intelligence, AAAI 2023, Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence, IAAI 2023, Thirteenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2023, Washington, DC, USA, February 7-14, 2023 (Brian Williams, Yiling Chen, Jennifer Neville, eds.), pages 6834–6841, 2023, AAAI Press.
[bibtex] [pdf]
[4]New Complexity-Theoretic Frontiers of Tractability for Neural Network Training
Cornelius Brand, Robert Ganian, Mathis Rocton
Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, 2023.
[bibtex]
[3]Fixed-Parameter Algorithms for Computing RAC Drawings of Graphs
Cornelius Brand, Robert Ganian, Sebastian Röder, Florian Schager
Graph Drawing and Network Visualization - 31st International Symposium, GD 2023, Isola delle Femmine, Palermo, Italy, September 20-22, 2023, Revised Selected Papers, Part II (Michael A. Bekos, Markus Chimani, eds.), volume 14466 of Lecture Notes in Computer Science, pages 66–81, 2023, Springer Verlag.
[bibtex] [pdf] [doi]
[2]The Parameterized Complexity of Network Microaggregation
Václav Blazej, Robert Ganian, Dusan Knop, Jan Pokorný, Simon Schierreich, Kirill Simonov
Thirty-Seventh AAAI Conference on Artificial Intelligence, AAAI 2023, Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence, IAAI 2023, Thirteenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2023, Washington, DC, USA, February 7-14, 2023 (Brian Williams, Yiling Chen, Jennifer Neville, eds.), pages 6262–6270, 2023, AAAI Press.
[bibtex] [pdf]
[1]Extending Orthogonal Planar Graph Drawings Is Fixed-Parameter Tractable
Sujoy Bhore, Robert Ganian, Liana Khazaliya, Fabrizio Montecchiani, Martin Nöllenburg
39th International Symposium on Computational Geometry, SoCG 2023, June 12-15, 2023, Dallas, Texas, USA (Erin W. Chambers, Joachim Gudmundsson, eds.), volume 258 of LIPIcs, pages 18:1–18:16, 2023, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]

2022

24 results
2022
[24]Parameterized Algorithms for Queue Layouts
Sujoy Bhore, Robert Ganian, Fabrizio Montecchiani, Martin Nöllenburg
J. Graph Algorithms Appl., volume 26, number 3, pages 335–352, 2022.
[bibtex] [pdf] [doi]
[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]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]
[20]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]
[19]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]
[18]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]
[17]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]
[16]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]
[15]Slim Tree-Cut Width
Robert Ganian, Viktoriia Korchemna
17th International Symposium on Parameterized and Exact Computation, IPEC 2022, September 7-9, 2022, Potsdam, Germany (Holger Dell, Jesper Nederlof, eds.), volume 249 of LIPIcs, pages 15:1–15:18, 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), volume 271 of LIPIcs, pages 13:1–13:17, 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [doi]
[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
Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Tokyo, Japan, September 13-16, 2022, Revised Selected Papers (Patrizio Angelini, Reinhard von Hanxleden, eds.), volume 13764 of Lecture Notes in Computer Science, pages 175–187, 2022, Springer Verlag.
[bibtex] [pdf] [doi]
[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

14 results
2021
[14]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]
[13]New Width Parameters for SAT and Sharp-SAT
Robert Ganian, Stefan Szeider
Artificial Intelligence, volume 295, pages 103460, 2021.
[bibtex] [pdf] [doi]
[12]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]
[11]On Strict (Outer-)Confluent Graphs
Henry Förster, Robert Ganian, Fabian Klute, Martin Nöllenburg
J. Graph Algorithms Appl., 2021.
[bibtex] [pdf]
[10]Graphs with at most two moplexes
Clément Dallard, Robert Ganian, Meike Hatzel, Matjaz Krnc, Martin Milanic
Journal of Graph Theory, 2021, Wiley Online Library.
[bibtex]
[9]The complexity landscape of decompositional parameters for ILP: Programs with Few Global Variables and Constraints
Pavel Dvořá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

  • Best Paper Award at SOFSEM 2025

    Best Paper Award at SOFSEM 2025

    2025-01-23
    Thomas Depian, Simon D. Fink, Alexander Firbas, Robert Ganian, and Martin Nöllenburg received the Best Paper Award for their paper …Read More »
  • Markus Wallinger receives Award of Excellence for his PhD Thesis

    Markus Wallinger receives Award of Excellence for his PhD Thesis

    2024-12-05
    Our former group member Markus Wallinger won the Award of Excellence by the Federal Ministry for Education, Science and Research. …Read More »
  • Thomas Depian receives State Prize for his Master’s Thesis

    Thomas Depian receives State Prize for his Master’s Thesis

    2024-11-21
    Our group member Thomas Depian won the Appreciation Award given by the Federal Ministry for Education, Science and Research. This …Read More »
  • Best Paper Award at GECCO 2024 for M. Bresich, G. Raidl, and S. Limmer

    Best Paper Award at GECCO 2024 for M. Bresich, G. Raidl, and S. Limmer

    2024-07-24
    Maria Bresich, Günther Raidl, and Steffen Limmer received the best paper award at the 2024 Genetic and Evolutionary Computation Conference …Read More »
  • Welcome to our Feodor Lynen Fellow Dr. Frank Sommer

    Welcome to our Feodor Lynen Fellow Dr. Frank Sommer

    2024-06-14
    On June 1, 2024, Dr. Frank Sommer has joined the Algorithms and Complexity group with a prestigious Feodor Lynen postdoc …Read More »

News archive

All news for 2015, 2016, 2017, 2018, 2019, 2020, 2021, 2022, 2023 and 2024.
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.