Property testers for dense constraint satisfaction programs on finite domains

Many NP‐hard languages can be “decided” in subexponential time if the definition of “decide” is relaxed only slightly. Rubinfeld and Sudan introduced the notion of property testers, probabilistic algorithms that can decide, with high probability, if a function has a certain property or if it is far from any function having this property. Goldreich, Goldwasser, and Ron constructed property testers with constant query complexity for dense instances of a large class of graph problems. Since many graph problems can be viewed as special cases of the Constraint Satisfaction Problem on Boolean domains, it is natural to try to construct property testers for more general cases of the Constraint Satisfaction Problem. In this paper, we give explicit constructions of property testers using a constant number of queries for dense instances of Constraint Satisfaction Problems where the constraints have constant arity and the variables assume values in some domain of finite size. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 14–32, 2002     

On the advantage over a random assignment

We initiate the study of a new measure of approximation. This measure compares the performance of an approximation algorithm to the random assignment algorithm. This is a useful measure for optimization problems where the random assignment algorithm is known to give essentially the best possible polynomial time approximation. In this paper, we focus on this measure for the optimization problems Max‐Lin‐2 in which we need to maximize the number of satisfied linear equations in a system of linear equations modulo 2, and Max‐k‐Lin‐2, a special case of the above problem in which each equation has at most k variables. The main techniques we use, in our approximation algorithms and inapproximability results for this measure, are from Fourier analysis and derandomization. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

On Moore bipartite digraphs

In the context of the degree/diameter problem for directed graphs, it is known that the number of vertices of a strongly connected bipartite digraph satisfies a Moore‐like bound in terms of its diameter k and the maximum out‐degrees (d₁, d₂) of its partite sets of vertices. It has been proved that, when d₁d₂ > 1, the digraphs attaining such a bound, called Moore bipartite digraphs, only exist when 2 ≤ k ≤ 4. This paper deals with the problem of their enumeration. In this context, using the theory of circulant matrices and the so‐called De Bruijn near‐factorizations of cyclic groups, we present some new constructions of Moore bipartite digraphs of diameter three and composite out‐degrees. By applying the iterated line digraph technique, such constructions also provide new families of dense bipartite digraphs with arbitrary diameter. Moreover, we show that the line digraph structure is inherent in any Moore bipartite digraph G of diameter k = 4, which means that G = L G′, where G′ is a Moore bipartite digraph of diameter k = 3. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 171–187, 2003     

Approximation algorithms via contraction decomposition

We prove that the edges of every graph of bounded (Euler) genus can be partitioned into any prescribed number k of pieces such that contracting any piece results in a graph of bounded treewidth (where the bound depends on k). This decomposition result parallels an analogous, simpler result for edge deletions instead of contractions, obtained in [4,20, 10, 17], and it generalizes a similar result for “compression” (a variant of contraction) in planar graphs [29]. Our decomposition result is a powerful tool for obtaining PTASs for contraction-closed problems (whose optimal solution only improves under contraction), a much more general class than minor-closed problems. We prove that any contraction-closed problem satisfying just a few simple conditions has a PTAS in bounded-genus graphs. In particular, our framework yields PTASs for the weighted Traveling Salesman Problem and for minimum-weight c-edge-connected submultigraph on bounded-genus graphs, improving and generalizing previous algorithms of [24, 1, 29, 25, 8, 5]. We also highlight the only main difficulty in extending our results to general H-minor-free graphs.     

AMLI preconditioner for the p‐version of the FEM

From the literature it is known that the conjugate gradient method with domain decomposition preconditioners is one of the most efficient methods for solving systems of linear algebraic equations resulting from p‐version finite element discretizations of elliptic boundary value problems. One ingredient of such a preconditioner is a preconditioner related to the Dirichlet problems. In the case of Poisson's equation, we present a preconditioner for the Dirichlet problems which can be interpreted as the stiffness matrix K_h,k resulting from the h‐version finite element discretization of a special degenerated problem. We construct an AMLI preconditioner C_h,k for the matrix K_h,k and show that the condition number of C K_h,k is independent of the discretization parameter. This proof is based on the strengthened Cauchy inequality. The theoretical result is confirmed by numerical examples. Copyright © 2003 John Wiley & Sons, Ltd.     

Rotational k‐cycle systems of order v < 3k; another proof of the existence of odd cycle systems

We give an explicit solution to the existence problem for 1‐rotational k‐cycle systems of order v < 3k with k odd and v ≠ 2k + 1. We also exhibit a 2‐rotational k‐cycle system of order 2k + 1 for any odd k. Thus, for k odd and any admissible v < 3k there exists a 2‐rotational k‐cycle system of order v. This may also be viewed as an alternative proof that the obvious necessary conditions for the existence of odd cycle systems are also sufficient. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 433–441, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10061     

K‐linked graphs with girth condition

