Publications: Robert Ganian

2026

Coordinated Motion Planning is FPT on Discretized Simple Polygons
Argyrios Deligkas, Eduard Eiben, Robert Ganian, Iyad Kanj
53rd International Colloquium on Automata, Languages, and Programming, ICALP 2026, 2026, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
Note: to appear
[details]

A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs (Best Paper Award)
Ajaykrishnan E S, Robert Ganian, Daniel Lokshtanov, Vaishali Surianarayanan
2026 Symposium on Simplicity in Algorithms, SOSA 2026, 2026, SIAM.
Note: to appear
[details]

Coordinated Motion Planning is FPT on Discretized Simple Polygons
Narek Bojikian, Alexander Firbas, Robert Ganian, Hung Hoang, Krisztina Szilagyi
53rd International Colloquium on Automata, Languages, and Programming, ICALP 2026, 2026, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
Note: to appear
[details]

Fair Correlation Clustering Meets Graph Parameters
Johannes Blaha, Robert Ganian, Katharina Gillig, Jonathan Højlev, Simon Wietheger
Proceedings of the 17th Latin American Theoretical Informatics (LATIN 2026), 2026.
Note: to appear
[details]

Routing Few Robots in a Crowded Network
Argyrios Deligkas and Eduard Eiben and Robert Ganian and Iyad Kanj and Dominik Leko and M. S. Ramanujan
Journal of Computer and System Sciences, 2026.
Note: to appear
[details]

Parameterized Algorithms for Coordinated Motion Planning: Minimizing Energy
Argyrios Deligkas and Eduard Eiben and Robert Ganian and Iyad Kanj and M. S. Ramanujan
ACM Transactions on Algorithms, 2026.
Note: to appear
[details]

The Peculiarities of Extending Queue Layouts
Depian, Thomas, Fink, Simon D., Ganian, Robert, Nöllenburg, Martin
Graph-Theoretic Concepts in Computer Science (WG'25) (Fernau, Henning and Kindermann, Philipp), volume 16124 of LNCS, pages 177-191, 2026, Springer.
[doi] [details]

The Parameterized Complexity of Coordinated Motion Planning
Eduard Eiben and Robert Ganian and Iyad Kanj
Discrete and Computational Geometry, 2026.
Note: to appear
[details]

A Structural Complexity Analysis of Synchronous Dynamical Systems
Eduard Eiben and Robert Ganian and Thekla Hamm and Viktoriia Korchemna
Artificial Intelligence, 2026.
Note: to appear
[details]

Bilateral Treewidth for QBF: Where Strategies and Resolution Meet
Robert Ganian, Marlene Gründel
29th International Conference on Theory and Applications of Satisfiability Testing, SAT 2026, 2026, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
Note: to appear
[details]

Makespan Minimization in Split Learning: From Theory to Practice
Robert Ganian and Fionn Mc Inerney and Dimitra Tsigkari
IEEE INFOCOM 2026 - IEEE Conference on Computer Communications, 2026.
Note: to appear
[details]

Computing Twin-Width via Treedepth and Vertex Integrity
Robert Ganian, Mathis Rocton
43rd International Symposium on Theoretical Aspects of Computer Science, STACS 2026, 2026, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
Note: to appear
[details]

Gateways to Tractability for Satisfiability in Pearl’s Causal Hierarchy
Robert Ganian, Marlene Gründel and Simon Wietheger
Proceedings of the 43rd International Conference on Machine Learning, ICML 2026, 2026, PMLR.
Note: to appear
[details]

2025

Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
Benjamin Bergougnoux and Vera Chekan and Robert Ganian and Mamadou Moustapha Kanté and Matthias Mnich and Sang-il Oum and Michal Pilipczuk and Erik Jan van Leeuwen
ACM Trans. Comput. Theory, volume 17, number 3, pages 18:1-18:42, 2025.
[pdf] [doi] [details]

Crossing and Independent Families Among Polygons
Anna Brötzner and Robert Ganian and Thekla Hamm and Fabian Klute and Irene Parada
19th International Symposium on Algorithms and Data Structures, WADS 2025, August 11-15, 2025, York University, Toronto, Canada (Pat Morin and Eunjin Oh), volume 349 of LIPIcs, pages 11:1-11:15, 2025, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]

A Structural Complexity Analysis of Hierarchical Task Network Planning
Cornelius Brand and Robert Ganian and Fionn Mc Inerney and Simon Wietheger
Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2025, Montreal, Canada, August 16-22, 2025, pages 4391-4400, 2025, ijcai.org.
[pdf] [doi] [details]

Computing Twin-Width Parameterized by the Feedback Edge Number and Vertex Integrity
Jakub Balabán, Robert Ganian, Mathis Rocton
SIAM J. Discret. Math., 2025.
Note: to appear
[details]

The complexity of optimizing atomic congestion
Cornelius Brand and Robert Ganian and Subrahmanyam Kalyanasundaram and Fionn Mc Inerney
Artif. Intell., volume 338, pages 104241, 2025.
[pdf] [doi] [details]

The Complexity of Extending Fair Allocations of Indivisible Goods
Argyrios Deligkas and Eduard Eiben and Robert Ganian and Tiger-Lily Goldsmith and Stavros D. Ioannidis
AAAI-25, Sponsored by the Association for the Advancement of Artificial Intelligence, February 25 - March 4, 2025, Philadelphia, PA, USA (Toby Walsh and Julie Shah and Zico Kolter), pages 13745-13753, 2025, AAAI Press.
[pdf] [doi] [details]

Routing Few Robots in a Crowded Network
Argyrios Deligkas and Eduard Eiben and Robert Ganian and Iyad Kanj and Dominik Leko and M. S. Ramanujan
19th International Symposium on Algorithms and Data Structures, WADS 2025, August 11-15, 2025, York University, Toronto, Canada (Pat Morin and Eunjin Oh), volume 349 of LIPIcs, pages 20:1-20:15, 2025, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]

Parameterized Algorithms for Multiagent Pathfinding on Trees
Argyrios Deligkas and Eduard Eiben and Robert Ganian and Iyad Kanj and M. S. Ramanujan
Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2025, Detroit, MI, USA, May 19-23, 2025 (Sanmay Das and Ann Nowé and Yevgeniy Vorobeychik), pages 584-592, 2025, International Foundation for Autonomous Agents and Multiagent Systems / ACM.
[pdf] [doi] [details]

