parameterized complexity | Algorithms at UNSW

An important focus of our group is multivariate complexity analysis and algorithm design, a.k.a. parameterized complexity. The basic insight is that in many situations, one or more secondary measurements of problem instances or computational objectives, beyond the overall input size, govern a problem’s computational complexity.

selected papers

ICALP

Edouard Bonnet, Serge Gaspers, Antonin Lambilliotte, Stefan Rümmele, and Abdallah Saffidine

The Parameterized Complexity of Positional Games

In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, 2017

DOI arXiv Bib

@inproceedings{BonnetGLRS17,
  author = {Bonnet, Edouard and Gaspers, Serge and Lambilliotte, Antonin and R{\"{u}}mmele, Stefan and Saffidine, Abdallah},
  editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  title = {The Parameterized Complexity of Positional Games},
  booktitle = {44th International Colloquium on Automata, Languages, and Programming,
                    {ICALP} 2017, July 10-14, 2017, Warsaw, Poland},
  series = {LIPIcs},
  volume = {80},
  pages = {90:1--90:14},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year = {2017},
  url = {https://doi.org/10.4230/LIPIcs.ICALP.2017.90},
  doi = {10.4230/LIPIcs.ICALP.2017.90}
}

Math. Soc. Sci.

Haris Aziz, and Julián Mestre

Parametrized algorithms for random serial dictatorship

Mathematical Social Sciences, 2014

DOI arXiv Bib

@article{AzizM14,
  author = {Aziz, Haris and Mestre, Juli{\'{a}}n},
  title = {Parametrized algorithms for random serial dictatorship},
  journal = {Mathematical Social Sciences},
  volume = {72},
  pages = {1--6},
  year = {2014},
  url = {https://doi.org/10.1016/j.mathsocsci.2014.07.002},
  doi = {10.1016/J.MATHSOCSCI.2014.07.002}
}

FOCS

Serge Gaspers, and Stefan Szeider

Strong Backdoors to Bounded Treewidth SAT

In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, 2013

DOI arXiv Bib

@inproceedings{GaspersS13,
  author = {Gaspers, Serge and Szeider, Stefan},
  title = {Strong Backdoors to Bounded Treewidth {SAT}},
  booktitle = {54th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
                    2013, 26-29 October, 2013, Berkeley, CA, {USA}},
  pages = {489--498},
  publisher = {{IEEE} Computer Society},
  year = {2013},
  url = {https://doi.org/10.1109/FOCS.2013.59},
  doi = {10.1109/FOCS.2013.59}
}

AAAI

Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, Claude-Guy Quimper, and Toby Walsh

The Parameterized Complexity of Global Constraints

In Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, AAAI 2008, Chicago, Illinois, USA, July 13-17, 2008, 2008

URL arXiv Bib

@inproceedings{BessiereHHKQW08,
  author = {Bessiere, Christian and Hebrard, Emmanuel and Hnich, Brahim and Kiziltan, Zeynep and Quimper, Claude{-}Guy and Walsh, Toby},
  editor = {Fox, Dieter and Gomes, Carla P.},
  title = {The Parameterized Complexity of Global Constraints},
  booktitle = {Proceedings of the Twenty-Third {AAAI} Conference on Artificial Intelligence,
                    {AAAI} 2008, Chicago, Illinois, USA, July 13-17, 2008},
  pages = {235--240},
  publisher = {{AAAI} Press},
  year = {2008},
  url = {http://www.aaai.org/Library/AAAI/2008/aaai08-037.php}
}