3 papers
cs.DM2026
Enumerating tuples of spanning trees
Rahul CS, Michal Wlodarczyk
Deciding whether a graph has k-edge-disjoint spanning trees is a well-studied problem. We consider the problem of enumerating all sets of spanning trees with polynomial delay. This…
cs.DS2025
Designing Compact ILPs via Fast Witness Verification
MichaÅ WÅodarczyk
The standard formalization of preprocessing in parameterized complexity is given by kernelization. In this work, we depart from this paradigm and study a different type of preproce…
cs.DS2024
Does Subset Sum Admit Short Proofs?
MichaÅ WÅodarczyk
We investigate the question whether Subset Sum can be solved by a polynomial-time algorithm with access to a certificate of length poly(k) where k is the maximal number of bits in…