Pathways to Tractability for Geometric Thickness
Depian, Thomas, Fink, Simon D., Firbas, Alexander, Ganian, Robert, Nöllenburg, Martin
Theory and Practice of Computer Science (SOFSEM'25) (Rastislav Královic and Vera Kurková), volume 15538 of LNCS, pages 209-224, 2025, Springer.
[doi] [details]

Structural Parameterizations of Simultaneous Planarity
Thomas Depian, Simon D. Fink, Alexander Firbas, Robert Ganian, Matthias Pfretzschner, Ignaz Rutter
36th International Symposium on Algorithms and Computation, ISAAC 2025, 2025, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
Note: to appear
[details]

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.
[details]

Linear Layouts Revisited: Stacks, Queues, and Exact Algorithms
Thomas Depian, Simon D. Fink, Robert Ganian, Vaishali Surianarayanan
33rd Annual European Symposium on Algorithms, ESA 2025, September 15-17, 2025, Warsaw, Poland (Anne Benoit and Haim Kaplan and Sebastian Wild and Grzegorz Herman), volume 351 of LIPIcs, pages 15:1-15:18, 2025, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
Note: to appear
[pdf] [doi] [details]

Partial Level Planarity Parameterized by the Size of the Missing Graph
Depian, Thomas, Fink, Simon D., Klemz, Boris, Ganian, Robert, Nöllenburg, Martin, Sieper, Marie Diana
European Workshop on Computational Geometry (EuroCG'25) (Kratochvíl, Jan and Liotta, Giuseppe), pages 50:1-50:10, 2025.
[details]

Approximate Evaluation of Quantitative Second Order Queries
Dreier, Jan, Ganian, Robert, Hamm, Thekla
2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 664-677, June 2025, IEEE Computer Society.
[pdf] [doi] [details]

A Minor-Testing Approach for Coordinated Motion Planning with Sliding Robots
Eduard Eiben and Robert Ganian and Iyad Kanj and M. S. Ramanujan
41st International Symposium on Computational Geometry, SoCG 2025, June 23-27, 2025, Kanazawa, Japan (Oswin Aichholzer and Haitao Wang), volume 332 of LIPIcs, pages 44:1-44:15, 2025, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]

Parameterized Complexity in Machine Learning
Robert Ganian
Computer Science Review, 2025.
Note: to appear
[details]

Parameterized Complexity of Caching in Networks
Robert Ganian and Fionn Mc Inerney and Dimitra Tsigkari
AAAI-25, Sponsored by the Association for the Advancement of Artificial Intelligence, February 25 - March 4, 2025, Philadelphia, PA, USA (Toby Walsh and Julie Shah and Zico Kolter), pages 11229-11237, 2025, AAAI Press.
[pdf] [doi] [details]

2024

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 and Mamadou Moustapha Kanté and Orna Kupferman and Daniel Lokshtanov), volume 289 of LIPIcs, pages 7:1-7:19, 2024, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]

Extending Orthogonal Planar Graph Drawings is Fixed-parameter Tractable
Bhore, Sujoy, Ganian, Robert, Khazaliya, Liana, Montecchiani, Fabrizio, Nöllenburg, Martin
J. Computational Geometry, volume 15, number 2, pages 3-39, 2024.
[doi] [details]

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 and Jennifer G. Dy and Sriraam Natarajan), pages 20044-20052, 2024, AAAI Press.
[pdf] [doi] [details]

Fixed-Parameter Algorithms for Computing Bend-Restricted RAC Drawings of Graphs
Cornelius Brand and Robert Ganian and Sebastian Röder and Florian Schager
J. Graph Algorithms Appl., volume 28, number 2, pages 131-150, 2024.
[pdf] [doi] [details]

Parameterized Algorithms for Coordinated Motion Planning: Minimizing Energy
Argyrios Deligkas and Eduard Eiben and Robert Ganian and Iyad Kanj and M. S. Ramanujan
51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia (Karl Bringmann and Martin Grohe and Gabriele Puppis and Ola Svensson), volume 297 of LIPIcs, pages 53:1-53:18, 2024, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]

The Parameterized Complexity of Extending Stack Layouts
Depian, Thomas, Fink, Simon D., Ganian, Robert, Nöllenburg, Martin
Graph Drawing and Network Visualization (GD'24) (Felsner, Stefan and Klein, Karsten), volume 320 of LIPIcs, pages 12:1-12:17, 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]

Exact Algorithms for Clustered Planarity with Linear Saturators
Da Lozzo, Giordano, Ganian, Robert, Gupta, Siddharth, Mohar, Bojan, Ordyniak, Sebastian, Zehavi, Meirav
35th International Symposium on Algorithms and Computation, ISAAC 2024, 2024, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[details]

Slim Tree-Cut Width
Robert Ganian and Viktoriia Korchemna
Algorithmica, volume 86, number 8, pages 2714-2738, 2024.
[pdf] [doi] [details]

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), pages 3377-3385, 8 2024, International Joint Conferences on Artificial Intelligence Organization.
Note: Main Track
[doi] [details]

A Tight Subexponential-Time Algorithm for Two-Page Book Embedding
Robert Ganian and Haiko Müller and Sebastian Ordyniak and Giacomo Paesani and Mateusz Rychlicki
51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia (Karl Bringmann and Martin Grohe and Gabriele Puppis and Ola Svensson), volume 297 of LIPIcs, pages 68:1-68:18, 2024, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]

Minimizing Switches in Cased Graph Drawings
Ganian, Robert, Nöllenburg, Martin, Röder, Sebastian
Graph Drawing and Network Visualization (GD'24) (Felsner, Stefan and Klein, Karsten), volume 320 of LIPIcs, pages 43:1-43:3, 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
Note: Poster abstract
[doi] [details]

2023

Extending Orthogonal Planar Graph Drawings is Fixed-Parameter Tractable
Bhore, Sujoy, Ganian, Robert, Khazaliya, Liana, Montecchiani, Fabrizio, Nöllenburg, Martin
Computational Geometry (SoCG'23) (Chambers, Erin W. and Gudmundsson, Joachim), volume 258 of LIPIcs, pages 18:1-18:16, 2023, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
[doi] [details]

The Parameterized Complexity of Network Microaggregation
Václav Blazej and Robert Ganian and Dusan Knop and Jan Pokorný and Simon Schierreich and 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 and Yiling Chen and Jennifer Neville), pages 6262-6270, 2023, AAAI Press.
[pdf] [details]

Worbel: Aggregating Point Labels into Word Clouds
Bhore, Sujoy, Ganian, Robert, Li, Guangping, Nöllenburg, Martin, Wulms, Jules
ACM Trans. Spatial Algorithms and Systems, volume 9, number 3, pages 19:1-19:32, 2023.
[doi] [details]

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 and Markus Chimani), volume 14466 of Lecture Notes in Computer Science, pages 66-81, 2023, Springer.
[pdf] [doi] [details]

A Parameterized Theory of PAC Learning
Cornelius Brand and Robert Ganian and 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 and Yiling Chen and Jennifer Neville), pages 6834-6841, 2023, AAAI Press.
[pdf] [details]

The Parameterized Complexity of Coordinated Motion Planning
Eduard Eiben and Robert Ganian and Iyad Kanj
39th International Symposium on Computational Geometry, SoCG 2023, June 12-15, 2023, Dallas, Texas, USA (Erin W. Chambers and Joachim Gudmundsson), volume 258 of LIPIcs, pages 28:1-28:16, 2023, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]

