Improving exact exponential-time algorithms for NP-complete problems is an expanding
research area. Unfortunately, general methods for comparing the complexity of such …

In this paper we examine generalized satisfiability problems with limited variable
occurrences. First, we show that 3 occurrences per variable suffice to make these problems …

The construction of exact exponential-time algorithms for NP-complete problems has for
some time been a very active research area. Unfortunately, there is a lack of general …

The main result of this article is a generalization of the classical blossom algorithm for
finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each …

General factors are a generalization of matchings. Given a graph $ G $ with a set $\pi (v) $ of
feasible degrees, called a degree constraint, for each vertex $ v $ of $ G $, the general factor …

On Planar Boolean CSP Page 1 On Planar Boolean CSP Zdenek Dvorák(B) and Martin
Kupec Computer Science Institute, Charles University in Prague, Prague, Czech Republic {rakdver,magon}@iuuk.mff.cuni.cz …

A dichotomy theorem for a class of decision problems is a result asserting that certain
problems in the class are solvable in polynomial time, while the rest are NP-complete. The …

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 …

Abstract In the Constraint Satisfaction Problem (CSP) one is supposed to find an assignment
to a set of variables so that a set of given constraints are satisfied. Many problems, both …

A graph G has an S-factor if there exists a spanning subgraph F of G such that for all v in V:
deg_F (v) in S. The simplest example of such factor is a 1-factor, which corresponds to a …