Robert Ganian

 

Robert Ganian is a postdoctoral researcher at TU Wien, Vienna, Austria, and a member of the Algorithms and Complexity Group. His main research interests include parameterized algorithms and complexity, model checking, and structural decompositions.

He received his Ph.D. in 2012, has published over 55 articles in scientific journals and conference proceedings, and has an Erdős Number of 2.

Academic Activities:

• Organization co-chair of ALGO 2017 in Vienna; ALGO is an annual congress combining the premier algorithmic conference European Symposium on Algorithms and a number of other specialized conferences and workshops. (300+ participants)
• Organizer of the Parameterized Complexity Summer School (PCSS 2017) in Vienna. (100+ participants)
• Organizer of the workshop on Parameterized Complexity of Computational Reasoning (PCCR 2014) in Vienna. (40+ participants)
• Member of the organizing team of the Symposium on Structure in Hard Combinatorial Problems (STRUCTURE 2013) in Vienna. (40+ participants)
• Organization co-chair of the next Workshop on Graph Classes, Optimization, and Width Parameters (GROW 2019), to be held in Vienna.
• Chair of the award committee of the 2018 VCLA International Student Awards.
• Program Committee member of the 27th International Joint Conference on Articial Intelligence and the 23rd European Conference on Articial Intelligence (IJCAI-ECAI-2018).
• Guest Editor of the GROW 2017 Special Issue of Discrete Applied Mathematics.
• Invited by the organizers to give a series of tutorials at the European Summer School in Logic, Language and Information (ESSLLI 2017) in Toulouse. (Approximately 400 participants)
• Coordinator of FWF project P26696 X-TRACT.

Publications:
57 results