From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem
Eduard Eiben and Robert Ganian and Iyad Kanj and Sebastian Ordyniak and Stefan Szeider
18th International Symposium on Parameterized and Exact Computation, IPEC 2023, September 6-8, 2023, Amsterdam, The Netherlands (Neeldhara Misra and Magnus Wahlström), volume 285 of LIPIcs, pages 16:1-16:14, 2023, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]

A Structural Complexity Analysis of Synchronous Dynamical Systems
Eduard Eiben and Robert Ganian and Thekla Hamm and 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 and Yiling Chen and Jennifer Neville), pages 6313-6321, 2023, AAAI Press.
[pdf] [details]

Parameterized complexity of envy-free resource allocation in social networks
Eduard Eiben and Robert Ganian and Thekla Hamm and Sebastian Ordyniak
Artif. Intell., volume 315, pages 103826, 2023.
[pdf] [doi] [details]

On the parameterized complexity of clustering problems for incomplete data
Eduard Eiben and Robert Ganian and Iyad Kanj and Sebastian Ordyniak and Stefan Szeider
Journal of Computer and System Sciences, volume 134, pages 1-19, 2023.
[doi] [details]

The Computational Complexity of Concise Hypersphere Classification
Eduard Eiben and Robert Ganian and Iyad Kanj and Sebastian Ordyniak and Stefan Szeider
Proceedings of the 40th International Conference on Machine Learning, ICML 2023, pages 9060-9070, 2023, PMLR.
[pdf] [details]

Structure-Aware Lower Bounds and Broadening the Horizon of Tractability for QBF
Johannes Klaus Fichte and Robert Ganian and Markus Hecher and Friedrich Slivovsky and Sebastian Ordyniak
Thirty-Eighth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1-14, 2023.
[pdf] [doi] [details]

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 and Martin Farach-Colton and Simon J. Puglisi and Grzegorz Herman), volume 274 of LIPIcs, pages 18:1-18:18, 2023, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]

Group Activity Selection with Few Agent Types
Robert Ganian and Sebastian Ordyniak and C. S. Rahul
Algorithmica, volume 85, number 5, pages 1111-1155, 2023.
[pdf] [doi] [details]

Hedonic diversity games: A complexity picture with more than two colors
Robert Ganian and Thekla Hamm and Dusan Knop and Simon Schierreich and Ondrej Suchy
Artif. Intell., volume 325, pages 104017, 2023.
[pdf] [doi] [details]

New Frontiers of Parameterized Complexity in Graph Drawing (Dagstuhl Seminar 23162)
Ganian, Robert, Montecchiani, Fabrizio, Nöllenburg, Martin, Zehavi, Meirav, Khazaliya, Liana
Dagstuhl Reports, volume 13, number 4, pages 58-97, 2023.
[doi] [details]

Maximizing Social Welfare in Score-Based Social Distance Games
Robert Ganian and Thekla Hamm and Dusan Knop and Sanjukta Roy and Simon Schierreich and Ondrej Suchý
Proceedings Nineteenth conference on Theoretical Aspects of Rationality and Knowledge, TARK 2023, Oxford, United Kingdom, 28-30th June 2023 (Rineke Verbrugge), volume 379 of EPTCS, pages 272-286, 2023.
[pdf] [doi] [details]

2022

Bounding and Computing Obstacle Numbers of Graphs
Martin Balko and Steven Chaplick and Robert Ganian and Siddharth Gupta and Michael Hoffmann and Pavel Valtr and Alexander Wolff
30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany (Shiri Chechik and Gonzalo Navarro and Eva Rotenberg and Grzegorz Herman), volume 244 of LIPIcs, pages 11:1-11:13, 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]

On Covering Segments with Unit Intervals
Dan Bergren and Eduard Eiben and Robert Ganian and Iyad Kanj
SIAM J. Discret. Math., volume 36, number 2, pages 1200-1230, 2022.
[pdf] [doi] [details]

Parameterized Algorithms for Queue Layouts
Bhore, Sujoy, Ganian, Robert, Montecchiani, Fabrizio, Nöllenburg, Martin
J. Graph Algorithms Appl., volume 26, number 3, pages 335-352, 2022.
[doi] [details]

Parameterized Algorithms for Upward Planarity
Steven Chaplick and Emilio Di Giacomo and Fabrizio Frati and Robert Ganian and Chrysanthi N. Raftopoulou and Kirill Simonov
38th International Symposium on Computational Geometry, SoCG 2022, June 7-10, 2022, Berlin, Germany (Xavier Goaoc and Michael Kerber), volume 224 of LIPIcs, pages 26:1-26:16, 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]

Testing Upward Planarity of Partial 2-Trees
Steven Chaplick and Emilio Di Giacomo and Fabrizio Frati and Robert Ganian and Chrysanthi N. Raftopoulou and Kirill Simonov
Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Tokyo, Japan, September 13-16, 2022, Revised Selected Papers (Patrizio Angelini and Reinhard von Hanxleden), volume 13764 of Lecture Notes in Computer Science, pages 175-187, 2022, Springer.
[pdf] [doi] [details]

The Complexity of Envy-Free Graph Cutting
Argyrios Deligkas and Eduard Eiben and Robert Ganian and Thekla Hamm and Sebastian Ordyniak
Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022 (Luc De Raedt), pages 237-243, 2022, ijcai.org.
[pdf] [doi] [details]

Finding a Cluster in Incomplete Data
Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak, Stefan Szeider
30th Annual European Symposium on Algorithms (ESA 2022) (Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz), volume 244 of Leibniz International Proceedings in Informatics (LIPIcs), pages 47:1-47:14, 2022, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]

A Unifying Framework for Characterizing and Computing Width Measures
Eduard Eiben and Robert Ganian and Thekla Hamm and Lars Jaffke and O-joung Kwon
13th Innovations in Theoretical Computer Science Conference, ITCS 2022, 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[details]

The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width
Robert Ganian and Thekla Hamm and Viktoriia Korchemna and Karolina Okrasa and Kirill Simonov
49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France (Mikolaj Bojanczyk and Emanuela Merelli and David P. Woodruff), volume 229 of LIPIcs, pages 66:1-66:20, 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]

The Complexity of k-Means Clustering when Little is Known
Robert Ganian and Thekla Hamm and Viktoriia Korchemna and Karolina Okrasa and Kirill Simonov
International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA (Kamalika Chaudhuri and Stefanie Jegelka and Le Song and Csaba Szepesvári and Gang Niu and Sivan Sabato), volume 162 of Proceedings of Machine Learning Research, pages 6960-6987, 2022, PMLR.
[pdf] [details]

