Technical Reports

81 results

2021
[81]	Hardness and Optimality in QBF Proof Systems Modulo NP Leroy Chew 2021, Technical report AC-TR-21-013, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[80]	Davis and Putnam Meet Henkin: Solving DQBF with Resolution Joshua Blinkhorn, Tomáš Peitl, Friedrich Slivovsky 2021, Technical report AC-TR-21-012, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[79]	Proof Complexity of Symbolic QBF Reasoning Stefan Mengel, Friedrich Slivovsky 2021, Technical report AC-TR-21-011, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[78]	Certified DQBF Solving by Definition Extraction Franz-Xaver Reichl, Friedrich Slivovsky, Stefan Szeider 2021, Technical report AC-TR-21-010, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[77]	Solving the Longest Common Subsequence Problem Concerning Non-uniform Distributions of Letters in Input Strings Bojan Nikolic, Kartelj Aleksandar, Marko Djukanovic, Milana Grbic, Christian Blum, Guenther Raidl 2021, Technical report AC-TR-21-009, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[76]	Solving the Generalized Constrained Longest Common Subsequence Problem with Many Pattern Strings Marko Djukanovic, Kartelj Aleksandar, Dragan Matic, Milana Grbic, Christian Blum, Guenther Raidl 2021, Technical report AC-TR-21-008, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[75]	The Parameterized Complexity of Clustering Incomplete Data Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak, Stefan Szeider 2021, Technical report AC-TR-21-007, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[74]	A General Cooperative Optimization Approach for Distributing Service Points in Mobility Applications Thomas Jatschka, Günther Raidl, Tobias Rodemann 2021, Technical report AC-TR-21-006, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[73]	Two new Mixed-Integer Linear Programming Models for Solving the Multidimensional Multi-Way Number Partitioning Problem Bojan Nikolic, Marko Djukanovic, Dragan Matic 2021, Technical report AC-TR-21-005, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[72]	Fixed-Parameter Tractability Marko Samer, Stefan Szeider 2021, Technical report AC-TR-21-004, Algorithms and Complexity Group, TU Wien. Note: Chapter 17, Handbook of Satisfiability, 2nd Edition, 2021 [bibtex] [pdf]
[71]	SAT-based Decision Tree Learning for Large Data Sets André Schidler, Stefan Szeider 2021, Technical report AC-TR-21-003, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[70]	Parameterized Complexity of Small Decision Tree Learning Sebastian Ordyniak, André Schidler, Stefan Szeider 2021, Technical report AC-TR-21-002, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[69]	Backdoor DNFs Sebastian Ordyniak, André Schidler, Stefan Szeider 2021, Technical report AC-TR-21-001, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
2020
[68]	Formalizing Graph Trail Properties in Isabelle/HOL Laura Kovács, Hanna Lachnitt, Stefan Szeider 2020, Technical report AC-TR-20-012, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[67]	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. [bibtex] [pdf]
[66]	Breaking Symmetries with RootClique and LexTopsort Johannes K. Fichte, Markus Hecher, Stefan Szeider 2020, Technical report AC-TR-20-010, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[65]	MaxSAT-Based Postprocessing for Treedepth Vaidyanathan P. R., Stefan Szeider 2020, Technical report AC-TR-20-009, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[64]	Finding the Hardest Formulas for Resolution Tomáš Peitl, Stefan Szeider 2020, Technical report AC-TR-20-008, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[63]	Short Q-Resolution Proofs with Homomorphisms Ankit Shukla, Friedrich Slivovsky, Stefan Szeider 2020, Technical report AC-TR-20-007, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[62]	A Faster Algorithm for Propositional Model Counting Parameterized by Incidence Treewidth Friedrich Slivovsky, Stefan Szeider 2020, Technical report AC-TR-20-006, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[61]	Threshold Treewidth and Hypertree Width Robert Ganian, Andre Schidler, Manuel Sorge, Stefan Szeider 2020, Technical report AC-TR-20-005, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[60]	An A* Search Algorithm for the Constrained Longest Common Subsequence Problem Marko Djukanovic, Christoph Berger, Günther R. Raidl, Christian Blum 2020, Technical report AC-TR-20-004, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[59]	Solving Longest Common Subsequence Problems via a Transformation to the Maximum Clique Problem Christian Blum, Marko Djukanovic, Alberto Santini, Hua Jiang, Chu-Min Li, Felipe Manya, Günther R. Raidl 2020, Technical report AC-TR-20-003, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[58]	On the Parameterized Complexity of Clustering Robert Ganian, Iyad Kanj, Sebastian Ordyniak, Stefan Szeider 2020, Technical report AC-TR-20-002, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[57]	Computing Optimal Hypertree Decompositions André Schidler, Stefan Szeider 2020, Technical report AC-TR-20-001, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
2019
[56]	A SAT Approach to Branchwidth Neha Lodha, Sebastian Ordyniak, Stefan Szeider 2019, Technical report AC-TR-19-010, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[55]	The Parameterized Complexity of Cascading Portfolio Scheduling Eduard Eiben, Robert Ganian, Iyad Kanj, Stefan Szeider 2019, Technical report AC-TR-19-009, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[54]	Finding Longest Common Subsequences: New A* Anytime Results Marko Djukanovic, Günther R. Raidl, Christian Blum 2019, Technical report AC-TR-19-008, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[53]	A Lower Bound for the Smallest Uniquely Hamiltonian Planar Graph with Minimum Degree Three Benedikt Klocker, Herbert Fleischner, Günther R. Raidl 2019, Technical report AC-TR-19-007, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[52]	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. [bibtex] [pdf]
[51]	Combining Resolution-Path Dependencies with Dependency Learning Tomáš Peitl, Friedrich Slivovsky, Stefan Szeider 2019, Technical report AC-TR-19-005, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[50]	Proof Complexity of Fragments of Long-Distance Q-resolution Tomáš Peitl, Friedrich Slivovsky, Stefan Szeider 2019, Technical report AC-TR-19-004, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[49]	Multivalued Decision Diagrams for Prize-Collecting Job Sequencing with One Common and Multiple Secondary Resources Johannes Maschler, Günther Raidl 2019, Technical report AC-TR-19-003, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[48]	A* Search for Prize-Collecting Job Sequencing with One Common and Multiple Secondary Resources Matthias Horn, Günther Raidl, Elina Rönnberg 2019, Technical report AC-TR-19-002, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[47]	SAT-Encodings for Treecut Width and Treedepth Robert Ganian, Neha Lodha, Sebastian Ordyniak, Stefan Szeider 2019, Technical report AC-TR-19-001, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
2018
[46]	Anytime Algorithms for the Longest Common Palindromic Subsequence Problem Marko Djukanovic, Günther Raidl, Christian Blum 2018, Technical report AC-TR-18-012, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[45]	A*-Based Construction of Decision Diagrams for a Prize-Collecting Scheduling Problem Matthias Horn, Johannes Maschler, Günther Raidl, Elina Rönnberg 2018, Technical report AC-TR-18-011, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[44]	A SAT Approach for Finding Sup-Transition-Minors Benedikt Klocker, Herbert Fleischner, Günther Raidl 2018, Technical report AC-TR-18-010, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[43]	A Model for Finding Transition-Minors Benedikt Klocker, Herbert Fleischner, Günther Raidl 2018, Technical report AC-TR-18-009, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[42]	On the Parameterized Complexity of (k,s)-SAT Daniël Paulusma, Stefan Szeider 2018, Technical report AC-TR-18-008, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[41]	Sum-of-Products with Default Values: Algorithms and Complexity Results Robert Ganian, Eun Jung Kim, Friedrich Slivovsky, Stefan Szeider 2018, Technical report AC-TR-18-007, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[40]	An SMT Approach to Fractional Hypertree Width Johannes K. Fichte, Markus Hecher, Neha Lodha, Stefan Szeider 2018, Technical report AC-TR-18-006, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[39]	Particle Therapy Patient Scheduling with Limited Starting Time Variations of Daily Treatments Johannes Maschler, Günther Raidl 2018, Technical report AC-TR-18-005, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[38]	Portfolio-Based Algorithm Selection for Circuit QBFs Holger H. Hoos, Tomáš Peitl, Friedrich Slivovsky, Stefan Szeider 2018, Technical report AC-TR-18-004, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[37]	Polynomial-Time Validation of QCDCL Certificates Tomáš Peitl, Friedrich Slivovsky, Stefan Szeider 2018, Technical report AC-TR-18-003, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[36]	Parameterized Algorithms for the Matrix Completion Problem Robert Ganian, Iyad Kanj, Sebastian Ordyniak, Stefan Szeider 2018, Technical report AC-TR-18-002, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[35]	Exact approaches for the directed network design problem with relays Markus Leitner, Ivana Ljubić, Martin Riedler, Mario Ruthmair 2018, Technical report AC-TR-18-001, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
2017
[34]	Herbrand Property: Finite Quasi-Herbrand Models and Lifting Chandra-Merlin Theorem to Quantified Conjunctive Queries Simone Bova, Fabio Mogavero 2017, Technical report AC-TR-17-017, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[33]	Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting Robert Ganian, M. S. Ramanujan, Stefan Szeider 2017, Technical report AC-TR-17-016, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[32]	SAT-Based Local Improvement for Finding Tree Decompositions of Small Width Johannes K. Fichte, Neha Lodha, Stefan Szeider 2017, Technical report AC-TR-17-015, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[31]	Backdoor Treewidth for SAT Robert Ganian, M. S. Ramanujan, Stefan Szeider 2017, Technical report AC-TR-17-014, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[30]	New Width Parameters for Model Counting Robert Ganian, Stefan Szeider 2017, Technical report AC-TR-17-013, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[29]	SAT-Encodings for Special Treewidth and Pathwidth Neha Lodha, Sebastian Ordyniak, Stefan Szeider 2017, Technical report AC-TR-17-012, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[28]	Dependency Learning for QBF Tomáš Peitl, Friedrich Slivovsky, Stefan Szeider 2017, Technical report AC-TR-17-011, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[27]	The Treewidth of Proofs Moritz Müller, Stefan Szeider 2017, Technical report AC-TR-17-010, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[26]	On the Parameterized Complexity of Finding Small Unsatisfiable Subsets of CNF Formulas and CSP Instances Ronald de Haan, Iyad Kanj, Stefan Szeider 2017, Technical report AC-TR-17-009, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[25]	Complexity Results for Aggregating Judgments using Scoring or Distance-Based Procedures Ronald de Haan, Marija Slavkovik 2017, Technical report AC-TR-17-008, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[24]	Pareto Optimal Allocation under Uncertain Preferences (Extended Abstract) Haris Aziz, Ronald de Haan, Baharak Rastegari 2017, Technical report AC-TR-17-007, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[23]	Stable Matching with Uncertain Pairwise Preferences Haris Aziz, Péter Biró, Tamás Fleiner, Serge Gaspers, Ronald de Haan, Nicholas Mattei, Baharak Rastegari 2017, Technical report AC-TR-17-006, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[22]	Complexity Results for Manipulation, Bribery and Control of the Kemeny Judgment Aggregation Procedure Ronald de Haan 2017, Technical report AC-TR-17-005, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[21]	Parameterized Complexity Classes Beyond Para-NP Ronald de Haan, Stefan Szeider 2017, Technical report AC-TR-17-004, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[20]	Long-Distance Q-Resolution with Dependency Schemes Tomáš Peitl, Friedrich Slivovsky, Stefan Szeider 2017, Technical report AC-TR-17-003, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[19]	Free Weak Nilpotent Minimum Algebras Stefano Aguzzoli Simone Bova, Diego Valota 2017, Technical report AC-TR-17-002, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[18]	An Iterative Time-Bucket Refinement Algorithm for a High Resolution Resource-Constrained Project Scheduling Problem Martin Riedler, Thomas Jatschka, Johannes Maschler, Günther Raidl 2017, Technical report AC-TR-17-001, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
2016
[17]	Solving a Selective Dial-a-Ride Problem with Logic-based Benders Decomposition Martin Riedler, Günther Raidl 2016, Technical report AC-TR-16-007, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[16]	Succinctness of Languages for Judgment Aggregation Ulle Endriss, Umberto Grandi, Ronald de Haan, Jérôme Lang 2016, Technical report AC-TR-16-006, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[15]	Parameterized Complexity Results for Agenda Safety in Judgment Aggregation Ulle Endriss, Ronald de Haan, Stefan Szeider 2016, Technical report AC-TR-16-005, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[14]	A SAT Approach to Branchwidth Sebastian Ordyniak Neha Lodha, Stefan Szeider 2016, Technical report AC-TR-16-004, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[13]	Positive and Negative Results for Parameterized Compilability Simone Bova, Ronald de Haan, Neha Lodha, Stefan Szeider 2016, Technical report AC-TR-16-003, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[12]	Knowledge Compilation Meets Communication Complexity Simone Bova, Florent Capelli, Stefan Mengel, Friedrich Slivovsky 2016, Technical report AC-TR-16-002, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[11]	A Genetic Algorithm in Combination with a Solution Archive for Solving the Generalized Vehicle Routing Problem with Stochastic Demands Benjamin Biesinger, Bin Hu, Günther Raidl 2016, Technical report AC-TR-16-001, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
2015
[10]	Fixed-Parameter Tractable Reductions to SAT for Planning Ronald de Haan, Martin Kronegger, Andreas Pfandler 2015, Technical report AC-TR-15-011, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[9]	Complexity of the Winner Determination Problem in Judgment Aggregation: Kemeny, Slater, Tideman, Young Ulle Endriss, Ronald de Haan 2015, Technical report AC-TR-15-010, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[8]	Machine Characterizations for Parameterized Complexity Classes Beyond Para-NP Ronald de Haan, Stefan Szeider 2015, Technical report AC-TR-15-009, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[7]	First-Order Queries on Finite Abelian Groups Simone Bova, Barnaby Martin 2015, Technical report AC-TR-15-008, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[6]	The Complexity of Equivalence, Entailment, and Minimization in Existential Positive Logic Simone Bova, Hubie Chen 2015, Technical report AC-TR-15-007, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[5]	On Compiling CNFs into Structured Deterministic DNNFs Simone Bova, Florent Capelli, Stefan Mengel, Friedrich Slivovsky 2015, Technical report AC-TR-15-006, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[4]	Algorithmic Applications of Tree-Cut Width Robert Ganian, Eun Jung Kim, Stefan Szeider 2015, Technical report AC-TR-15-005, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[3]	Exact Approaches for Network Design Problems with Relays Markus Leitner, Ivana Ljubić, Martin Riedler, Mario Ruthmair 2015, Technical report AC-TR-15-003, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[2]	Parameterized Complexity Results for Symbolic Model Checking of Temporal Logics Ronald de Haan, Stefan Szeider 2015, Technical report AC-TR-15-002, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]
[1]	Community Structure Inspired Algorithms for SAT and #SAT Robert Ganian, Stefan Szeider 2015, Technical report AC-TR-15-001, Algorithms and Complexity Group, TU Wien. [bibtex] [pdf]