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

New Frontiers for Parameterized Complexity (Research Project)

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

Project Team

Robert Ganian (Postdoc, Principal Investigator)
Thekla Hamm (Doctoral Student)

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

18 results
2020
[18]Parameterized Algorithms for Book Embedding Problems
Sujoy Bhore, Robert Ganian, Fabrizio Montecchiani, Martin Nöllenburg
J. Graph Algorithms Appl., 2020.
[bibtex] [doi]
[17]The Power of Cut-Based Parameters for Computing Edge Disjoint Paths
Robert Ganian, Sebastian Ordyniak
Algorithmica, 2020.
Note: to appear
[bibtex]
[16]Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions: a Survey
Robert Ganian, Sebastian Ordyniak
MDPI Algorithms, 2020.
Note: to appear
[bibtex]
[15]On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem
Robert Ganian, Fabian Klute, Sebastian Ordyniak
Algorithmica, 2020.
Note: to appear
[bibtex]
[14]Using Decomposition-Parameters for QBF: Mind the Prefix!
Eduard Eiben, Robert Ganian, Sebastian Ordyniak
Journal of Computer and System Sciences, 2020.
Note: to appear
[bibtex]
[13]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]
[12]Towards a Polynomial Kernel for Directed Feedback Vertex Set
Benjamin Bergougnoux, Eduard Eiben, Robert Ganian, Sebastian Ordyniak, M. S. Ramanujan
Algorithmica, 2020.
Note: to appear
[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
Proceeding of AAAI-20, the Thirty-Fourth AAAI Conference on Artificial Intelligence, February 7–12, 2020, New York, 2020.
Note: to appear
[bibtex]
[7]The Complexity Landscape of Resource-Constrained Scheduling
Robert Ganian, Thekla Hamm, Guillaume Mescoff
Proceeding of IJCAI-PRICAI2020, the 29th International Joint Conference on Artificial Intelligence and the 17th Pacific Rim International Conference on Artificial Intelligence, 2020.
Note: to appear
[bibtex]
[6]Parameterized Complexity of Envy-Free Resource Allocation in Social Networks
Eduard Eiben, Robert Ganian, Thekla Hamm, Sebastian Ordyniak
Proceeding of AAAI-20, the Thirty-Fourth AAAI Conference on Artificial Intelligence, February 7–12, 2020, New York, 2020.
Note: to appear
[bibtex]
[5]Extending Nearly Complete 1-Planar Drawings in Polynomial Time
Eduard Eiben, Robert Ganian, Thekla Hamm, Fabian Klute, Martin Nollenburg
45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, 2020, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.
Note: to appear
[bibtex]
[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, 2020, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.
Note: to appear
[bibtex]
[3]Stable Matchings with Diversity Constraints: Affirmative Action is beyond NP
Jiehua Chen, Robert Ganian, Thekla Hamm
Proceeding of IJCAI-PRICAI2020, the 29th International Joint Conference on Artificial Intelligence and the 17th Pacific Rim International Conference on Artificial Intelligence, 2020.
Note: to appear
[bibtex]
[2]Parameterized Algorithms for Queue Layouts
Sujoy Bhore, Robert Ganian, Fabrizio Montecchiani, Martin Nöllenburg
Proceedings of GD 2020, the 28th International Symposium on Graph Drawing and Network Visualization, 2020.
Note: To appear
[bibtex]
[1]On Covering Segments with Unit Intervals
Dan Bergren, Eduard Eiben, Robert Ganian, Iyad Kanj
37th Symposium on Theoretical Aspects of Computer Science, STACS 2020, 2020, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.
Note: to appear
[bibtex]

2019

14 results
2019
[14]On the Complexity Landscape of Connected f-Factor Problems
Robert Ganian, N. S. Narayanaswamy, Sebastian Ordyniak, C. S. Rahul, M. S. Ramanujan
Algorithmica, 2019.
[bibtex]
[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]
[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]
[11]Counting linear extensions: Parameterizations by treewidth
Eduard Eiben, Robert Ganian, Kustaa Kangas, Sebastian Ordyniak
Algorithmica, 2019.
[bibtex]
[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]
[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]
[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
Proceedings of GD 2019, the 27th International Symposium on Graph Drawing and Network Visualization, 2019.
Note: To appear
[bibtex]
[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]
[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]
[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]
[2]Integer Programming and Incidence Treedepth?
Eduard Eiben, Robert Ganian, Dusan Knop, Sebastian Ordyniak, Michal Piliczuk, Marcin Wrochna
Proceedings of IPCO 2019, The 20th Conference on Integer Programming and Combinatorial Optimization, 2019.
Note: To appear
[bibtex]
[1]Parameterized Algorithms for Book Embedding Problems
Sujoy Bhore, Robert Ganian, Fabrizio Montecchiani, Martin Nöllenburg
Proceedings of GD 2019, the 27th International Symposium on Graph Drawing and Network Visualization, 2019.
Note: To appear
[bibtex]

News

  • Martin Nöllenburg: promotion to Full Professor

    Martin Nöllenburg: promotion to Full Professor

    2020-12-17
    By December 1st, 2020, our colleague Martin Nöllenburg has been promoted to Full Professor for Graph and Geometric Algorithms.  Martin has …Read More »
  • Martin Kronegger wins the Best Teaching Award 2020

    Martin Kronegger wins the Best Teaching Award 2020

    2020-10-23
    Congratulations to Martin Kronegger who received a Best Teaching Award 2020 from TU Wien. The Algorithms and Complexity group is …Read More »
  • Welcome to our Feodor Lynen Fellow Dr. Manuel Sorge

    Welcome to our Feodor Lynen Fellow Dr. Manuel Sorge

    2020-10-12
    On October 1, 2020, Dr. Manuel Sorge has joined the Algorithms and Complexity group with a prestigious Feodor Lynen postdoc …Read More »
  • TU Wien students excel at the 2020 Graph Drawing Contest

    TU Wien students excel at the 2020 Graph Drawing Contest

    2020-10-01
    The 27th annual Graph Drawing Contest, held (virtually) in conjunction with the 28th International Symposium on Graph Drawing and Network …Read More »
  • Best Paper Award at CP’2020

    Best Paper Award at CP’2020

    2020-09-11
    Tomáš Peitl and Stefan Szeider won the Best Paper Award at the main track of CP'2020, the 26th International Conference on Principles …Read More »

News archive

All news for 2015, 2016, 2017, 2018 and 2019.
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.