ECCC-Report TR05-016https://eccc.weizmann.ac.il/report/2005/016Comments and Revisions published for TR05-016en-usMon, 31 Jan 2005 16:15:10 +0200
Paper TR05-016
| Classification of Bipartite Boolean Constraint Satisfaction through Delta-Matroid Intersection |
Tomas Feder,
Daniel Ford
https://eccc.weizmann.ac.il/report/2005/016Matroid 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.
Mon, 31 Jan 2005 16:15:10 +0200https://eccc.weizmann.ac.il/report/2005/016