Hedonic Diversity Games: A Complexity Picture with More than Two Colors
Robert Ganian and Thekla Hamm and Dusan Knop and Simon Schierreich and Ondrej Suchý
Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, pages 5034-5042, 2022, AAAI Press.
[pdf] [details]

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.
[pdf] [details]

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.
[pdf] [doi] [details]

Slim Tree-Cut Width
Robert Ganian and Viktoriia Korchemna
17th International Symposium on Parameterized and Exact Computation, IPEC 2022, September 7-9, 2022, Potsdam, Germany (Holger Dell and Jesper Nederlof), volume 249 of LIPIcs, pages 15:1-15:18, 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]

Preface: Ninth workshop on graph classes, optimization, and Width Parameters, Vienna, Austria
Robert Ganian and Jan Kratochvíl and Stefan Szeider
Discr. Appl. Math., volume 312, pages 1-2, 2022.
[pdf] [details]

Threshold Treewidth and Hypertree Width
Robert Ganian, Andre Schidler, Manuel Sorge, Stefan Szeider
Journal of Artificial Intelligence Research, volume 74, pages 1687-1713, 2022.
[pdf] [doi] [details]

Weighted Model Counting with Twin-Width
Robert Ganian, Filip Pokr ́yvka, 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 and Ofer Strichman), volume 236 of LIPIcs, pages 15:1-15:17, 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]

An efficient algorithm for counting Markov equivalent DAGs
Robert Ganian and Thekla Hamm and Topi Talvitie
Artificial Intelligence, volume 304, pages 103648, 2022.
[pdf] [doi] [details]

Preface: 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022, August 22-26, 2022, Vienna, Austria
Stefan Szeider and Robert Ganian and Alexandra Silva
47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022, August 22-26, 2022, Vienna, Austria, volume 241 of LIPIcs, 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [details]

2021

Towards a Polynomial Kernel for Directed Feedback Vertex Set
Benjamin Bergougnoux and Eduard Eiben and Robert Ganian and Sebastian Ordyniak and M. S. Ramanujan
Algorithmica, volume 83, number 5, pages 1201-1221, 2021.
[pdf] [details]

Worbel: Aggregating Point Labels into Word Clouds
Bhore, Sujoy, Ganian, Robert, Li, Guangping, Nöllenburg, Martin, Wulms, Jules
Advances in Geographic Information Systems (SIGSPATIAL'21), pages 256-267, 2021, ACM.
[pdf] [doi] [details]

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.
[pdf] [details]

The complexity landscape of decompositional parameters for ILP: Programs with Few Global Variables and Constraints
Pavel Dvořák and Eduard Eiben and Robert Ganian and Dušan Knop and Sebastian Ordyniak
Artificial Intelligence, 2021.
[pdf] [details]

The Parameterized Complexity of Connected Fair Division
Argyrios Deligkas and Eduard Eiben and Robert Ganian and Thekla Hamm and 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), pages 139-145, 2021, ijcai.org.
[pdf] [details]

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.
[pdf] [details]

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.
[details]

Measuring what matters: A hybrid approach to dynamic programming with treewidth
Eduard Eiben and Robert Ganian and Thekla Hamm and O-joung Kwon
J. Comput. Syst. Sci., volume 121, pages 57-75, 2021.
[pdf] [details]

The Parameterized Complexity of Clustering Incomplete Data
Eduard Eiben, Robert Ganian, Iyad Kanj and Sebastian Ordyniak, Stefan Szeider
Proceeding of AAAI-21, the Thirty-Fifth AAAI Conference on Artificial Intelligence, pages 7296-7304, 2021, AAAI Press.
[pdf] [details]

The Parameterized Complexity of Clustering Incomplete Data
Eduard Eiben, Robert Ganian, Iyad Kanj and Sebastian Ordyniak, Stefan Szeider
2021, Technical report AC-TR-21-007, Algorithms and Complexity Group, TU Wien.
[pdf] [details]

On Strict (Outer-)Confluent Graphs
Henry Förster, Robert Ganian, Fabian Klute, Martin Nöllenburg
J. Graph Algorithms Appl., 2021.
[pdf] [details]

The Complexity of Object Association in Multiple Object Tracking
Robert Ganian and Thekla Hamm and Sebastian Ordyniak
Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Virtual Event, February 2-9, 2021, pages 1388-1396, 2021, AAAI Press.
[pdf] [details]

On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem
Robert Ganian and Fabian Klute and Sebastian Ordyniak
Algorithmica, volume 83, number 1, pages 297-336, 2021.
[pdf] [details]

The Complexity of Bayesian Network Learning: Revisiting the Superstructure
Robert Ganian and 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 and Alina Beygelzimer and Yann N. Dauphin and Percy Liang and Jennifer Wortman Vaughan), pages 430-442, 2021.
[pdf] [details]

The Power of Cut-Based Parameters for Computing Edge-Disjoint Paths
Robert Ganian and Sebastian Ordyniak
Algorithmica, volume 83, number 2, pages 726-752, 2021.
[pdf] [details]

On Structural Parameterizations of the Edge Disjoint Paths Problem
Robert Ganian and Sebastian Ordyniak and M. S. Ramanujan
Algorithmica, volume 83, number 6, pages 1605-1637, 2021.
[pdf] [details]

New Width Parameters for SAT and Sharp-SAT
Ganian, Robert, Szeider, Stefan
Artificial Intelligence, volume 295, pages 103460, 2021.
[pdf] [doi] [details]

Crossing-Optimal Extension of Simple Drawings
Robert Ganian and Thekla Hamm and Fabian Klute and Irene Parada and Birgit Vogtenhuber
48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference) (Nikhil Bansal and Emanuela Merelli and James Worrell), volume 198 of LIPIcs, pages 72:1-72:17, 2021, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [details]

Parameterized Complexity in Graph Drawing (Dagstuhl Seminar 21293)
Ganian, Robert, Montecchiani, Fabrizio, Nöllenburg, Martin, Zehavi, Meirav
Dagstuhl Reports, volume 11, number 6, pages 82-123, 2021.
[doi] [details]

2020

On Covering Segments with Unit Intervals
Dan Bergren and Eduard Eiben and Robert Ganian and Iyad Kanj
37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France (Christophe Paul and Markus Bläser), volume 154 of LIPIcs, pages 13:1-13:17, 2020, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [details]

Parameterized Algorithms for Book Embedding Problems
Bhore, Sujoy, Ganian, Robert, Montecchiani, Fabrizio, Nöllenburg, Martin
J. Graph Algorithms Appl., volume 24, number 4, pages 603-620, 2020.
[doi] [details]

