__
TR05-016 | 13th January 2005 00:00
__

#### Classification of Bipartite Boolean Constraint Satisfaction through Delta-Matroid Intersection

**Abstract:**
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.