NP-completeness of a family of graph-colouring problems

It is well known that the problem of graph k-colourability, for any k≥3, is NP-complete but that graph 2-colourability may be solved easily in polynomial time. An (s,r)-colouring of a graph G(s≥r≥1) is an assignment of r colours from a set of s to each vertex of G in such a way that no two adjacent vertices have a colour in common. The problem of (2r+1, r)-colourability for r = 1, 2, 3,… forms a family of increasingly restrictive colouring problems, the first of which is the standard 3-colourability problem. Each of these problems is shown to be NP-complete by constructing a polynomial transformation from 3-satisfiability to (2r+1, r)-colourability, valid for each value of r.     

Multi-degree cyclic scheduling of a no-wait robotic cell with multiple robots

This paper addresses cyclic scheduling of a no-wait robotic cell with multiple robots. In contrast to many previous studies, we consider r-degree cyclic (r > 1) schedules, in which r identical parts with constant processing times enter and leave the cell in each cycle. We propose an algorithm to find the minimal number of robots for all feasible r-degree cycle times for a given r (r > 1). Consequently, the optimal r-degree cycle time for any given number of robots for this given r can be obtained with the algorithm. To develop the algorithm, we first show that if the entering times of r parts, relative to the start of a cycle, and the cycle time are fixed, minimizing the number of robots for the corresponding r-degree schedule can be transformed into an assignment problem. We then demonstrate that the cost matrix for the assignment problem changes only at some special values of the cycle time and the part entering times, and identify all special values for them. We solve our problem by enumerating all possible cost matrices for the assignment problem, which is subsequently accomplished by enumerating intervals for the cycle time and linear functions of the part entering times due to the identification of the special values. The algorithm developed is shown to be polynomial in the number of machines for a fixed r, but exponential if r is arbitrary.     

A note on the complexity of finding regular subgraphs

Given a graph G and an integer r, does there exist a regular subgraph of G with degree r? In this note we establish NP-completeness for the r-regular subgraph problem for each r ? 3 and certain restrictions on G. In particular, the cubic subgraph problem is NP-complete even for the simple case where G is a bipartite planar graph with maximum degree 4.     

A new method of solving nonlinear mathematical programming problems involving r-invex functions

A new approach to a solution of a nonlinear constrained mathematical programming problem involving r-invex functions with respect to the same function η is introduced. An η-approximated problem associated with an original nonlinear mathematical programming problem is presented that involves η-approximated functions constituting the original problem. The equivalence between optima points for the original mathematical programming problem and its η-approximated optimization problem is established under r-invexity assumption.     

Approximation algorithms and hardness results for the clique packing problem

For a fixed family F of graphs, an F-packing in a graph G is a set of pairwise vertex-disjoint subgraphs of G, each isomorphic to an element of F. Finding an F-packing that maximizes the number of covered edges is a natural generalization of the maximum matching problem, which is just F={K₂}. In this paper we provide new approximation algorithms and hardness results for the K_r-packing problem where K_r={K₂,K₃,…,K_r}.We show that already for r=3 the K_r-packing problem is APX-complete, and, in fact, we show that it remains so even for graphs with maximum degree 4. On the positive side, we give an approximation algorithm with approximation ratio at most 2 for every fixed r. For r=3,4,5 we obtain better approximations. For r=3 we obtain a simple3/2-approximation, achieving a known ratio that follows from a more involved algorithm of Halldórsson. For r=4, we obtain a (3/2+?)-approximation, and for r=5 we obtain a (25/14+?)-approximation.     

The packing problem for projective geometries over GF(3) with dimension greater than five

An (n, d) set in the projective geometry PG(r, q) is a set of n points, no d of which are dependent. The packing problem is that of finding n(r, q, d), the largest size of an (n, d) set in PG(r, q). The packing problem for PG(r, 3) is considered. All of the values of n(r, 3, d) for r ? 5 are known. New results for r = 6 are n(6, 3, 5) = 14 and 20 ? n(6, 3, 4) ? 31. In general, upper bounds on n(r, q, d) are determined using a slightly improved sphere-packing bound, the linear programming approach of coding theory, and an orthogonal (n, d) set with the known extremal values of n(r, q, d)—values when r and d are close to each other. The BCH constructions and computer searches are used to give lower bounds. The current situation for the packing problem for PG(r, 3) with r ? 15 is summarized in a final table.     

