Arc-Disjoint Cycle Packing is a classical NP -complete problem and we study it from two perspectives: (1) by restricting the cycles in the packing to be of a fixed length, and (2) by restricting the inputs to bipartite tournaments. Focusing first on Arc-Disjoint r -Cycle Packing (where the cycles in the packing are required to be of length r ), we show NP -completeness in oriented graphs with girth r for each r ≥ 3 and study the parameterized complexity of the problem with respect to two parameterizations (solution size and vertex cover size) for r = 4 in oriented graphs. Moving on to Arc-Disjoint Cycle Packing in bipartite tournaments, we show that every bipartite tournament either contains k arc-disjoint cycles or has a feedback arc set of size at most 7 ( k − 1 ) . This result adds to the set of Erdös-Pósa-type results known in the combinatorics literature for packing and covering problems.

In this paper, we study testing of sequence properties that are defined by forbidden order patterns. A sequence f : {1,…, n} → ℝ of length n contains a pattern is the group of permutations of k elements), iff there are indices i1 < i2 < · · · < ik, such that f (ix) > f (iy) whenever π(χ) > π(y). If f does not contain π, we say f is π-free. For example, for π = (2,1), the property of being π-free is equivalent to being non-decreasing, i.e. monotone. The property of being (k,k — 1,…, 1)-free is equivalent to the property of having a partition into at most k - 1 non-decreasing subsequences. Let k constant, be a (forbidden) pattern. Assuming f is stored in an array, we consider the property testing problem of distinguishing the case that f is π-free from the case that f differs in more than en places from any π-free sequence. We show the following results: There is a clear dichotomy between the monotone patterns and the non-monotone ones: For monotone patterns of length k, i.e., (k,k - 1,…, 1) and (1, 2,…, k), we design non-adaptive one-sided error ε-tests of (∊−1 log n)O(k2) query complexity. For non-monotone patterns, we show that for any size-k non-monotone π, any non-adaptive one-sided error ε-test requires at least Ω(γ/η) queries. This general lower bound can be further strengthened for specific non-monotone k-length patterns to Ω(n1–2/(k+1)). On the other hand, there always exists a non- adaptive one-sided error ε-test for with O(e−1/kn1–1/k) query complexity Again, this general upper bound can be further strengthened for specific non-monotone patterns. E.g., for π = (1, 3, 2), we describe an ε-test with (almost tight) query complexity of Finally, we show that adaptivity can make a big difference in testing non-monotone patterns, and develop an adaptive algorithm that for any tests π-freeness by making (∊−1 logn)O(1) queries. For all algorithms presented here, the running times are linear in their query complexity.

The separation dimension of a graph $G$ is the smallest natural number $k$ for which the vertices of $G$ can be embedded in $\mathbb{R}^k$ such that any pair of disjoint edges in $G$ can be separated by a hyperplane normal to one of the axes. Equivalently, it is the smallest possible cardinality of a family $\mathcal{F}$ of total orders of the vertices of $G$ such that for any two disjoint edges of $G$, there exists at least one total order in $\mathcal{F}$ in which all the vertices in one edge precede those in the other. In general, the maximum separation dimension of a graph on $n$ vertices is $\Theta(\log n)$. In this article, we focus on bounded degree graphs and show that the separation dimension of a graph with maximum degree $d$ is at most $2^{9{log^{\star}}\!d} d$. We also demonstrate that the above bound is nearly tight by showing that, for every $d$, almost all $d$-regular graphs have separation dimension at least $\ceil{d/2}$.

A rainbow colouring of a connected graph G is a colouring of the edges of G such that every pair of vertices in G is connected by at least one path in which no two edges are coloured the same. The minimum number of colours required to rainbow colour G is called its rainbow connection number. Chakraborty, Fischer, Matsliah and Yuster have shown that it is NP-hard to compute the rainbow connection number of graphs [J. Comb. Optim., 2011]. Basavaraju, Chandran, Rajendraprasad and Ramaswamy have reported an (r+3)-factor approximation algorithm to rainbow colour any graph of radius r [Graphs and Combinatorics, 2012]. In this article, we use a result of Guruswami, Håstad and Sudan on the NP-hardness of colouring a 2-colourable 4-uniform hypergraph using constantly many colours [SIAM J. Comput., 2002] to show that for every positive integer k, it is NP-hard to distinguish between graphs with rainbow connection number 2k+2 and 4k+2. This, in turn, implies that there cannot exist a polynomial time algorithm to rainbow colour graphs with less than twice the optimum number of colours, unless P=NP. The authors have earlier shown that the rainbow connection number problem remains NP-hard even when restricted to the class of chordal graphs, though in this case a 4-factor approximation algorithm is available [COCOON, 2012]. In this article, we improve upon the 4-factor approximation algorithm to design a linear-time algorithm that can rainbow colour a chordal graph G using at most 3/2 times the minimum number of colours if G is bridgeless and at most 5/2 times the minimum number of colours otherwise. Finally we show that the rainbow connection number of bridgeless chordal graphs cannot be polynomial-time approximated to a factor less than 5/4, unless P=NP.