Discrete Mathematics, Algorithms and Applications

Let H be a graph with the chromatic number h and the chromatic surplus s. A connected graph G of order n is called H-good if R(G, H) = (n - 1)(h - 1) + s. In this paper, we show that P_n is 2K_m-good for n ≥ 3. Furthermore, we obtain the Ramsey number R(L, 2K_m), where L is a linear forest. Moreover, we also give the Ramsey number R(L, H_m) which is an extension for R(kP_n, H_m) proposed by Ali et al. [1], where H_m is a cocktail party graph on 2m vertices.

In this paper, contention resolution among k contenders on a multiple-access channel is explored. The problem studied has been modeled as a k-Selection in Radio Networks, in which every contender has to have exclusive access at least once to a shared communication channel. The randomized adaptive protocol presented shows that, for a probability of error 2ε, all the contenders get access to the channel in time (e+1+ξ)k + O(log²(1/ε)), where ε ≤ 1/(n+1), ξ > 0 is any constant arbitrarily close to 0, and n is the total number of potential contenders. The above time complexity is asymptotically optimal for any significant ε. The protocol works even if the number of contenders k is unknown and collisions cannot be detected.

The parallel repetition theorem states that for any two provers one round game with value at most 1 - ∊ (for ∊ < 1/2), the value of the game repeated n times in parallel is at most (1 - ∊³)^{Ω(n/log s)} where s is the size of the answers set [9, 12]. It is not known how the value of the game decreases when there are three or more players. In this paper we address the problem of the error decrease of parallel repetition game for k-provers where k > 2. We consider a special case of the No-Signaling model and show that the error of the parallel repetition of k-provers one round game, for k > 2, in this model, decreases exponentially depending only on the error of the original game and on the number of repetitions. There were no prior results for k-provers parallel repetition for k > 2 in any model.

We consider directed figures defined as labelled polyominoes with designated start and end points, with a partial catenation. As we are interested in codicity verification for sets of figures, we show that it is decidable for sets of figures with parallel translation vectors, which is one of the decidability border cases in this setting. We give a constructive proof which leads to a straightforward algorithm.

A word circuit [1] is a directed acyclic graph in which each edge holds a w-bit word (i.e., some x ∈ {0, 1}^w) and each node is a gate computing some binary function g : {0, 1}^w × {0, 1}^w → {0, 1}^w. The following problem was studied in [1]: How many binary gates are needed to compute a ternary function f : ({0, 1}^w)³ → {0, 1}^w. They proved that (2 + o(1))2^w binary gates are enough for any ternary function, and there exists a ternary function which requires word circuits of size (1 - o(1))2^w. One of the open problems in [1] is to get these bounds tight within a low order term. In this paper we solved this problem by constructing new word circuits for ternary functions of size (1 + o(1))2^w. We investigate the problem in a general setting: How many k-input word gates are needed for computing an n-input word function f : ({0, 1}^w)ⁿ → {0, 1}^w (here n ≥ k). We show that for any fixed n, (1 - o(1))2^{(n - k)w} basic gates are necessary and (1 + o(1))2^{(n - k)w} gates are sufficient (assume w is sufficiently large). Since word circuit is a natural generalization of boolean circuit, we also consider the case when w is a constant and the number of inputs n is sufficiently large. We show that basic gates are necessary and sufficient in this case.

We give a priority queue that achieves the same amortized bounds as Fibonacci heaps. Namely, find-min requires O(1) worst-case time, insert, meld and decrease-key require O(1) amortized time, and delete-min requires O(log n) amortized time. Our structure is simple and promises an efficient practical behavior when compared to other known Fibonacci-like heaps. The main idea behind our construction is to propagate rank updates instead of performing cascaded cuts following a decrease-key operation, allowing for a relaxed structure.

The density of a language is defined as the function d_L(n) = |L ∩ Σⁿ| and counts the number of words of a certain length accepted by L. The study of the density of regular and context-free languages has attracted some attention culminating in the fact that such languages are either sparse, when the density can be bounded by a polynomial, or dense otherwise. We show that for all nonambiguous context-free languages the number of accepted words of a given length n can also be computed recursively using a finite combination of the number of accepted words smaller than n, or . This extends an old result by Chomsky and provides us with a more expressive description and new insights into possible applications of the density function for such languages as well as possible characterizations of the density of higher languages.

The notion of average-case hardness is a fundamental one in complexity theory. In particular, it plays an important role in the research on derandomization, as there are general derandomization results which are based on the assumption that average-case hard functions exist. However, to achieve a complete derandomization, one usually needs a function which is extremely hard against a complexity class, in the sense that any algorithm in the class fails to compute the function on 1/2 - 2^-Ω(n) fraction of its n-bit inputs. Unfortunately, lower bound results are very rare and they are only known for very restricted complexity classes, and achieving such extreme hardness seems even more difficult. Motivated by this, we study the hardness against linear-size circuits of constant depth in this paper. We show that the parity function is extremely hard for them: any such circuit must fail to compute the parity function on at least 1/2 - 2^-Ω(n) fraction of inputs.

We consider the optimization problem of finding k nonintersecting rectangles and tableaux in n × n pixel plane where each pixel has a real valued weight. We discuss existence of efficient algorithms if a corner point of each rectangle/tableau is specified.

The persistent homology provides a mathematical tool to describe "features" in a principled manner. The persistence algorithm proposed by Edelsbrunner et al. can compute not only the persistent homology for a filtered simplicial complex, but also representative generating cycles for persistent homology groups. However, if there are dynamic changes either in the filtration or in the underlying simplicial complex, the representative generating cycle can change wildly.

