Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR05-016 | 13th January 2005 00:00

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

TR05-016
Authors: Tomas Feder, Daniel Ford
Publication: 31st January 2005 16:15
Keywords:

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.

ISSN 1433-8092 | Imprint