Dr Sebastian Ordyniak
PhD
Department of Computer Science
Visiting academic
Full contact details
Dr Sebastian Ordyniak
Department of Computer Science
Department of Computer Science
- Profile
-
Dr Sebastian Ordyniak was a Lecturer in the Algorithms group at the University of Sheffield in the Department of Computer Science until August 2020. Before coming to Sheffield, he obtained his Diplom and Ph.D. from the Humboldt University Berlin and the University of Oxford respectively. He has held postdoc positions at the TU Wien in the group of Prof. Stefan Szeider, and at the Masaryk University Brno in the group of Prof. Petr Hliněný.
- Research interests
-
Dr Ordyniak's research focus lies in the development and analysis of efficient algorithms for hard computational problems that arise in practical applications, as well as the establishment of theoretical limits of algorithmic approaches. Namely, he considers problems arising in the areas of Combinatorial Optimisation, Artificial Intelligence, and Logic.
His main interest lies in the development of so-called parameterised algorithms, ie exact algorithms that are tailor-suited not only to a specific problem but to a particular class of problem instances, which are often characterised by exhibiting a certain kind of structure. The main advantage of these algorithms is that they are usually more efficient than general purpose algorithms on real-world instances.
- Publications
-
Journal articles
- The complexity landscape of decompositional parameters for ILP : programs with few global variables and constraints. Artificial Intelligence, 300.
- On structural parameterizations of the bounded-degree vertex deletion problem. Algorithmica.
- Using decomposition-parameters for QBF: Mind the prefix!. Journal of Computer and System Sciences, 110, 1-21. View this article in WRRO
- Solving integer linear programs by exploiting variable-constraint interactions : a survey. Algorithms, 12(12). View this article in WRRO
- A SAT approach to branchwidth. ACM Transactions on Computational Logic, 20(3). View this article in WRRO
- On the complexity landscape of connected f-factor problems. Algorithmica, 81(6), 2606-2632. View this article in WRRO
- Counting Linear Extensions: Parameterizations by Treewidth. Algorithmica, 81(4), 1657-1683. View this article in WRRO
- Backdoors to planning. Artificial Intelligence, 269, 49-75. View this article in WRRO
- Backdoors for Linear Temporal Logic. Algorithmica, 81(2), 476-496. View this article in WRRO
- SAT-Encodings for Treecut Width and Treedepth.. CoRR, abs/1911.12995.
- Parameterized Algorithms for MILPs with Small Treedepth.. CoRR, abs/1912.03501.
- On Clustering Incomplete Data.. CoRR, abs/1911.01465.
- Group activity selection with few agent types. Leibniz International Proceedings in Informatics, LIPIcs, 144.
- The Power of Cut-Based Parameters for Computing Edge Disjoint Paths, 190-204.
- The complexity landscape of decompositional parameters for ILP. Artificial Intelligence, 257, 61-71. View this article in WRRO
- The Complexity Landscape of Decompositional Parameters for ILP.. CoRR, abs/1809.00585.
- First order limits of sparse graphs: Plane trees and path-width. Random Structures & Algorithms, 50(4), 612-635.
- Backdoors into heterogeneous classes of SAT and CSP. Journal of Computer and System Sciences, 85, 38-56. View this article in WRRO
- Kernelization using structural parameters on sparse graph classes. Journal of Computer and System Sciences, 84, 219-242. View this article in WRRO
- Small Resolution Proofs for QBF using Dependency Treewidth.. CoRR, abs/1711.02120.
- On Structural Parameterizations of the Edge Disjoint Paths Problem.. CoRR, abs/1711.02076.
- Tree-depth and vertex-minors. European Journal of Combinatorics, 56, 46-56.
- A Parameterized Study of Maximum Generalized Pattern Matching Problems. Algorithmica, 75(1), 1-26. View this article in WRRO
- Complexity and monotonicity results for domination games. Theoretical Computer Science, 628, 1-29.
- Strong Backdoors for Linear Temporal Logic.. CoRR, abs/1602.04934.
- Backdoors to q-Horn. Algorithmica, 74(1), 540-557.
- A complete parameterized complexity analysis of bounded planning. Journal of Computer and System Sciences, 81(7), 1311-1332.
- On finding optimal polytrees. Theoretical Computer Science, 592, 49-58.
- Parameterized Complexity Results for Exact Bayesian Network Structure Learning.. CoRR, abs/1402.0558.
- A Parameterized Study of Maximum Generalized Pattern Matching Problems.. CoRR, abs/1409.2398.
- The Complexity of Repairing, Adjusting, and Aggregating of Extensions in Abstract Argumentation, 158-175.
- Satisfiability of acyclic and almost acyclic CNF formulas. Theoretical Computer Science, 481, 85-99.
- Parameterized Algorithms for Modular-Width.. CoRR, abs/1308.2858.
- Upper and Lower Bounds for Weak Backdoor Set Detection, 394-402.
- Augmenting tractable fragments of abstract argumentation. Artificial Intelligence, 186, 157-173.
- Parameterized Complexity and Kernel Bounds for Hard Planning Problems. CoRR, abs/1211.0479.
- Algorithms and Complexity Results for Exact Bayesian Structure Learning. CoRR, abs/1203.3501.
- Don't be strict in local search!. Proceedings of the National Conference on Artificial Intelligence, 1, 486-492.
- The complexity of planning revisited - A parameterized analysis. Proceedings of the National Conference on Artificial Intelligence, 3, 1735-1741.
- Digraph decompositions and monotonicity in digraph searching. Theoretical Computer Science, 412(35), 4688-4703.
- Algorithms and complexity results for persuasive argumentation. Artificial Intelligence, 175(9-10), 1722-1736.
- Faster Existential FO Model Checking on Posets. Logical Methods in Computer Science, 11(4).
- Parameterized Complexity Results for Exact Bayesian Network Structure Learning. Journal of Artificial Intelligence Research, 46, 263-302.
Chapters
- Integer Programming and Incidence Treedepth, Integer Programming and Combinatorial Optimization (pp. 194-204). Springer International Publishing
- Backdoor Sets for CSP. In Krokhin AA & Zivny S (Ed.), The Constraint Satisfaction Problem (pp. 137-157). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
- Width-Measures for Directed Graphs and Algorithmic Applications, Discrete Mathematics and Its Applications (pp. 181-231). Chapman and Hall/CRC
- Quantitative Graph Theory Chapman and Hall/CRC
Conference proceedings papers
- Parameterized pre-coloring extension and list coloring problems. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 154. Montpellier, France, 10 March 2020 - 13 March 2020. View this article in WRRO
- A join-based hybrid parameter for constraint satisfaction. Principles and Practice of Constraint Programming (pp 195-212). Stamford, CT, USA, 30 September 2019 - 4 October 2019. View this article in WRRO
- A Refined Understanding of Cost-optimal Planning with Polytree Causal Graphs. Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, 10 August 2019 - 16 August 2019.
- Solving integer quadratic programming via explicit and structural restrictions. Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, Vol. 33 (pp 1477-1484). Honolulu,Hawaii, USA, 27 January 2019 - 1 February 2019. View this article in WRRO
- SAT-encodings for treecut width and treedepth. 2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX) (pp 117-129). San Diego, California, USA, 7 January 2019 - 8 January 2019. View this article in WRRO
- Small resolution proofs for QBF using dependency treewidth. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 96
- On structural parameterizations of the Bounded-Degree Vertex Deletion problem. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 96
- A Refined Understanding of Cost-Optimal Planning with Polytree Causal Graphs.. SOCS (pp 19-27)
- Unary Integer Linear Programming with Structural Restrictions. Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 13 July 2018 - 19 July 2018. View this article in WRRO
- Parameterized Algorithms for the Matrix Completion Problem.. ICML, Vol. 80 (pp 1642-1651) View this article in WRRO
- Novel Structural Parameters for Acyclic Planning Using Tree Embeddings. Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 13 July 2018 - 19 July 2018. View this article in WRRO
- A Structural Approach to Activity Selection. Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 13 July 2018 - 19 July 2018. View this article in WRRO
- Parameterized algorithms for the matrix completion problem. 35th International Conference on Machine Learning, ICML 2018, Vol. 4 (pp 2674-2683)
- On structural parameterizations of the edge disjoint paths problem. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 92
- Towards a polynomial kernel for directed feedback vertex set. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 83
- Backdoors for linear temporal logic. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 63
- Solving Integer Linear Programs with a Small Number of Global Variables and Constraints.. IJCAI (pp 607-613)
- Going beyond primal treewidth for (M)ILP. 31st AAAI Conference on Artificial Intelligence, AAAI 2017 (pp 815-821)
- SAT-Encodings for Special Treewidth and Pathwidth (pp 429-445)
- A SAT Approach to Branchwidth. Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, 19 August 2017 - 26 August 2017.
- Solving Integer Linear Programs with a Small Number of Global Variables and Constraints. Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, 19 August 2017 - 26 August 2017.
- Counting linear extensions: Parameterizations by treewidth. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 57
- On the complexity landscape of connected f-factor problems. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 58
- Directed elimination games. Discrete Applied Mathematics, Vol. 199 (pp 187-198)
- Clique-Width and Directed Width Measures for Answer-Set Programming.. ECAI, Vol. 285 (pp 1105-1113)
- Edge-Editing to a Dense and a Sparse Graph Class (pp 562-575)
- The complexity landscape of decompositional parameters for ILP. 30th AAAI Conference on Artificial Intelligence, AAAI 2016 (pp 710-716)
- Clique-width and directed width measures for answer-set Programming. Frontiers in Artificial Intelligence and Applications, Vol. 285 (pp 1105-1113)
- SOBRA - Shielding Optimization for BRAchytherapy (pp 309-320)
- A SAT Approach to Branchwidth (pp 179-195)
- FO Model Checking on Posets TOF Bounded Width. 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (pp 963-974)
- Variable-deletion backdoors to planning. Proceedings of the National Conference on Artificial Intelligence, Vol. 5 (pp 3305-3312)
- Parameterized Algorithms for Parity Games (pp 336-347)
- Backdoors to Planning. PROCEEDINGS OF THE TWENTY-EIGHTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE (pp 2300-2307)
- Backdoors into heterogeneous classes of SAT and CSP. Proceedings of the National Conference on Artificial Intelligence, Vol. 4 (pp 2652-2658)
- Finite Integer Index of Pathwidth and Treewidth (pp 258-269)
- Faster Existential FO Model Checking on Posets (pp 441-451)
- A Parameterized Study of Maximum Generalized Pattern Matching Problems (pp 270-281)
- Upper and Lower Bounds for Weak Backdoor Set Detection.. SAT, Vol. 7962 (pp 394-402)
- Backdoors to q-horn. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 20 (pp 67-79)
- The Complexity of Repairing, Adjusting, and Aggregating of Extensions in Abstract Argumentation.. TAFA, Vol. 8306 (pp 158-175)
- Parameterized Complexity and Kernel Bounds for Hard Planning Problems (pp 13-24)
- Parameterized Algorithms for Modular-Width (pp 163-176)
- Kernelization Using Structural Parameters on Sparse Graph Classes (pp 529-540)
- Don't Be Strict in Local Search!. AAAI
- On finding optimal polytrees. Proceedings of the National Conference on Artificial Intelligence, Vol. 1 (pp 750-756)
- The Complexity of Planning Revisited - A Parameterized Analysis.. AAAI
- Valued-based argumentation for tree-like value graphs. Frontiers in Artificial Intelligence and Applications, Vol. 245(1) (pp 378-389)
- Augmenting tractable fragments of abstract argumentation. IJCAI International Joint Conference on Artificial Intelligence (pp 1033-1038)
- Satisfiability of Acyclic and almost Acyclic CNF Formulas (II) (pp 47-60)
- Algorithms and complexity results for exact Bayesian structure learning. Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, UAI 2010 (pp 401-408)
- Algorithms and Complexity Results for Persuasive Argumentation.. COMMA, Vol. 216 (pp 311-322)
- Distance d-Domination Games (pp 308-319)
- Satisfiability of acyclic and almost acyclic CNF formulas. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 8 (pp 84-95)
- Algorithms and complexity results for persuasive argumentation. Frontiers in Artificial Intelligence and Applications, Vol. 216 (pp 311-322)
- Digraph Decompositions and Monotonicity in Digraph Searching (pp 336-347)
- On the Parameterized Complexity of Clustering Incomplete Data into Subspaces of Small Rank. Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 34(04) (pp 3906-3913)
- Parameterized Complexity of Envy-Free Resource Allocation in Social Networks. Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 34(05) (pp 7135-7142)
- The complexity landscape of decompositional parameters for ILP : programs with few global variables and constraints. Artificial Intelligence, 300.
- Professional activities and memberships
-
Member of the Algorithms research group