Search

A star in an undirected graph is a tree in which at most one vertex has degree larger than one. A star forest is a collection of vertex disjoint stars. An out-star (in-star) in a digraph D is a star in the underlying undirected graph of D such that all edges are directed out of (into) the center. The problem of partitioning the edges of the underlying graph of a digraph D into two star forests F 0 and F 1 is known to be NP-complete. On the other hand, with the additional requirement for F0 and F 1 to be forests of out-stars the problem becomes polynomial (via an easy reduction to 2-SAT). In this article we settle the complexity of problems lying in between these two problems. Namely, we study the complexity of the related problems where we require each F i to be a forest of stars in the underlying sense and require (in different problems) that in D, F i is either a forest of out-stars, in-stars, out- or in-stars or just stars in the underlying sense.

An instance of a constraint satisfaction problem is l-consistent if any l constraints of it can be simultaneously satisfied. For a set Π of constraint types, ρl(Π) denotes the largest ratio of constraints which can be satisfied in any l-consistent instance composed by constraints of types from Π. In the case of sets Π consisting of finitely many Boolean predicates, we express the limit ρ∞(Π):=liml→∞ρl(Π) as the minimum of a certain functional on a convex set of polynomials. Our results yield a robust deterministic algorithm (for a fixed set Π) running in time linear in the size of the input and 1/ε which finds either an inconsistent set of constraints (of size bounded by the function of ε) or a truth assignment which satisfies the fraction of at least ρ∞(Π)-ε of the given constraints. We also compute the values of ρl({P}) for several specific predicates P.

It is known that almost all 2-CNF-formulas where the number of clauses is n(1−ϵ), ϵ>0 a constant, n the number of variables are satisfiable. For n(1+ϵ) clauses they are known to be unsatisfiable. We strengthen the first result and show that for each ϵ=ϵ(n)⩾(1/( ln n)) 1/2 (hence ϵ may approach 0) the first of the results above still holds.