Parameterized Algorithms for Queue Layouts
Bhore, Sujoy, Ganian, Robert, Montecchiani, Fabrizio, Nöllenburg, Martin
Graph Drawing and Network Visualization (GD'20) (Auber, David and Valtr, Pavel), volume 12590 of LNCS, pages 40-54, 2020, Springer.
[pdf] [doi] [details]

Foreword: Eighth Workshop on Graph Classes, Optimization, and Width Parameters, Toronto, Ontario, Canada
Derek G. Corneil and Robert Ganian and Andrzej Proskurowski
Discr. Appl. Math., volume 278, pages 1-2, 2020.
[details]

On Existential MSO and Its Relation to ETH
Robert Ganian and Ronald de Haan and Iyad Kanj and Stefan Szeider
ACM Trans. Comput. Theory, volume 12, number 4, pages 22:1-22:32, 2020.
[pdf] [doi] [details]

Extending Nearly Complete 1-Planar Drawings in Polynomial Time
Eiben, Eduard, Ganian, Robert, Hamm, Thekla, Klute, Fabian, Nöllenburg, Martin
Mathematical Foundations of Computer Science (MFCS'20) (Esparza, Javier and Král’, Daniel), volume 170 of LIPIcs, pages 31:1-31:16, 2020, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]

Extending Partial 1-Planar Drawings
Eiben, Eduard, Ganian, Robert, Hamm, Thekla, Klute, Fabian, Nöllenburg, Martin
Automata, Languages, and Programming (ICALP'20) (Artur Czumaj and Anuj Dawar and Emanuela Merelli), volume 168 of LIPIcs, pages 43:1-43:19, 2020, Schloss Dagstuhl–Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]

Parameterized Complexity of Envy-Free Resource Allocation in Social Networks
Eduard Eiben and Robert Ganian and Thekla Hamm and 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.
[pdf] [details]

Using decomposition-parameters for QBF: Mind the prefix!
Eduard Eiben and Robert Ganian and Sebastian Ordyniak
J. Comput. Syst. Sci., volume 110, pages 1-21, 2020.
[pdf] [details]

The Complexity Landscape of Resource-Constrained Scheduling
Robert Ganian and Thekla Hamm and Guillaume Mescoff
Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020 (Christian Bessiere), pages 1741-1747, 2020, ijcai.org.
[pdf] [details]

An Efficient Algorithm for Counting Markov Equivalent DAGs
Robert Ganian and Thekla Hamm and 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.
[pdf] [details]

On the Parameterized Complexity of Clustering Incomplete Data into Subspaces of Small Rank
Robert Ganian, Iyad Kanj, Sebastian Ordyniak and 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.
[pdf] [details]

On the Parameterized Complexity of Clustering
Robert Ganian, Iyad Kanj, Sebastian Ordyniak and Stefan Szeider
2020, Technical report AC-TR-20-002, Algorithms and Complexity Group, TU Wien.
[pdf] [details]

Fixed-Parameter Tractability of Dependency QBF with Structural Parameters
Robert Ganian and Tomáš Peitl and Friedrich Slivovsky and Stefan Szeider
Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning, KR 2020 (Diego Calvanese and Esra Erdem and Michael Thielscher), pages 392-402, 2020.
[pdf] [details]

Fixed-Parameter Tractability of Dependency QBF with Structural Parameters
Robert Ganian, Tomáš Peitl, Friedrich Slivovsky, Stefan Szeider
2020, Technical report AC-TR-20-011, Algorithms and Complexity Group, TU Wien.
[pdf] [details]

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.
[pdf] [doi] [details]

Threshold Treewidth and Hypertree Width
Robert Ganian, Andre Schidler, Manuel Sorge and Stefan Szeider
2020, Technical report AC-TR-20-005, Algorithms and Complexity Group, TU Wien.
[pdf] [details]

2019

Parameterized Algorithms for Book Embedding Problems
Bhore, Sujoy, Ganian, Robert, Montecchiani, Fabrizio, Nöllenburg, Martin
Graph Drawing and Network Visualization (GD'19) (Archambault, Daniel and Tóth, Csaba D.), volume 11904 of LNCS, pages 365-378, 2019, Springer.
[pdf] [doi] [details]

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 and Pinar Heggernes and Joost-Pieter Katoen), pages 42:1-42:15, 2019.
[pdf] [details]

The Parameterized Complexity of Cascading Portfolio Scheduling
Eduard Eiben, Robert Ganian, Iyad Kanj and Stefan Szeider
Proceedings of NeurIPS 2019, the Thirty-third Conference on Neural Information Processing Systems (Hanna M. Wallach and Hugo Larochelle and Alina Beygelzimer and Florence d’Alché-Buc and Emily B. Fox and Roman Garnett), pages 7666-7676, 2019.
[pdf] [details]

The Parameterized Complexity of Cascading Portfolio Scheduling
Eduard Eiben, Robert Ganian, Iyad Kanj and Stefan Szeider
2019, Technical report AC-TR-19-009, Algorithms and Complexity Group, TU Wien.
[pdf] [details]

Solving integer quadratic programming via explicit and structural restrictions
Eduard Eiben, Robert Ganian, Dusan Knop and Sebastian Ordyniak
The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019 (Pascal Van Hentenryck and Zhi-Hua Zhou), pages 1477-1484, 2019.
[pdf] [details]

Counting linear extensions: Parameterizations by treewidth
Eduard Eiben, Robert Ganian, Kustaa Kangas, Sebastian Ordyniak
Algorithmica, 2019.
[pdf] [details]

Integer Programming and Incidence Treedepth
Eduard Eiben and Robert Ganian and Dusan Knop and Sebastian Ordyniak and Michal Pilipczuk and Marcin Wrochna
Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Ann Arbor, MI, USA, May 22-24, 2019, Proceedings (Andrea Lodi and Viswanath Nagarajan), volume 11480 of Lecture Notes in Computer Science, pages 194-204, 2019, Springer.
[pdf] [details]

On Strict (Outer-)Confluent Graphs
Förster, Henry, Ganian, Robert, Klute, Fabian, Nöllenburg, Martin
Graph Drawing and Network Visualization (GD'19) (Archambault, Daniel and Tóth, Csaba D.), volume 11904 of LNCS, pages 147-161, 2019, Springer.
[pdf] [doi] [details]

Shrub-Depth: Capturing Height of Dense Graphs
Robert Ganian, Petr Hlinen ́y, Jaroslav Nesetril, Jan Obdrz\ĺek, Patrice Ossona de Mendez
Logical Methods in Computer Science, 2019.
[pdf] [details]

SAT-Encodings for Treecut Width and Treedepth
Robert Ganian, Neha Lodha, Sebastian Ordyniak and Stefan Szeider
Proceedings of ALENEX 2019, the 21st Workshop on Algorithm Engineering and Experiments (Stephen G. Kobourov and Henning Meyerhenke), pages 117-129, 2019, SIAM.
[pdf] [doi] [details]

SAT-Encodings for Treecut Width and Treedepth
Robert Ganian, Neha Lodha, Sebastian Ordyniak and Stefan Szeider
2019, Technical report AC-TR-19-001, Algorithms and Complexity Group, TU Wien.
[pdf] [details]

On the Complexity Landscape of Connected f-Factor Problems
Robert Ganian and N. S. Narayanaswamy and Sebastian Ordyniak and C. S. Rahul and M. S. Ramanujan
Algorithmica, volume 81, number 6, pages 2606-2632, 2019.
[pdf] [details]

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 and Dimitrios M. Thilikos), pages 190-204, 2019.
[pdf] [details]

Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions: A Survey
Robert Ganian and Sebastian Ordyniak
Algorithms, volume 12, number 12, pages 248, 2019.
[pdf] [details]

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 and Simon de Givry), volume 11802 of Lecture Notes in Computer Science, pages 195-212, 2019, Springer Verlag.
[pdf] [doi] [details]

A Join-Based Hybrid Parameter for Constraint Satisfaction
Robert Ganian, Sebastian Ordyniak, Stefan Szeider
2019, Technical report AC-TR-19-006, Algorithms and Complexity Group, TU Wien.
[pdf] [details]

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 and Ola Svensson and Grzegorz Herman), pages 48:1-48:16, 2019.
[pdf] [details]

2018

A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
Eduard Eiben and Robert Ganian and O-joung Kwon
Journal of Computer and System Sciences, volume 97, pages 121-146, 2018.
[pdf] [details]

On the complexity of rainbow coloring problems
Eduard Eiben and Robert Ganian and Juho Lauri
Discr. Appl. Math., volume 246, pages 38-48, 2018.
[pdf] [details]

Small Resolution Proofs for QBF using Dependency Treewidth
Eduard Eiben, Robert Ganian and Sebastian Ordyniak
35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28–March 3, 2018, Caen, France (Rolf Neidermeier and Brigitte Vall ́ee), volume 96 of LIPIcs, pages 28:1-28:15, 2018, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.
[pdf] [details]

Solving Problems on Graphs of High Rank-Width
Eduard Eiben, Robert Ganian, Stefan Szeider
Algorithmica, volume 80, number 2, pages 742-771, 2018.
[pdf] [doi] [details]

Meta-kernelization using well-structured modulators
Eduard Eiben and Robert Ganian and Stefan Szeider
Discr. Appl. Math., volume 248, pages 153-167, 2018.
[pdf] [doi] [details]

Unary Integer Linear Programming with Structural Restrictions
Eduard Eiben and Robert Ganian and Dusan Knop and Sebastian Ordyniak
Proceedings of IJCAI 2018, the 27th International Joint Conference on Artificial Intelligence, pages 1284-1290, 2018, ijcai.org.
[pdf] [details]

A Structural Approach to Activity Selection
Eduard Eiben and Robert Ganian and Sebastian Ordyniak
Proceedings of IJCAI 2018, the 27th International Joint Conference on Artificial Intelligence, pages 203-209, 2018, ijcai.org.
[pdf] [details]

Parameterized Algorithms for the Matrix Completion Problem
Robert Ganian, Iyad Kanj, Sebastian Ordyniak and Stefan Szeider
Proceeding of ICML, the Thirty-fifth International Conference on Machine Learning, Stockholm, July 10–15, 2018, pages 1642-1651, 2018, JMLR.org.
Note: ISSN: 1938-7228
[pdf] [details]

Sum-of-Products with Default Values: Algorithms and Complexity Results
Robert Ganian, Eun Jung Kim, Friedrich Slivovsky, Stefan Szeider
Proceedings of ICTAI 2018, the 30th IEEE International Conference on Tools with Artificial Intelligence (Lefteri H. Tsoukalas and Éric Grégoire and Miltiadis Alamaniotis), pages 733-737, 2018, IEEE.
[pdf] [doi] [details]

Sum-of-Products with Default Values: Algorithms and Complexity Results
Robert Ganian, Eun Jung Kim, Friedrich Slivovsky and Stefan Szeider
2018, Technical report AC-TR-18-007, Algorithms and Complexity Group, TU Wien.
[pdf] [details]

On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem
Robert Ganian and Fabian Klute and Sebastian Ordyniak
35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28–March 3, 2018, Caen, France (Rolf Neidermeier and Brigitte Vall ́ee), volume 96 of LIPIcs, pages 33:1-33:14, 2018, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.
[pdf] [details]

The complexity landscape of decompositional parameters for ILP
Robert Ganian and Sebastian Ordyniak
Artificial Intelligence, volume 257, pages 61-71, 2018.
[pdf] [details]

2017

Towards a Polynomial Kernel for Directed Feedback Vertex Set
Benjamin Bergougnoux and Eduard Eiben and Robert Ganian and Sebastian Ordyniak and M. S. Ramanujan
42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, August 21-25, 2017 - Aalborg, Denmark (Kim G. Larsen and Hans L. Bodlaender and Jean-François Raskin), volume 83 of LIPIcs, pages 36:1-36:15, 2017, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.
[pdf] [details]

Going Beyond Primal Treewidth for (M)ILP
Robert Ganian and Sebastian Ordyniak and M. S. Ramanujan
Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA., pages 815-821, 2017.
[pdf] [details]

Solving Integer Linear Programs with a Small Number of Global Variables and Constraints
Pavel Dvořák and Eduard Eiben and Robert Ganian and Dušan Knop and Sebastian Ordyniak
Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017 (Carles Sierra), pages 607-613, 2017, ijcai.org.
[pdf] [details]

On Structural Parameterizations of the Edge Disjoint Paths Problem
Robert Ganian and Sebastian Ordyniak and Ramanujan Sridharan
28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand (Yoshio Okamoto and Takeshi Tokuyama), volume 92 of LIPIcs, pages 36:1-36:13, 2017, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.
[pdf] [details]

Backdoor Treewidth for SAT
Robert Ganian, M. S. Ramanujan, Stefan Szeider
2017, Technical report AC-TR-17-014, Algorithms and Complexity Group, TU Wien.
[pdf] [details]

Combining Treewidth and Backdoors for CSP
Robert Ganian, M. S. Ramanujan, Stefan Szeider
34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) (Heribert Vollmer and Vall ́ee), volume 66 of Leibniz International Proceedings in Informatics (LIPIcs), pages 36:1-36:17, 2017, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
[pdf] [doi] [details]

Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
Robert Ganian and M. S. Ramanujan and Stefan Szeider
ACM Transactions on Algorithms, volume 13, number AC-TR-17-016, pages 29:1-29:32, 2017.
[pdf] [doi] [details]