In this paper, we consider the problem of tracking generating cycles with temporal coherence. Specifically, our goal is to track a chosen essential generating cycle so that the changes in it are "local". This requires reordering simplices in the filtration. To handle reordering operations, we build upon the matrix framework proposed by Cohen-Steiner et al. to swap two consecutive simplices, so that we can process a reordering directly. We present an application showing how our algorithm can track an essential cycle in a complex constructed out of a point cloud data.

We provide an efficient reduction from the problem of querying approximate multiplicatively weighted farthest neighbors in a metric space to the unweighted problem. Combining our techniques with core-sets for approximate unweighted farthest neighbors, we show how to find approximate farthest neighbors that are farther than a factor (1 - ∊) of optimal in time O(log n) per query in D-dimensional Euclidean space for any constants D and ∊. As an application, we find an O(n log n) expected time algorithm for choosing the center of a star topology network connecting a given set of points, so as to approximately minimize the maximum dilation between any pair of points.

The 3D visibility skeleton is a data structure that encodes the global visibility information of a set of 3D objects. While it is useful in answering global visibility queries, its large size often limits its practical use. In this paper, we address this issue by proposing a subset of the visibility skeleton, which is empirically about 25% to 50% of the whole set. We show that the rest of the data structure can be recovered from the subset as needed, partially or completely. The running time complexity, which we analyze in terms of output size, is efficient. We also prove that the subset is minimal in the sense that the complexity bound ceases to hold if the subset is restricted further.

Let G be an undirected graph with m edges and n vertices. A spanner of G is a subgraph which preserves approximate distances between all pairs of vertices. An f-vertex fault-tolerant spanner is a subgraph which preserves approximate distances, under the failure of any set of at most f vertices. The contribution of this paper is twofold: we present algorithms for computing fault-tolerant spanners, and propose streaming algorithms for computing spanners in very small internal memory. In particular, we give algorithms for computing f-vertex fault-tolerant (3,2)- and (2,1)-spanners of G with the following bounds: our (3,2)-spanner contains O(f^4/3n^4/3) edges and can be computed in time Õ(f²m), while our(2, 1)-spanner contains O(fn^3/2) edges and can be computed in time . Both algorithms improve significantly on previously known bounds.

Assume that the graph G is presented as an input stream of edges, which may appear in any arbitrary order, and that we do not know in advance m and n. We show how to compute efficiently (3, 2)- and (2, 1)-spanners of G, using only very small internal memory and as low access external memory device. Our spanners have asymptotically optimal size and the I/O complexity of our algorithms for computing such spanners is optimal upto apolylogarithmic factor. Our f-vertex fault-tolerant (3, 2)- and (2, 1)-spanners can also be computed efficiently in the same computational model described above.

Let T be an edge weighted tree, let d_T(u, v) be the sum of the weights of the edges on the path from u to v in T, and let d_min and d_max be two non-negative real numbers such that d_min ≤ d_max. Then a pairwise compatibility graph of T for d_min and d_max is a graph G = (V, E), where each vertex u' ∈ V corresponds to a leaf u of T and there is an edge (u', v') ∈ E if and only if d_min ≤ d_T(u, v) ≤ d_max. A graph G is called a pairwise compatibility graph (PCG) if there exists an edge weighted tree T and two non-negative real numbers d_min and d_max such that G is a pairwise compatibility graph of T for d_min and d_max. Kearney et al. conjectured that every graph is a PCG [3]. In this paper, we refute the conjecture by showing that not all graphs are PCGs. Moreover, we recognize several classes of graphs as pairwise compatibility graphs. We identify two restricted classes of bipartite graphs as PCG. We also show that the well known tree power graphs and some of their extensions are PCGs.

We consider the following sample selection problem. We observe in an online fashion a sequence of samples, each endowed by a quality. Our goal is to either select or reject each sample, so as to maximize the aggregate quality of the subsample selected so far. There is a natural trade-off here between the rate of selection and the aggregate quality of the subsample. We show that for a number of such problems extremely simple and oblivious "threshold rules" for selection achieve optimal tradeoffs between rate of selection and aggregate quality in a probabilistic sense. In some cases we show that the same threshold rule is optimal for a large class of quality distributions and is thus oblivious in a strong sense.

A 2-matching in an undirected graph G = (VG, EG) is a function x: EG → {0, 1, 2} such that for each node v ∈ VG the sum of values x(e) for all edges e incident to v does not exceed 2. The size of x is the sum ∑_e x(e). If {e ∈ EG|x(e) ≠ 0} contains no triangles then x is called triangle-free.

Cornuéjols and Pulleyblank devised a combinatorial O(mn)-algorithm that finds a maximum triangle free 2-matching of size (hereinafter n ≔ |VG|, m ≔ |EG|) and also established a min-max theorem.

We claim that this approach is, in fact, superfluous by demonstrating how these results may be obtained directly from the Edmonds–Gallai decomposition. Applying the algorithm of Micali and Vazirani we are able to find a maximum triangle-free 2-matching in time. Also we give a short self-contained algorithmic proof of the min-max theorem.

Next, we consider the case of regular graphs. It is well-known that every regular graph admits a perfect 2-matching. One can easily strengthen this result and prove that every d-regular graph (for d ≥ 3) contains a perfect triangle-free 2-matching. We give the following algorithms for finding a perfect triangle-free 2-matching in a d-regular graph: an O(n)-algorithm for d = 3, an O(m + n^3/2)-algorithm for d = 2k(k ≥ 2), and an O(n²)-algorithm for d = 2k + 1(k ≥ 2).

We also prove that there exists a constant c > 1 such that every 3-regular graph contains at least cⁿ perfect triangle-free 2-matchings.