On the parametrized complexity of Read-once refutations in UTVPI+ constraint systems

DOI10.1016/j.tcs.2021.05.007OpenAlexW3179772470MaRDI QIDQ2049975

Yanyan Li

Publication date: 27 August 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2021.05.007

zbMATH Keywords

network flowsbranchingparameterized complexitystrong exponential time hypothesisread-once refutationunit two variable per inequality constraints

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Uses Software

• Yices
• z3

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Certifying algorithms
• Infeasibility of instance compression and succinct PCPs for NP
• Some consequences of non-uniform conditions on uniform classes
• Optimal length resolution refutations of difference constraint systems
• The octagon abstract domain
• On problems without polynomial kernels
• The complexity of read-once resolution
• Finding read-once resolution refutations in systems of 2CNF clauses
• Iterative aggregation and disaggregation algorithm for pseudo-polynomial network flow models with side constraints
• Restricted cutting plane proofs in Horn constraint systems
• A polynomial time algorithm for read-once certification of linear infeasibility in UTVPI constraints
• A combinatorial algorithm for Horn programs
• A Multicommodity Network-Flow Problem with Side Constraints on Paths Solved by Column Generation
• Two Variables per Linear Inequality as an Abstract Domain
• Parametric dispatching of hard real-time tasks
• Kernelization
• Computational Complexity
• Formal Techniques, Modelling and Analysis of Timed and Fault-Tolerant Systems
• Frontiers of Combining Systems
• Parameterized Algorithms
• Fast and Flexible Difference Constraint Propagation for DPLL(T)

This page was built for publication: On the parametrized complexity of Read-once refutations in UTVPI+ constraint systems