Technical Reports

81 results
2021
[81]Hardness and Optimality in QBF Proof Systems Modulo NP

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
, ,
2021, Technical report AC-TR-21-012, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[79]Proof Complexity of Symbolic QBF Reasoning
,
2021, Technical report AC-TR-21-011, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[78]Certified DQBF Solving by Definition Extraction
, ,
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
, , , , ,
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
, , , , ,
2021, Technical report AC-TR-21-008, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[75]The Parameterized Complexity of Clustering Incomplete Data
, , , ,
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
, ,
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
, ,
2021, Technical report AC-TR-21-005, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[72]Fixed-Parameter Tractability
,
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
,
2021, Technical report AC-TR-21-003, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[70]Parameterized Complexity of Small Decision Tree Learning
, ,
2021, Technical report AC-TR-21-002, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[69]Backdoor DNFs
, ,
2021, Technical report AC-TR-21-001, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
2020
[68]Formalizing Graph Trail Properties in Isabelle/HOL
, ,
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
, , ,
2020, Technical report AC-TR-20-011, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[66]Breaking Symmetries with RootClique and LexTopsort
, ,
2020, Technical report AC-TR-20-010, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[65]MaxSAT-Based Postprocessing for Treedepth
,
2020, Technical report AC-TR-20-009, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[64]Finding the Hardest Formulas for Resolution
,
2020, Technical report AC-TR-20-008, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[63]Short Q-Resolution Proofs with Homomorphisms
, ,
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
,
2020, Technical report AC-TR-20-006, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[61]Threshold Treewidth and Hypertree Width
, , ,
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
, , ,
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
, , , , , ,
2020, Technical report AC-TR-20-003, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[58]On the Parameterized Complexity of Clustering
, , ,
2020, Technical report AC-TR-20-002, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[57]Computing Optimal Hypertree Decompositions
,
2020, Technical report AC-TR-20-001, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
2019
[56]A SAT Approach to Branchwidth
, ,
2019, Technical report AC-TR-19-010, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[55]The Parameterized Complexity of Cascading Portfolio Scheduling
, , ,
2019, Technical report AC-TR-19-009, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[54]Finding Longest Common Subsequences: New A* Anytime Results
, ,
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
, ,
2019, Technical report AC-TR-19-007, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[52]A Join-Based Hybrid Parameter for Constraint Satisfaction
, ,
2019, Technical report AC-TR-19-006, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[51]Combining Resolution-Path Dependencies with Dependency Learning
, ,
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
, ,
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
,
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
, ,
2019, Technical report AC-TR-19-002, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[47]SAT-Encodings for Treecut Width and Treedepth
, , ,
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
, ,
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
, , ,
2018, Technical report AC-TR-18-011, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[44]A SAT Approach for Finding Sup-Transition-Minors
, ,
2018, Technical report AC-TR-18-010, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[43]A Model for Finding Transition-Minors
, ,
2018, Technical report AC-TR-18-009, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[42]On the Parameterized Complexity of (k,s)-SAT
,
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
, , ,
2018, Technical report AC-TR-18-007, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[40]An SMT Approach to Fractional Hypertree Width
, , ,
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
,
2018, Technical report AC-TR-18-005, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[38]Portfolio-Based Algorithm Selection for Circuit QBFs
, , ,
2018, Technical report AC-TR-18-004, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[37]Polynomial-Time Validation of QCDCL Certificates
, ,
2018, Technical report AC-TR-18-003, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[36]Parameterized Algorithms for the Matrix Completion Problem
, , ,
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
, , ,
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
,
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
, ,
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
, ,
2017, Technical report AC-TR-17-015, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[31]Backdoor Treewidth for SAT
, ,
2017, Technical report AC-TR-17-014, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[30]New Width Parameters for Model Counting
,
2017, Technical report AC-TR-17-013, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[29]SAT-Encodings for Special Treewidth and Pathwidth
, ,
2017, Technical report AC-TR-17-012, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[28]Dependency Learning for QBF
, ,
2017, Technical report AC-TR-17-011, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[27]The Treewidth of Proofs
,
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
, ,
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
,
2017, Technical report AC-TR-17-008, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[24]Pareto Optimal Allocation under Uncertain Preferences (Extended Abstract)
, ,
2017, Technical report AC-TR-17-007, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[23]Stable Matching with Uncertain Pairwise Preferences
, , , , , ,
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

2017, Technical report AC-TR-17-005, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[21]Parameterized Complexity Classes Beyond Para-NP
,
2017, Technical report AC-TR-17-004, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[20]Long-Distance Q-Resolution with Dependency Schemes
, ,
2017, Technical report AC-TR-17-003, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[19]Free Weak Nilpotent Minimum Algebras
,
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
, , ,
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
,
2016, Technical report AC-TR-16-007, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[16]Succinctness of Languages for Judgment Aggregation
, , ,
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
, ,
2016, Technical report AC-TR-16-005, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[14]A SAT Approach to Branchwidth
,
2016, Technical report AC-TR-16-004, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[13]Positive and Negative Results for Parameterized Compilability
, , ,
2016, Technical report AC-TR-16-003, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[12]Knowledge Compilation Meets Communication Complexity
, , ,
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
, ,
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
, ,
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
,
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
,
2015, Technical report AC-TR-15-009, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[7]First-Order Queries on Finite Abelian Groups
,
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
,
2015, Technical report AC-TR-15-007, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[5]On Compiling CNFs into Structured Deterministic DNNFs
, , ,
2015, Technical report AC-TR-15-006, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[4]Algorithmic Applications of Tree-Cut Width
, ,
2015, Technical report AC-TR-15-005, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[3]Exact Approaches for Network Design Problems with Relays
, , ,
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
,
2015, Technical report AC-TR-15-002, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]
[1]Community Structure Inspired Algorithms for SAT and #SAT
,
2015, Technical report AC-TR-15-001, Algorithms and Complexity Group, TU Wien.
[bibtex] [pdf]