Characteristics of implemented algorithms?

[bslavchev]

I'm quite lost as to the characteristics of each implemented algorithm. Specifically I am really interested in what each algorithm outputs - e.g. I can imagine the preprocessing algorithm doesn't output a solution at all, but what would it output if I ran it on a problem instance alone? Among the other algorithms - which ones are provably exact, which will output a "best until now" solution if they receive SIGTERM, which can never reach a provably exact solution even given all the time in the world?

[felix-salfelder]

On Wed, Jan 18, 2023 at 07:05:23AM -0800, Bobby Slavchev wrote: I can imagine the preprocessing algorithm doesn't output a solution at all, but what would it output if I ran it on a problem instance alone?

The preprocessor has a "get_treedec" (or so) method that assembles a decomposition from the preprocessed data. Iirc, "tdecomp --pp" prints it. It should be optimal up to a certain treewith (around 3 or 4?). (Your other questions are interesting, but I can't answer off the top of my head.)