Backdoor Treewidth for SAT
Robert Ganian, M. S. Ramanujan, Stefan Szeider
Theory and Applications of Satisfiability Testing - SAT 2017 - 20th International Conference, Melbourne, VIC, Australia, August 28 - September 1, 2017, Proceedings (Serge Gaspers and Toby Walsh), volume 10491 of Lecture Notes in Computer Science, pages 20-37, 2017, Springer Verlag.
[pdf] [doi] [details]

New Width Parameters for Model Counting
Robert Ganian, Stefan Szeider
Theory and Applications of Satisfiability Testing - SAT 2017 - 20th International Conference, Melbourne, VIC, Australia, August 28 - September 1, 2017, Proceedings (Serge Gaspers and Toby Walsh), volume 10491 of Lecture Notes in Computer Science, pages 38-52, 2017, Springer Verlag.
[pdf] [doi] [details]

New Width Parameters for Model Counting
Robert Ganian, Stefan Szeider
2017, Technical report AC-TR-17-013, Algorithms and Complexity Group, TU Wien.
[pdf] [details]

2016

Model Checking Existential Logic on Partially Ordered Sets
Simone Bova, Robert Ganian, Stefan Szeider
ACM Transactions on Computational Logic, volume 17, number 2, 2016.
[doi] [details]

