New Frontiers for Parameterized Complexity (Research Project)

Funding Organisation: The Austrian Science Funds, FWF
Project Number: FWF P 31336

Project Team

Research Statement

Many important computational problems are intractable on general instances. However, realistic problem instances often contain a certain hidden structure that can be exploited to solve the problem efficiently. The parameterized complexity paradigm provides the perfect tools and techniques to formalize, quantify and exploit various forms of structure in order to efficiently solve a plethora of NP-hard problems. This paradigm has been applied in many fundamental areas of computer science with great success, including graph algorithms, computational logic, boolean satisfiability, constraint satisfaction and others. However, there are prominent areas of computer science where we still lack a thorough understanding of the parameterized complexity of key computational problems.

This project aims at investigating the parameterized complexity of fundamental problems in two such high-impact areas: integer linear programming and machine learning. The obtained results will allow the design of efficient algorithms capable of exploiting various natural forms of structure in order to find exact solutions for NP-hard problems in these important areas of computer science. A secondary aim of the project is to apply newly obtained insights and advancements in other, including more traditional, frontiers of parameterized complexity research.

 

Publications

2020

14 results

2020
[14]	Parameterized Algorithms for Book Embedding Problems Sujoy Bhore, Robert Ganian, Fabrizio Montecchiani, Martin Nöllenburg J. Graph Algorithms Appl., 2020. [bibtex] [doi]
[13]	Using decomposition-parameters for QBF: Mind the prefix! Eduard Eiben, Robert Ganian, Sebastian Ordyniak J. Comput. Syst. Sci., volume 110, pages 1–21, 2020. [bibtex] [pdf]
[12]	On Existential MSO and its Relation to ETH Robert Ganian, Ronald de Haan, Iyad Kanj, Stefan Szeider ACM Transactions on Computation Theory, volume 12, number 4, pages 22:1–22:32, 2020. [bibtex]
[11]	Threshold Treewidth and Hypertree Width Robert Ganian, Andre Schidler, Manuel Sorge, Stefan Szeider Proceeding of IJCAI-PRICAI2020, the 29th International Joint Conference on Artificial Intelligence and the 17th Pacific Rim International Conference on Artificial Intelligence, pages 1898–1904, 2020. [bibtex] [pdf] [doi]
[10]	Fixed-Parameter Tractability of Dependency QBF with Structural Parameters Robert Ganian, Tomás Peitl, Friedrich Slivovsky, Stefan Szeider Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning, KR 2020 (Diego Calvanese, Esra Erdem, Michael Thielscher, eds.), pages 392–402, 2020. [bibtex] [pdf]
[9]	On the Parameterized Complexity of Clustering Incomplete Data into Subspaces of Small Dimension Robert Ganian, Iyad Kanj, Sebastian Ordyniak, Stefan Szeider Proceeding of AAAI-20, the Thirty-Fourth AAAI Conference on Artificial Intelligence, February 7–12, 2020, New York, pages 3906–3913, 2020, AAAI Press. [bibtex] [pdf]
[8]	An Efficient Algorithm for Counting Markov Equivalent DAGs Robert Ganian, Thekla Hamm, Topi Talvitie The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, New York, NY, USA, February 7-12, 2020, pages 10136–10143, 2020, AAAI Press. [bibtex] [pdf]
[7]	The Complexity Landscape of Resource-Constrained Scheduling Robert Ganian, Thekla Hamm, Guillaume Mescoff Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020 (Christian Bessiere, ed.), pages 1741–1747, 2020, ijcai.org. [bibtex] [pdf]
[6]	Parameterized Complexity of Envy-Free Resource Allocation in Social Networks Eduard Eiben, Robert Ganian, Thekla Hamm, Sebastian Ordyniak The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, New York, NY, USA, February 7-12, 2020, pages 7135–7142, 2020, AAAI Press. [bibtex] [pdf]
[5]	Extending Nearly Complete 1-Planar Drawings in Polynomial Time Eduard Eiben, Robert Ganian, Thekla Hamm, Fabian Klute, Martin Nöllenburg 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, August 24-28, 2020, Prague, Czech Republic (Javier Esparza, Daniel Král', eds.), volume 170 of LIPIcs, pages 31:1–31:16, 2020, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. [bibtex] [pdf]
[4]	Extending Partial 1-Planar Drawings Eduard Eiben, Robert Ganian, Thekla Hamm, Fabian Klute, Martin Nöllenburg 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference) (Artur Czumaj, Anuj Dawar, Emanuela Merelli, eds.), volume 168 of LIPIcs, pages 43:1–43:19, 2020, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. [bibtex] [pdf]
[3]	Stable Matchings with Diversity Constraints: Affirmative Action is beyond NP Jiehua Chen, Robert Ganian, Thekla Hamm Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020 (Christian Bessiere, ed.), pages 146–152, 2020, ijcai.org. [bibtex] [pdf]
[2]	Parameterized Algorithms for Queue Layouts Sujoy Bhore, Robert Ganian, Fabrizio Montecchiani, Martin Nöllenburg Graph Drawing and Network Visualization - 28th International Symposium, GD 2020, Vancouver, BC, Canada, September 16-18, 2020, Revised Selected Papers (David Auber, Pavel Valtr, eds.), volume 12590 of Lecture Notes in Computer Science, pages 40–54, 2020, Springer Verlag. [bibtex] [pdf]
[1]	On Covering Segments with Unit Intervals Dan Bergren, Eduard Eiben, Robert Ganian, Iyad Kanj 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France (Christophe Paul, Markus Bläser, eds.), volume 154 of LIPIcs, pages 13:1–13:17, 2020, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. [bibtex] [pdf]

