Search

The Chordal Vertex Deletion (CHVD) problem asks to delete a minimum number of vertices from an input graph to obtain a chordal graph. In this paper we develop a polynomial kernel for CHVD under the parameterization by the solution size. Using a new Erdõs-Pósa-type packing/covering duality for holes in nearly chordal graphs, we present a polynomial-time algorithm that reduces any instance (G, k) of CHVD to an equivalent instance with poly(k) vertices. The existence of a polynomial kernel answers an open problem posed by Marx in 2006 [D. Marx, "Chordal Deletion Is Fixed-Parameter Tractable," in Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci. 4271, Springer, 2006, pp. 37-48]. To obtain the kernelization, we develop the first poly(opt)-approximation algorithm for CHVD, which is of independent interest. In polynomial time, it either decides that G has no chordal deletion set of size k, or outputs a solution of size O(k4log² k). [ABSTRACT FROM AUTHOR]

Inside a two-dimensional region ("cake"), there are m nonoverlapping tiles of a certain kind ("toppings"). We want to expand the toppings while keeping them nonoverlapping, and possibly add some blank pieces of the same "certain kind," such that the entire cake is covered. How many blanks must we add? We study this question in several cases: (1) The cake and toppings are general polygons. (2) The cake and toppings are convex figures. (3) The cake and toppings are axis-parallel rectangles. (4) The cake is an axis-parallel rectilinear polygon and the toppings are axis-parallel rectangles. In all four cases, we provide tight bounds on the number of blanks. [ABSTRACT FROM AUTHOR]

We prove an upper bound on the Shannon capacity of a graph via a linear programming variation. We show that our bound can outperform both the Lov\'asz theta number and the Haemers minimum rank bound. As a by-product, we also obtain a new upper bound on the broadcast rate of index coding. [ABSTRACT FROM AUTHOR]

For given simple graphs G1 and G2, the size Ramsey number Ȓ(G1,G2) is the smallest positive integer m, where there exists a graph G with m edges such that in any edge coloring of G with two colors red and blue, there is either a red copy of G1 or a blue copy of G2. In 1981, Erdös and Faudree investigated the size Ramsey number Ȓ(Kn, tK2), where Kn is a complete graph on n vertices and tK2 is a matching of size t. They obtained the value of Ȓ(Kn, tK2) when n ≥ 4t-1 as well as for t = 2 and asked for the behavior of these numbers when t is much larger than n. In this regard, they posed the following interesting question: For every positive integer n, is it true that ... In this paper, we obtain the exact value of Ȓ(Kn, tK2) for every pair of positive integers n, t, and as a byproduct, we give an affirmative answer to the question of Erdös and Faudree. [ABSTRACT FROM AUTHOR]

In this paper, we study the connectivity properties of the random subgraph of the n-cube generated by the k-out model and denoted by Qn(k). Let k be an integer, 1 ≤ k ≤ n-1. We let Qn(k) be the graph that is generated by independently including for every ν ∊ V(Qn) a set of k distinct edges chosen uniformly from all the (k n) sets of distinct edges that are incident to ν. We study the connectivity properties of Qn(k) as k varies. We show that without high probability (w.h.p.), Qn(1) does not contain a giant component i.e., a component that spans Ω(2n) vertices. Thereafter, we show that such a component emerges when k=2. In addition, the giant component spans all but o(2n) vertices, and hence it is unique. We then establish the connectivity threshold found at k0=log2 n-2log2log2 n. The threshold is sharp in the sense that Qn([k0]) is disconnected but Qn([k0]+1) is connected w.h.p. Furthermore, we show that w.h.p., Qn(k) is k-connected for every k≥ [k0]+1. [ABSTRACT FROM AUTHOR]