Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-016 | 13th January 2005 00:00

Classification of Bipartite Boolean Constraint Satisfaction through Delta-Matroid Intersection



Matroid intersection has a known polynomial time algorithm using an
oracle. We generalize this result to delta-matroids that do not have
equality as a restriction, and give a polynomial time algorithm for
delta-matroid intersection on delta-matroids without equality using an
oracle. We note that when equality is present, delta-matroid intersection
is as general as delta-matroid parity.
We also obtain algorithms using an oracle for delta-matroid parity on
delta-matroids without inequality, and for delta-matroid
intersection where one delta-matroid does not contain either equality
or inequality, and the second delta-matroid is arbitrary.
Both of these results also generalize matroid intersection.
The results imply a dichotomy for bipartite Boolean constraint
satisfaction problems using an oracle when one of the two sides does
not contain equality, leaving open cases of delta-matroid parity when
both sides have equality; the results also imply a full dichotomy
for $k$-partite Boolean constraint satisfaction problems for $k\geq 3$.
We then discuss polynomial cases of Boolean constraint satisfaction
problems with two occurrences per variable through delta-matroid
parity that cannot be obtained using the oracle approach.

ISSN 1433-8092 | Imprint