2019

15 results

2019
[15]	Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions: A Survey Robert Ganian, Sebastian Ordyniak Algorithms, volume 12, number 12, pages 248, 2019. [bibtex] [pdf]
[14]	On the Complexity Landscape of Connected f-Factor Problems Robert Ganian, N. S. Narayanaswamy, Sebastian Ordyniak, C. S. Rahul, M. S. Ramanujan Algorithmica, volume 81, number 6, pages 2606–2632, 2019. [bibtex] [pdf]
[13]	Parameterized Complexity of Asynchronous Border Minimization Robert Ganian, Martin Kronegger, Andreas Pfandler, Alexandru Popa Algorithmica, volume 81, number 1, pages 201–223, 2019. [bibtex] [pdf]
[12]	Shrub-Depth: Capturing Height of Dense Graphs Robert Ganian, Petr Hlinený, Jaroslav Nesetril, Jan Obdrzálek, Patrice Ossona de Mendez Logical Methods in Computer Science, 2019. [bibtex] [pdf]
[11]	Counting linear extensions: Parameterizations by treewidth Eduard Eiben, Robert Ganian, Kustaa Kangas, Sebastian Ordyniak Algorithmica, 2019. [bibtex] [pdf]
[10]	Group Activity Selection with Few Agent Types Robert Ganian, Sebastian Ordyniak, C. S. Rahul 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany (Michael A. Bender, Ola Svensson, Grzegorz Herman, eds.), pages 48:1–48:16, 2019. [bibtex] [pdf]
[9]	A Join-Based Hybrid Parameter for Constraint Satisfaction Robert Ganian, Sebastian Ordyniak, Stefan Szeider Proceedings of CP 2019, the 25th International Conference on Principles and Practice of Constraint Programming (Thomas Schiex, Simon de Givry, eds.), volume 11802 of Lecture Notes in Computer Science, pages 195–212, 2019, Springer Verlag. [bibtex] [pdf] [doi]
[8]	The Power of Cut-Based Parameters for Computing Edge Disjoint Paths Robert Ganian, Sebastian Ordyniak Graph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19-21, 2019, Revised Papers (Ignasi Sau, Dimitrios M. Thilikos, eds.), pages 190–204, 2019. [bibtex] [pdf]
[7]	SAT-Encodings for Treecut Width and Treedepth Robert Ganian, Neha Lodha, Sebastian Ordyniak, Stefan Szeider Proceedings of ALENEX 2019, the 21st Workshop on Algorithm Engineering and Experiments (Stephen G. Kobourov, Henning Meyerhenke, eds.), pages 117–129, 2019, Society for Industrial and Applied Mathematics (SIAM). [bibtex] [pdf] [doi]
[6]	On Strict (Outer-)Confluent Graphs Henry Förster, Robert Ganian, Fabian Klute, Martin Nöllenburg Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Prague, Czech Republic, September 17-20, 2019, Proceedings (Daniel Archambault, Csaba D. Tóth, eds.), volume 11904 of Lecture Notes in Computer Science, pages 147–161, 2019, Springer Verlag. [bibtex] [pdf]
[5]	Solving integer quadratic programming via explicit and structural restrictions Eduard Eiben, Robert Ganian, Dusan Knop, Sebastian Ordyniak The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019 (Pascal Van Hentenryck, Zhi-Hua Zhou, eds.), pages 1477–1484, 2019. [bibtex] [pdf]
[4]	The Parameterized Complexity of Cascading Portfolio Scheduling Eduard Eiben, Robert Ganian, Iyad Kanj, Stefan Szeider Proceedings of NeurIPS 2019, the Thirty-third Conference on Neural Information Processing Systems (Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d'Alché-Buc, Emily B. Fox, Roman Garnett, eds.), pages 7666–7676, 2019. [bibtex] [pdf]
[3]	Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth Eduard Eiben, Robert Ganian, Thekla Hamm, O-joung Kwon 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany (Peter Rossmanith, Pinar Heggernes, Joost-Pieter Katoen, eds.), pages 42:1–42:15, 2019. [bibtex] [pdf]
[2]	Integer Programming and Incidence Treedepth Eduard Eiben, Robert Ganian, Dusan Knop, Sebastian Ordyniak, Michal Pilipczuk, Marcin Wrochna Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Ann Arbor, MI, USA, May 22-24, 2019, Proceedings (Andrea Lodi, Viswanath Nagarajan, eds.), volume 11480 of Lecture Notes in Computer Science, pages 194–204, 2019, Springer Verlag. [bibtex] [pdf]
[1]	Parameterized Algorithms for Book Embedding Problems Sujoy Bhore, Robert Ganian, Fabrizio Montecchiani, Martin Nöllenburg Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Prague, Czech Republic, September 17-20, 2019, Proceedings (Daniel Archambault, Csaba D. Tóth, eds.), volume 11904 of Lecture Notes in Computer Science, pages 365–378, 2019, Springer Verlag. [bibtex] [pdf]