A characterization for a graphic sequence to be potentially C r -graphic

Let r 3, n r and π = (d1, d2, . . . , dn) be a graphic sequence. If there exists a simple graph G on n vertices having degree sequence π such that G contains Cr (a cycle of length r) as a subgraph, then π is said to be potentially Cr-graphic. Li and Yin (2004) posed the following problem: characterize π = (d1, d2, . . . , dn) such that π is potentially Cr-graphic for r 3 and n r. Rao and Rao (1972) and Kundu (1973) answered this problem for the case of n = r. In this paper, this problem is solved completely.     

The Riesz Basis Property of an Indefinite Sturm–Liouville Problem with Non-Separated Boundary Conditions

We consider a regular indefinite Sturm–Liouville eigenvalue problem ?f′′ + q f = λ r f on [a, b] subject to general self-adjoint boundary conditions and with a weight function r which changes its sign at finitely many, so-called turning points. We give sufficient and in some cases necessary and sufficient conditions for the Riesz basis property of this eigenvalue problem. In the case of separated boundary conditions we extend the class of weight functions r for which the Riesz basis property can be completely characterized in terms of the local behavior of r in a neighborhood of the turning points. We identify a class of non-separated boundary conditions for which, in addition to the local behavior of r in a neighborhood of the turning points, local conditions on r near the boundary are needed for the Riesz basis property. As an application, it is shown that the Riesz basis property for the periodic boundary conditions is closely related to a regular HELP-type inequality without boundary conditions.     

COMPUTATIONAL COMPLEXITY OF（2,2） PATH CHROMATIC NUMBER PROBLEM

Is there a normal Pk coloring using r colors for a given graph ? This problem is called the (k, r) path chromatic number problem of graphs. This paper proves that the (2, 2) path chromatic number problem of graphs with maximum degree 4 is NP-complete.     

On the forbidden induced subgraph sandwich problem

We consider the sandwich problem, a generalization of the recognition problem introduced by Golumbic et al. (1995) [15], with respect to classes of graphs defined by excluding induced subgraphs. We prove that the sandwich problem corresponding to excluding a chordless cycle of fixed length k is NP-complete. We prove that the sandwich problem corresponding to excluding K_r?e for fixed r is polynomial. We prove that the sandwich problem corresponding to 3PC(⋅,⋅)-free graphs is NP-complete. These complexity results are related to the classification of a long-standing open problem: the sandwich problem corresponding to perfect graphs.     

Integer-friendly formulations for the r-separation problem

In this paper, we consider different formulations for the r-separation problem, where the objective is to choose as as many points as possible from a given set of points subject to the constraint that no two selected points can be closer than r units to one another. Our goal is to devise a mathematical programming formulation with an LP-relaxation which yields integer solutions with great frequency. We consider six different formulations of the r-separation problem. We show that the LP-relaxations of the most obvious formulations will yield fractional results in all instances of the problem if an optimal solution contains fewer than half of the given points. To build computationally effective formulations for the r-separation problem, we write dense constraints with unit right-hand-sides. The LP formulation that performs the best in our computational tests almost always finds 0–1 solutions to the problem.     

Ascending sequences in permutations

The problem of the number p(n , r), (1 ?r?n), of permutations on the set {1,…,n} with longest ascending subsequence of given length r is considered. By placing further restrictions on the ascending subsequence, combinatorial identities are obtained which allow the explicit calculation of p(n , r) in some cases.     

Non-linear multiparameter eigenvalue problems for ordinary differential equations