Quantified Conjunctive Queries on Partially Ordered Sets
Simone Bova, Robert Ganian, Stefan Szeider
Theoretical Computer Science, volume 618, pages 72-84, 2016.
[pdf] [doi] [details]

A Single-Exponential Fixed-Parameter Algorithm for Distance-Hereditary Vertex Deletion
Eduard Eiben and Robert Ganian and O-joung Kwon
Mathematical Foundations of Computer Science 2016 - 41st International Symposium, MFCS 2016 (Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier), volume 58 of LIPIcs, pages 34:1-34:14, 2016, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.
[pdf] [details]

Using Decomposition-Parameters for QBF: Mind the Prefix!
Eduard Eiben and Robert Ganian and Sebastian Ordyniak
Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (Dale Schuurmans and Michael P. Wellman), pages 964-970, 2016, AAAI Press.
[pdf] [details]

Counting Linear Extensions: Parameterizations by Treewidth
Eduard Eiben, Robert Ganian, Kustaa Kangas, Sebastian Ordyniak
24th European Symposium of Algorithms, ESA 2016, volume 57 of LIPIcs, pages 39:1-39:18, 2016, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.
[pdf] [details]

On Existential MSO and its Relation to ETH
Robert Ganian, Ronald de Haan, Iyad Kanj, Stefan Szeider
41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) (Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier), volume 58 of Leibniz International Proceedings in Informatics (LIPIcs), pages 42:1-42:14, 2016, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
[pdf] [doi] [details]

Are There Any Good Digraph Measures?
Robert Ganian, Petr Hlinen ́y, Joachim Kneis, Daniel Meister, Jan Obdrz\ĺek, Peter Rossmanith, Somnath Sikdar
Journal of Combinatorial Theory, Series B, volume 116, pages 250-286, 2016.
[details]

FO Model Checking of Interval Graphs
Robert Ganian, Petr Hlinen ́y, Daniel Kr\ál, Jan Obdrz'ék, Jarett Schwartz, Jakub Teska
Logical Methods in Computer Science, volume 11, number 4, 2016.
[pdf] [details]

Polynomial-Time Construction of Optimal MPI Derived Datatype Trees
Robert Ganian and Martin Kalany and Stefan Szeider and Jesper Larsson Träff
2016 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2016, Chicago, IL, USA, May 23-27, 2016, pages 638-647, 2016, IEEE Computer Society.
[pdf] [doi] [details]

The Complexity Landscape of Decompositional Parameters for ILP
Robert Ganian and Sebastian Ordyniak
Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (Dale Schuurmans and Michael P. Wellman), pages 710-716, 2016, AAAI Press.
[pdf] [details]

Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
Robert Ganian, M. S. Ramanujan, Stefan Szeider
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1670-1681, 2016.
[pdf] [doi] [details]