Recently, Mader [ 7 ] proved that every 2k‐connected graph with girth g(G) sufficiently large is k‐linked. We show here that g(G ≥ 11 will do unless k = 4,5. If k = 4,5, then g(G) ≥ 19 will do. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 48–50, 2004     

Behaviour of (−Δ−k2−i0+)−1 outside fading obstacles,independant scattering hypothesis and applications

This paper deals with the behaviour of k‐outgoing solutions of ?Δu?k²u=f outside a fading soft obstacle. We extend an approach using the so‐called Lax–Phillips construction and the well‐known properties of the capacity of smooth obstacles. So, classical results are recovered in a straightforward manner. The previous approach enables us to consider the case of obstacles composed of many tiny spheres. Roughly speaking, we prove that the scattering amplitude is approximately the sum of the scattering amplitudes scattered by each isolated sphere, which is an alternative form of the first Born approximation. As a consequence, two inverse problems are solved. Copyright © 2003 John Wiley & Sons, Ltd.     

Lipschitz continuity and Gateaux differentiability of the best approximation operator in vector-valued Chebyshev approximation

When G is a finite-dimensional Haar subspace of C(X,R^k), the vector-valued functions (including complex-valued functions when k is 2) from a finite set X to Euclidean k-dimensional space, it is well-known that at any function f in C(X,R^k) the best approximation operator satisfies the strong unicity condition of order 2 and a Lipschitz (Hőlder) condition of order . This note shows that in fact the best approximation operator satisfies the usual Lipschitz condition of order 1 and has a Gateaux derivative on a dense set of functions in C(X,R^k).     

Crossing numbers of sequences of graphs II: Planar tiles

We describe a method of creating an infinite family of crossing‐critical graphs from a single small planar map, the tile, by gluing together many copies of the tile together in a circular fashion. This method yields all known infinite families of k‐crossing‐critical graphs. Furthermore, the method yields new infinite families, which extend from (4,6) to (3.5,6) the interval of rationals r for which there is, for some k, an infinite sequence of k‐crossing‐critical graphs all having average degree r. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 332–341, 2003     

Highly edge‐connected detachments of graphs and digraphs

Let G = (V,E) be a graph or digraph and r : V → Z₊. An r‐detachment of G is a graph H obtained by ‘splitting’ each vertex ν ∈ V into r(ν) vertices. The vertices ν₁,…,ν_r(ν) obtained by splitting ν are called the pieces of ν in H. Every edge uν ∈ E corresponds to an edge of H connecting some piece of u to some piece of ν. Crispin Nash‐Williams 9 gave necessary and sufficient conditions for a graph to have a k‐edge‐connected r‐detachment. He also solved the version where the degrees of all the pieces are specified. In this paper, we solve the same problems for directed graphs. We also give a simple and self‐contained new proof for the undirected result. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 67–77, 2003     

4‐*GDDs(3n) and generalized Steiner systems GS(2, 4, v, 3)

Generalized Steiner systems GS(2, k, v, g) were first introduced by Etzion and used to construct optimal constant weight codes over an alphabet of size g + 1 with minimum Hamming distance 2k ? 3, in which each codeword has length v and weight k. As to the existence of a GS(2, k, v, g), a lot of work has been done for k = 3, while not so much is known for k = 4. The notion k‐*GDD was first introduced and used to construct GS(2, 3, v, 6). In this paper, singular indirect product (SIP) construction for GDDs is modified to construct GS(2, 4, v, g) via 4‐*GDDs. Furthermore, it is proved that the necessary conditions for the existence of a 4‐*GDD(3ⁿ), namely, n ≡ 0, 1 (mod 4) and n ≥ 8 are also sufficient. The known results on the existence of a GS(2, 4, v, 3) are then extended. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 381–393, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10047     

Vertex‐pancyclicity of hypertournaments

A hypertournament or a k‐tournament, on n vertices, 2≤k≤n, is a pair T=(V, E), where the vertex set V is a set of size n and the edge set E is the collection of all possible subsets of size k of V, called the edges, each taken in one of its k! possible permutations. A k‐tournament is pancyclic if there exists (directed) cycles of all possible lengths; it is vertex‐pancyclic if moreover the cycles can be found through any vertex. A k‐tournament is strong if there is a path from u to v for each pair of distinct vertices u and v. A question posed by Gutin and Yeo about the characterization of pancyclic and vertex‐pancyclic hypertournaments is examined in this article. We extend Moon's Theorem for tournaments to hypertournaments. We prove that if k≥8 and n≥k + 3, then a k‐tournament on n vertices is vertex‐pancyclic if and only if it is strong. Similar results hold for other values of k. We also show that when n≥7, k≥4, and n≥k + 2, a strong k‐tournament on n vertices is pancyclic if and only if it is strong. The bound n≥k+ 2 is tight. We also find bounds for the generalized problem when we extend vertex‐pancyclicity to require d edge‐disjoint cycles of each possible length and extend strong connectivity to require d edge‐disjoint paths between each pair of vertices. Our results include and extend those of Petrovic and Thomassen. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 338–348, 2010     

Generalized Adjunction of k‐Very Ample Vector Bundles on Algebraic Surfaces II

We study the k‐very ampleness of the adjoint bundle K_S + det E associated to a (k — 1)‐very ample vector bundle E with degree greater than or equal to 4k + 5 on an algebraic surface S. We classify polarized surfaces (S, E) which the k‐very ampleness of K_S + det E fails.     

Det‐extremal cubic bipartite graphs

Let G be a connected k–regular bipartite graph with bipartition V(G) = X ∪ Y and adjacency matrix A. We say G is det‐extremal if per (A) = |det(A)|. Det–extremal k–regular bipartite graphs exist only for k = 2 or 3. McCuaig has characterized the det‐extremal 3‐connected cubic bipartite graphs. We extend McCuaig's result by determining the structure of det‐extremal cubic bipartite graphs of connectivity two. We use our results to determine which numbers can occur as orders of det‐extremal connected cubic bipartite graphs, thus solving a problem due to H. Gropp. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 50–64, 2003     

Concentration inequalities for nonlinear matroid intersection

In this work we propose new randomized rounding algorithms for matroid intersection and matroid base polytopes. We prove concentration inequalities for polynomial objective functions and constraints that has numerous applications and can be used in approximation algorithms for Minimum Quadratic Spanning Tree, Unrelated Parallel Machines Scheduling and scheduling with time windows and nonlinear objectives. We also show applications related to Constraint Satisfaction and dense polynomial optimization. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 541–571, 2015     

Using Homogeneous Weights for Approximating the Partial Cover Problem

In this paper we consider the natural generalizations of two fundamental problems, the Set-Cover problem and the Min-Knapsack problem. We are given a hypergraph, each vertex of which has a nonnegative weight, and each edge of which has a nonnegative length. For a given threshold , our objective is to find a subset of the vertices with minimum total cost, such that at least a length of of the edges is covered. This problem is called the partial set cover problem. We present an O(|V|² + |H|)-time, Δ_E-approximation algorithm for this problem, where Δ_E ≥ 2 is an upper bound on the edge cardinality of the hypergraph and |H| is the size of the hypergraph (i.e., the sum of all its edges cardinalities). The special case where Δ_E = 2 is called the partial vertex cover problem. For this problem a 2-approximation was previously known, however, the time complexity of our solution, i.e., O(|V|²), is a dramatic improvement.We show that if the weights are homogeneous (i.e., proportional to the potential coverage of the sets) then any minimal cover is a good approximation. Now, using the local-ratio technique, it is sufficient to repeatedly subtract a homogeneous weight function from the given weight function.     

Antimagic labelling of vertex weighted graphs

Suppose G is a graph, k is a non‐negative integer. We say G is k‐antimagic if there is an injection f: E→{1, 2, …, |E| + k} such that for any two distinct vertices u and v, . We say G is weighted‐k‐antimagic if for any vertex weight function w: V→?, there is an injection f: E→{1, 2, …, |E| + k} such that for any two distinct vertices u and v, . A well‐known conjecture asserts that every connected graph G≠K₂ is 0‐antimagic. On the other hand, there are connected graphs G≠K₂ which are not weighted‐1‐antimagic. It is unknown whether every connected graph G≠K₂ is weighted‐2‐antimagic. In this paper, we prove that if G has a universal vertex, then G is weighted‐2‐antimagic. If G has a prime number of vertices and has a Hamiltonian path, then G is weighted‐1‐antimagic. We also prove that every connected graph G≠K₂ on n vertices is weighted‐ ?3n/2?‐antimagic. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory     

The number of k‐SAT functions

We study the number SAT(k; n) of Boolean functions of n variables that can be expressed by a k‐SAT formula. Equivalently, we study the number of subsets of the n‐cube 2ⁿ that can be represented as the union of (n ? k)‐subcubes. In The number of 2‐SAT functions (Isr J Math, 133 (2003), 45–60) the authors and Imre Leader studied SAT(k; n) for k ≤ n/2, with emphasis on the case k = 2. Here, we prove bounds on SAT(k; n) for k ≥ n/2; we see a variety of different types of behavior. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 22: 227–247, 2003     

The mathematics of playing golf, or: a new class of difficult non-linear mixed integer programs

We consider a class of non-linear mixed integer programs with n integer variables and k continuous variables. Solving instances from this class to optimality is an NP-hard problem. We show that for the cases with k=1 and k=2, every optimal solution is integral. In contrast to this, for every k≥3 there exist instances where every optimal solution takes non-integral values. Received: August 2001 / Accepted: January 2002?Published online March 27, 2002