In this paper we consider the non-linear multiparameter eigenvalue problem in ordinary differential equations: y″_r(x_r) + q_r(x_r)y_r(x_r) + M_r(y_r) + ∑_{s = 1}ⁿμ_s(a_rs(x_r + P_rs) y_r(x_r) = 0, r = 1,…, n, where the non-linear functions M_rand P_rs will be required to satisfy certain Fréchet differentiability conditions. We study bifurcation from the simple eigenvalues of the corresponding linear problem and state a completeness theorem for the eigenfunctions of these systems.     

Moderate deviations and hypothesis testing for signal detection problem

We use moderate deviations to study the signal detection problem for a diffusion model.We establish a moderate deviation principle for the log-likelihood function of the diffusion model.Then applying the moderate deviation estimates to hypothesis testing for signal detection problem we give a decision region such that its error probability of the second kind tends to zero with faster speed than the error probability of the first kind when the error probability of the first kind is approximated by e-αr(T),where α>0,r(T)=o(T) and r(T) →∞ as the observation time T goes to infinity.     

Finiteness in restricted simplicial decomposition

Simplicial decomposition is an important form of decomposition for large non-linear programming problems with linear constraints. Von Hohenbalken has shown that if the number of retained extreme points is n + 1, where n is the number of variables in the problem, the method will reach an optimal simplex after a finite number of master problems have been solved (i.e., after a finite number of major cycles). However, on many practical problems it is infeasible to allocate computer memory for n + 1 extreme points. In this paper, we present a version of simplicial decomposition where the number of retained extreme points is restricted to r, 1 ? r ? n + 1, and prove that if r is sufficiently large, an optimal simplex will be reached in a finite number of major cycles. This result insures rapid convergence when r is properly chosen and the decomposition is implemented using a second order method to solve the master problem.     

A note on the m-center problem with rectilinear distances

Given n demand points on a plane, the problem we consider is to locate a given number, m, of facilities on the plane so that the maximum of the set of rectilinear distances of each demand point to its nearest facility is minimized. This problem is known as the m-center problem on the plane. A related problem seeks to determine, for a given r, the minimum number of facilities and their locations so as to ensure that every point is within r units of rectilinear distance from its nearest facility. We formulate the latter problem as a problem of covering nodes by cliques of an intersection graph. Certain bounds are established on the size of the problem. An efficient algorithm is provided to generate this set-covering problem. Computational results with this approach are summarized.     

Counting rises and levels in <Emphasis Type="Italic">r</Emphasis>-color compositions

An r-color composition of a positive integer n is a sequence of positive integers, called parts, summing to n in which each part of size r is assigned one of r possible colors. In this paper, we address the problem of counting the r-color compositions having a prescribed number of rises. Formulas for the relevant generating functions are computed which count the compositions in question according to a certain statistic. Furthermore, we find explicit formulas for the total number of rises within all of the r-color compositions of n having a fixed number of parts. A similar treatment is given for the problem of counting the number of levels and a further generalization in terms of rises of a particular type is discussed.     

The golden ratio and super central configurations of the n-body problem

In this paper, we consider the problem of central configurations of the n-body problem with the general homogeneous potential 1/rα. A configuration q=(q₁,q₂,…,qn) is called a super central configuration if there exists a positive mass vector m=(m₁,…,mn) such that q is a central configuration for m with mi attached to qi and q is also a central configuration for m^′, where m^′≠m and m^′ is a permutation of m. The main discovery in this paper is that super central configurations of the n-body problem have surprising connections with the golden ratio φ. Let r be the ratio of the collinear three-body problem with the ordered positions q₁, q₂, q₃ on a line. q is a super central configuration if and only if 1/r₁(α)<r<r₁(α) and r≠1, where r₁(α)>1 is a continuous function such that , the golden ratio. The existence and classification of super central configurations are established in the collinear three-body problem with general homogeneous potential 1/rα. Super central configurations play an important role in counting the number of central configurations for a given mass vector which may decrease the number of central configurations under geometric equivalence.     

The G/M/r machine interference model

This paper solves the machine interference problem in which N automatic machines are maintained by a team of r operatives. Repair times are assumed to follow a negative exponential distribution, and running times for each of the machines are assumed to be independently and identically distributed. It is shown that the solution to this G/M/r model is identical in most important respects to that for the M/M/r model.