Leírás
Abstract: There is a common method for solving various (combinatiorial)
optimization problems. The problem is modeled in a language, which can
be solved with a well known specialized software. Such methods are
usually using Linear Programming (LP), Constrain Programming (CP) or
SAT solvers. Due to Karp's famous paper we know that NP-complete
problems can be reduced to each other, so it is clear that different
NP-complete problems can be solved using a solver specialized to one
of those. The present talk shall focus on using graph modeling for
mathematical programming, and performing clique search on the
resulting auxiliary graph. We would like to present some thoughts on
whether and when such approach is good or bad; what methods can be
used to simplify the problem (symmetry breaking); if we can transform
the auxiliary graph into a simpler one; etc. We also will present a
special graph class that seems to be useful in this question, and
conclude some specialized transformations connected to it. As a direct
consequence we will prove that some well known problems are solvable
in polynomial time (2-SAT and 2-color problems).
Zoom link:
https://zoom.us/j/2961946869