| |
|
Description: |
Consider the problem of computing the number of perfect matchings in a bipartite graph. Since this problem is #P-complete, likely only for special classes do polynomial-time algorithms exist. One approach is by attempting to reduce the underlying (hard) permanent-computation
to some (easy) determinant-computation. This approach goes back to an exercise posed by Poly in 1913, and can be expressed in many, closely related ways, for example as the "even digraph" problem (is there an
even directed cycle in a given directed graph?), or whether some square matrix is sign-non-singular (are all matrices with the same sign pattern invertible?).
In [Robertson,Seymour,Thomas] and in [McCuaig] finally it was shown, that all these problems are solvable in polynomial time.
In [Kullmann] the qualitative-matrix-approach (see [Brualdi,Shader] for
background) was expanded, and a natural embedding of the problem into some (boolean) satisfiability problem (exploiting autarky theory) was demonstrated. As an application for example it is shown, that hypergraph 2-colourability is decidable in polynomial
time if the maximum of the differences of the number of hyperedges and the number of vertices over all sub-hypergraphs is zero.
In my talk I want to introduce this old (and new) area, hopefully giving some feeling for the subject, and communicating open problems.
Richard A. Brualdi and Bryan L. Shader.
Matrices of sign-solvable linear systems.
Cambridge University Press, 1995.
Oliver Kullmann. Polynomial time SAT decision for linearly lean complementation-invariant clause-sets of minimal relative deficiency.
University of Wales Swansea, Computer Science Report Series, CSR 1-2007; to appear in SAT 2007.
William McCuaig. Polya's Permanent Problem. The Electronic Journal of
Combinatorics:11, 2004, #R79, 83 pages.
Neil Robertson, Paul D. Seymour, Robin Thomas. Permanents, Pfaffian
orientations, and even directed circuits. Annals of Mathematics:150, 1999, 929-975.
Area(s): LOGIC AND COMPUTATION
|
|
Date: |
|
| Start Time: |
14:00 |
|
Speaker: |
Oliver Kullmann (University of Wales, Swansea)
|
|
Place: |
5.4
|
|
See more:
|
<Main>
|
|