2018
[57]	Solving Problems on Graphs of High Rank-Width Eduard Eiben, Robert Ganian, Stefan Szeider Algorithmica, volume 80, number 2, pages 742–771, 2018. [bibtex] [pdf] [doi]
[56]	On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem Robert Ganian, Fabian Klute, Sebastian Ordyniak 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28–March 3, 2018, Caen, France (Rolf Neidermeier, Brigitte Vallée, eds.), 2018, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. Note: To appear [bibtex]
[55]	Parameterized Algorithms for the Matrix Completion Problem Robert Ganian, Iyad Kanj, Sebastian Ordyniak, Stefan Szeider Proceeding of ICML, the Thirty-fifth International Conference on Machine Learning, Stockholm, July 10–15, 2018, 2018. Note: to appear [bibtex] [pdf]
[54]	Small Resolution Proofs for QBF using Dependency Treewidth Eduard Eiben, Robert Ganian, Sebastian Ordyniak 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28–March 3, 2018, Caen, France (Rolf Neidermeier, Brigitte Vallée, eds.), 2018, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. Note: To appear [bibtex]
2017
[53]	Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting Robert Ganian, M. S. Ramanujan, Stefan Szeider ACM Transactions on Algorithms, volume 13, number 2, pages 29:1–29:32, 2017. [bibtex] [pdf] [doi]
[52]	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, Toby Walsh, eds.), volume 10491 of Lecture Notes in Computer Science, pages 38–52, 2017, Springer Verlag. [bibtex] [pdf] [doi]
[51]	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, Brigitte Vallée, eds.), volume 66 of Leibniz International Proceedings in Informatics (LIPIcs), pages 36:1–36:17, 2017, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. [bibtex] [pdf] [doi]
[50]	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, Toby Walsh, eds.), volume 10491 of Lecture Notes in Computer Science, pages 20–37, 2017, Springer Verlag. [bibtex] [pdf] [doi]
[49]	On Structural Parameterizations of the Edge Disjoint Paths Problem Robert Ganian, Sebastian Ordyniak, Ramanujan Sridharan 28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand (Yoshio Okamoto, Takeshi Tokuyama, eds.), volume 92 of LIPIcs, pages 36:1–36:13, 2017, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. [bibtex]
[48]	Solving Integer Linear Programs with a Small Number of Global Variables and Constraints Pavel Dvo\v rák, Eduard Eiben, Robert Ganian, Dušan Knop, Sebastian Ordyniak Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017 (Carles Sierra, ed.), pages 607–613, 2017, ijcai.org. [bibtex]
[47]	Going Beyond Primal Treewidth for (M)ILP Robert Ganian, Sebastian Ordyniak, 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. [bibtex] [pdf]
[46]	Towards a Polynomial Kernel for Directed Feedback Vertex Set Benjamin Bergougnoux, Eduard Eiben, Robert Ganian, Sebastian Ordyniak, M. S. Ramanujan 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, August 21-25, 2017 - Aalborg, Denmark (Kim G. Larsen, Hans L. Bodlaender, Jean-François Raskin, eds.), volume 83 of LIPIcs, pages 36:1–36:15, 2017, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. [bibtex]
2016
[45]	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. [bibtex] [pdf] [doi]
[44]	FO Model Checking of Interval Graphs Robert Ganian, Petr Hlinený, Daniel Král, Jan Obdrzálek, Jarett Schwartz, Jakub Teska Logical Methods in Computer Science, volume 11, number 4, 2016. [bibtex] [pdf]
[43]	Are There Any Good Digraph Measures? Robert Ganian, Petr Hlinený, Joachim Kneis, Daniel Meister, Jan Obdrzálek, Peter Rossmanith, Somnath Sikdar Journal of Combinatorial Theory, Series B, volume 116, pages 250–286, 2016. [bibtex]
[42]	Quantified Conjunctive Queries on Partially Ordered Sets Simone Bova, Robert Ganian, Stefan Szeider Theoretical Computer Science, volume 618, pages 72–84, 2016. [bibtex] [pdf] [doi]
[41]	Model Checking Existential Logic on Partially Ordered Sets Simone Bova, Robert Ganian, Stefan Szeider ACM Transactions on Computational Logic, volume 17, number 2, 2016. [bibtex] [doi]
[40]	Backdoors to Tractable Valued CSP Robert Ganian, Ramanujan M.S., Stefan Szeider Principles and Practice of Constraint Programming - 22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings (Michel Rueher, ed.), volume 9892 of Lecture Notes in Computer Science, pages 233–250, 2016, Springer Verlag. [bibtex] [pdf] [doi]
[39]	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. [bibtex] [pdf] [doi]
[38]	The Complexity Landscape of Decompositional Parameters for ILP Robert Ganian, Sebastian Ordyniak Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (Dale Schuurmans, Michael P. Wellman, eds.), pages 710–716, 2016, AAAI Press. [bibtex] [pdf]
[37]	Polynomial-Time Construction of Optimal MPI Derived Datatype Trees Robert Ganian, Martin Kalany, Stefan Szeider, 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. [bibtex] [pdf] [doi]
[36]	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, Anca Muscholl, Rolf Niedermeier, eds.), volume 58 of Leibniz International Proceedings in Informatics (LIPIcs), pages 42:1–42:14, 2016, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. [bibtex] [pdf] [doi]
[35]	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, Anca Muscholl, Rolf Niedermeier, eds.), pages 41:1–41:14, 2016, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. [bibtex] [pdf]
[34]	Counting Linear Extensions: Parameterizations by Treewidth Eduard Eiben, Robert Ganian, 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. [bibtex] [pdf]
[33]	Using Decomposition-Parameters for QBF: Mind the Prefix! Eduard Eiben, Robert Ganian, Sebastian Ordyniak Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (Dale Schuurmans, Michael P. Wellman, eds.), pages 964–970, 2016, AAAI Press. [bibtex] [pdf]
[32]	A Single-Exponential Fixed-Parameter Algorithm for Distance-Hereditary Vertex Deletion Eduard Eiben, Robert Ganian, O-joung Kwon Mathematical Foundations of Computer Science 2016 - 41st International Symposium, MFCS 2016 (Piotr Faliszewski, Anca Muscholl, Rolf Niedermeier, eds.), volume 58 of LIPIcs, pages 34:1–34:14, 2016, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. [bibtex] [pdf]
2015
[31]	Improving Vertex Cover as a Graph Parameter Robert Ganian Discrete Mathematics & Theoretical Computer Science, volume 17, number 2, pages 77–100, 2015. [bibtex]
[30]	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, Sean Weaver, eds.), pages 223-237, 2015, Springer Verlag. [bibtex] [pdf] [doi]
[29]	Parameterized Complexity of Asynchronous Border Minimization Robert Ganian, Martin Kronegger, Andreas Pfandler, Alexandru Popa Theory and Applications of Models of Computation - 12th Annual Conference, TAMC 2015, Singapore, May 18-20, 2015, Proceedings (Rahul Jain, Sanjay Jain, Frank Stephan, eds.), volume 9076 of Lecture Notes in Computer Science, pages 428–440, 2015, Springer Verlag. [bibtex] [pdf] [doi]
[28]	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. [bibtex] [pdf] [doi]
[27]	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, Iyad A. Kanj, eds.), volume 43 of LIPIcs, pages 114–126, 2015. [bibtex] [pdf] [doi]
[26]	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. [bibtex] [pdf] [doi]
[25]	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, William F. Smyth, eds.), pages 209–220, 2015. [bibtex] [pdf] [doi]
2014
[24]	Lower bounds on the complexity of MSO1 model-checking Robert Ganian, Petr Hlinený, Alexander Langer, Jan Obdrzálek, Peter Rossmanith, Somnath Sikdar J. Comput. Syst. Sci., volume 80, number 1, pages 180–194, 2014. [bibtex]
[23]	Digraph width measures in parameterized algorithmics Robert Ganian, Petr Hlinený, Joachim Kneis, Alexander Langer, Jan Obdrzálek, Peter Rossmanith Discrete Applied Mathematics, volume 168, pages 88–107, 2014. [bibtex]
[22]	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, Pinar Heggernes, eds.), volume 8894 of Lecture Notes in Computer Science, pages 122–134, 2014, Springer Verlag. [bibtex] [pdf] [doi]
[21]	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, Dale Miller, eds.), pages 21:1–21:10, 2014, ACM. [bibtex] [pdf] [doi]
2013
[20]	Cops-and-robbers: remarks and problems Michel Boyer, Sif El Harti, Amal El Ouarari, Robert Ganian, Tomas Gavenciak, Gena Hahn, Carsten Moldenauer, Ignaz Rutter, Benoit Theriault, Martin Vatshelle Journal of Combinatorial Mathematics and Combinatorial Computing, volume 85, pages 141–159, 2013. [bibtex]
[19]	A unified approach to polynomial algorithms on graphs of bounded (bi-)rank-width Robert Ganian, Petr Hlinený, Jan Obdrzálek Eur. J. Comb., volume 34, number 3, pages 680–701, 2013. [bibtex]
[18]	Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width Robert Ganian, Petr Hlinený, Jan Obdrzálek Fundam. Inform., volume 123, number 1, pages 59–76, 2013. [bibtex]
[17]	Meta-kernelization with Structural Parameters Robert Ganian, Friedrich Slivovsky, Stefan Szeider Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings (Krishnendu Chatterjee, Jiri Sgall, eds.), volume 8087 of Lecture Notes in Computer Science, pages 457-468, 2013, Springer Verlag. [bibtex] [doi]
[16]	Expanding the Expressive Power of Monadic Second-Order Logic on Restricted Graph Classes Robert Ganian, 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 Verlag. [bibtex]
[15]	FO Model Checking of Interval Graphs Robert Ganian, Petr Hlinený, Daniel Král', Jan Obdrzálek, Jarett Schwartz, 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 Verlag. [bibtex]
2012
[14]	When Trees Grow Low: Shrubs and Fast MSO1 Robert Ganian, Petr Hlinený, Jaroslav Nesetril, Jan Obdrzálek, Patrice Ossona de Mendez, 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 Verlag. [bibtex]
[13]	Lower Bounds on the Complexity of MSO1 Model-Checking Robert Ganian, Petr Hlinený, Alexander Langer, Jan Obdrzálek, Peter Rossmanith, 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. [bibtex]
2011
[12]	Clique-width: When Hard Does Not Mean Impossible Robert Ganian, Petr Hlinený, 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. [bibtex]
[11]	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 Verlag. [bibtex]
[10]	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 Verlag. [bibtex]
2010
[9]	On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width Robert Ganian, Petr Hlinený Discrete Applied Mathematics, volume 158, number 7, pages 851–867, 2010. [bibtex]
[8]	Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width Robert Ganian, Petr Hlinený, 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. [bibtex]
[7]	New Results on the Complexity of Oriented Colouring on Restricted Digraph Classes Robert Ganian, 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 Verlag. [bibtex]
[6]	Are There Any Good Digraph Width Measures? Robert Ganian, Petr Hlin\v ený, Joachim Kneis, Daniel Meister, Jan Obdrzálek, Peter Rossmanith, 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 Verlag. [bibtex]
[5]	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 Verlag. [bibtex]
2009
[4]	Better Polynomial Algorithms on Graphs of Bounded Rank-Width Robert Ganian, Petr Hlinený 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 Verlag. [bibtex]
[3]	On Digraph Width Measures in Parameterized Algorithmics Robert Ganian, Petr Hlin\v ený, Joachim Kneis, Alexander Langer, Jan Obdrzálek, 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 Verlag. [bibtex]
[2]	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. [bibtex]
2008
[1]	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. [bibtex]