Backdoors to Tractable Valued CSP
Robert Ganian, M.S. Ramanujan, Stefan Szeider
Principles and Practice of Constraint Programming - 22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings (Michel Rueher), volume 9892 of Lecture Notes in Computer Science, pages 233-250, 2016, Springer Verlag.
[pdf] [[doi]](https://doi.org/10.1007/978-3-319-44953-1 16) [details]

Meta-Kernelization with Structural Parameters
Robert Ganian, Friedrich Slivovsky, Stefan Szeider
Journal of Computer and System Sciences, volume 82, number 2, pages 333-346, 2016.
[pdf] [doi] [details]

On the Complexity Landscape of Connected f-factor Problems
Robert Ganian, N.S. Narayanaswamy, Sebastian Ordyniak, C.S. Rahul, Ramanujan M. S.
Mathematical Foundations of Computer Science 2016 - 41st International Symposium, MFCS 2016 (Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier), pages 41:1-41:14, 2016, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.
[pdf] [details]

2015

On the Complexity of Rainbow Coloring Problems
Eduard Eiben, Robert Ganian, Juho Lauri
Combinatorial Algorithms - 26th International Workshop, IWOCA 2015, Verona, Italy, October 5-7, 2015, Revised Selected Papers (Zsuzsanna Lipták and William F. Smyth), pages 209-220, 2015.
[pdf] [doi] [details]

Solving Problems on Graphs of High Rank-Width
Eduard Eiben, Robert Ganian, Stefan Szeider
Algorithms and Data Structures Symposium (WADS 2015), August 5-7, 2015, University of Victoria, BC, Canada, pages 314-326, 2015, Springer Verlag.
[pdf] [doi] [details]

Meta-Kernelization using Well-Structured Modulators
Eduard Eiben, Robert Ganian, Stefan Szeider
Parameterized and Exact Computation - 10th International Symposium, IPEC 2014, Patras, Greece, September 16-18, 2015. Revised Selected Papers (Thore Husfeldt and Iyad A. Kanj), volume 43 of LIPIcs, pages 114-126, 2015.
[pdf] [doi] [details]

Improving Vertex Cover as a Graph Parameter
Robert Ganian
Discrete Mathematics & Theoretical Computer Science, volume 17, number 2, pages 77-100, 2015.
[details]

Algorithmic Applications of Tree-Cut Width
Robert Ganian, Eun Jung Kim, Stefan Szeider
Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II, volume 9235 of Lecture Notes in Computer Science, pages 348-360, 2015, Springer Verlag.
[pdf] [doi] [details]

Community Structure Inspired Algorithms for SAT and #SAT
Robert Ganian, Stefan Szeider
18th International Conference on Theory and Applications of Satisfiability Testing (SAT 2015), September 24-27, 2015, Austin, Texas (Marijn Heule and Sean Weaver), pages 223-237, 2015, Springer Verlag.
[pdf] [doi] [details]

2014

Model checking existential logic on partially ordered sets
Simone Bova, Robert Ganian, Stefan Szeider
Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS ‘14, Vienna, Austria, July 14 - 18, 2014 (Thomas A. Henzinger and Dale Miller), pages 21:1-21:10, 2014, ACM.
[pdf] [doi] [details]

Quantified Conjunctive Queries on Partially Ordered Sets
Simone Bova, Robert Ganian, Stefan Szeider
Parameterized and Exact Computation - 9th International Symposium, IPEC 2014, Wroclaw, Poland, September 10-12, 2014. Revised Selected Papers (Marek Cygan and Pinar Heggernes), volume 8894 of Lecture Notes in Computer Science, pages 122-134, 2014, Springer Verlag.
[pdf] [doi] [details]

Digraph width measures in parameterized algorithmics
Robert Ganian and Petr Hlinený and Joachim Kneis and Alexander Langer and Jan Obdrzálek and Peter Rossmanith
Discrete Applied Mathematics, volume 168, pages 88-107, 2014.
[details]

Lower bounds on the complexity of MSO1 model-checking
Robert Ganian and Petr Hlinený and Alexander Langer and Jan Obdrzálek and Peter Rossmanith and Somnath Sikdar
J. Comput. Syst. Sci., volume 80, number 1, pages 180-194, 2014.
[details]

2013

Cops-and-robbers: remarks and problems
Michel Boyer, Sif El Harti, Amal El Ouarari and Robert Ganian, Tomas Gavenciak, Gena Hahn and Carsten Moldenauer, Ignaz Rutter, Benoit Theriault, Martin Vatshelle
Journal of Combinatorial Mathematics and Combinatorial Computing, volume 85, pages 141-159, 2013.
[details]

FO Model Checking of Interval Graphs
Robert Ganian and Petr Hlinený and Daniel Král’ and Jan Obdrzálek and Jarett Schwartz and Jakub Teska
Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part II, volume 7966 of Lecture Notes in Computer Science, pages 250-262, 2013, Springer.
[details]

Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width
Robert Ganian and Petr Hlinený and Jan Obdrzálek
Fundam. Inform., volume 123, number 1, pages 59-76, 2013.
[details]

A unified approach to polynomial algorithms on graphs of bounded (bi-)rank-width
Robert Ganian and Petr Hlinený and Jan Obdrzálek
Eur. J. Comb., volume 34, number 3, pages 680-701, 2013.
[details]

Expanding the Expressive Power of Monadic Second-Order Logic on Restricted Graph Classes
Robert Ganian and Jan Obdrzálek
Combinatorial Algorithms - 24th International Workshop, IWOCA 2013, Rouen, France, July 10-12, 2013, Revised Selected Papers, volume 8288 of Lecture Notes in Computer Science, pages 164-177, 2013, Springer.
[details]

Meta-kernelization with Structural Parameters
Robert Ganian and Friedrich Slivovsky and Stefan Szeider
Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings (Krishnendu Chatterjee and Jiri Sgall), volume 8087 of Lecture Notes in Computer Science, pages 457-468, 2013, Springer Verlag.
[doi] [details]

2012

Lower Bounds on the Complexity of MSO1 Model-Checking
Robert Ganian and Petr Hlinený and Alexander Langer and Jan Obdrzálek and Peter Rossmanith and Somnath Sikdar
29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th - March 3rd, 2012, Paris, France, volume 14 of LIPIcs, pages 326-337, 2012, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.
[details]

When Trees Grow Low: Shrubs and Fast MSO1
Robert Ganian and Petr Hlinený and Jaroslav Nesetril and Jan Obdrzálek and Patrice Ossona de Mendez and Reshma Ramadurai
Mathematical Foundations of Computer Science 2012 - 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012. Proceedings, volume 7464 of Lecture Notes in Computer Science, pages 419-430, 2012, Springer.
[details]

2011

New Results on the Complexity of the Max- and Min-Rep Problems
Robert Ganian
SOFSEM 2011: Theory and Practice of Computer Science - 37th Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 22-28, 2011. Proceedings, volume 6543 of Lecture Notes in Computer Science, pages 238-247, 2011, Springer.
[details]

Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
Robert Ganian
Parameterized and Exact Computation - 6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers, volume 7112 of Lecture Notes in Computer Science, pages 259-271, 2011, Springer.
[details]

Clique-width: When Hard Does Not Mean Impossible
Robert Ganian and Petr Hlinený and Jan Obdrzálek
28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011, March 10-12, 2011, Dortmund, Germany, volume 9 of LIPIcs, pages 404-415, 2011, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.
[details]

2010

Thread Graphs, Linear Rank-Width and Their Algorithmic Applications
Robert Ganian
Combinatorial Algorithms - 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers, volume 6460 of Lecture Notes in Computer Science, pages 38-42, 2010, Springer.
[details]

Are There Any Good Digraph Width Measures?
Robert Ganian and Petr Hliněný and Joachim Kneis and Daniel Meister and Jan Obdrzálek and Peter Rossmanith and Somnath Sikdar
Parameterized and Exact Computation - 5th International Symposium, IPEC 2010, Chennai, India, December 13-15, 2010. Proceedings, volume 6478 of Lecture Notes in Computer Science, pages 135-146, 2010, Springer.
[details]

New Results on the Complexity of Oriented Colouring on Restricted Digraph Classes
Robert Ganian and Petr Hlinený
SOFSEM 2010: Theory and Practice of Computer Science, 36th Conference on Current Trends in Theory and Practice of Computer Science, Spindleruv Mlýn, Czech Republic, January 23-29, 2010. Proceedings, volume 5901 of Lecture Notes in Computer Science, pages 428-439, 2010, Springer.
[details]

On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
Robert Ganian and Petr Hlinený
Discrete Applied Mathematics, volume 158, number 7, pages 851-867, 2010.
[details]

Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width
Robert Ganian and Petr Hlinený and Jan Obdrzálek
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010, December 15-18, 2010, Chennai, India, volume 8 of LIPIcs, pages 73-83, 2010, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.
[details]

2009

The Parameterized Complexity of Oriented Colouring
Robert Ganian
Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, MEMICS 2009, November 13-15, 2009, Prestige Hotel, Znojmo, Czech Republic, 2009, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany.
[details]

On Digraph Width Measures in Parameterized Algorithmics
Robert Ganian and Petr Hliněný and Joachim Kneis and Alexander Langer and Jan Obdrzálek and Peter Rossmanith
Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10-11, 2009, Revised Selected Papers, volume 5917 of Lecture Notes in Computer Science, pages 185-197, 2009, Springer.
[details]

Better Polynomial Algorithms on Graphs of Bounded Rank-Width
Robert Ganian and Petr Hliněný
Combinatorial Algorithms, 20th International Workshop, IWOCA 2009, Hradec nad Moravicí, Czech Republic, June 28-July 2, 2009, Revised Selected Papers, pages 266-277, 2009, Springer.
[details]

2008

Automata approach to graphs of bounded rank-width
Robert Ganian, Petr Hlinený
Proceedings of the 19th International Workshop on Combinatorial Algorithms, IWOCA 2008, September 13-15, 2008, Nagoya, Japan, pages 4-15, 2008, College Publications.
[details]