We study the computational complexity of the dominating set problem for hereditary graph classes, i.e., classes of simple unlabeled graphs closed under deletion of vertices. Every hereditary class can be defined by a set of its forbidden induced subgraphs. There are numerous open cases for the complexity of the problem even for hereditary classes with small forbidden structures. We completely determine the complexity of the problem for classes defined by forbidding a five-vertex path and any set of fragments with at most five vertices. Additionally, we also prove polynomial-time solvability of the problem for some two classes of a similar type. The notion of a boundary class is a helpful tool for analyzing the computational complexity of graph problems in the family of hereditary classes. Three boundary classes were known for the dominating set problem prior to this paper. We present a new boundary class for it.

In this paper a fast greedy sequential heuristic for the vertex colouring problem is presented. The suggested algorithm builds the same colouring of the graph as the well-known greedy sequential heuristic in which on every step the current vertex is coloured in the minimum possible colour. Our main contributions include introduction of a special matrix of forbidden colours and application of efficient bitwise operations on bit representations of the adjacency and forbidden colours matrices. Computational experiments show that in comparison with the classical greedy heuristic the average speedup of the developed approach is 2.6 times on DIMACS instances.

The notion of a tolerance is a helpful tool for designing approximation and exact algorithms for solving combinatorial optimization problems. In this paper we suggest a tolerance-based polynomial heuristic algorithm for the weighted independent set problem. Several computational experiments show that our heuristics works very well on graphs of a small density

The notion of a boundary graph class was recently introduced for a classification of hereditary graph classes according to the complexity of a considered problem. Two concrete graph classes are known to be boundary for several graph problems. We formulate a criterion to determine whether these classes are boundary for a given graph problem or not. We also demonstrate that the classes are simultaneously boundary for some continuous set of graph problems and they are not simultaneously boundary for another set of the same cardinality. Both families of problems are constituted by variants of the maximum induced subgraph problem.

In this paper, we demonstrate that the search for weighing matrices constructed from two circulants can be viewed as a minimization problem together with two competent genetic algorithms to locate optima of an objective function. The motivation to deal with the messy genetic algorithm (mGA) is given from the pioneering results of Goldberg, regarding the ability of the mGA to put tight genes together in a solution which points directly to structural patterns in weighing matrices. In order to take into advantage certain properties of two ternary sequences with zero autocorrelation we use an adaptation of the fast messy GA (fmGA) where we combine mGA with advanced techniques, such as thresholding and tie-breaking. This transformation of the weighing matrices problem to an instance of a combinatorial optimization problem seems to be promising, since we resolved two open cases for weighing matrices as these are listed in the second edition of the Handbook of Combinatorial Designs.

Before a knock-out tournament starts, the participants are assigned to positions in the tournament bracket through a process known as seeding. There are many ways to seed a tournament. In this paper, we solve a discrete optimization problem of finding a seeding that maximizes spectator interest in a tournament when spectators are interested in matches with high competitive intensity (i.e., matches that involve teams comparable in strength) and high quality (i.e., matches that involve strong teams). We find a solution to the problem under two assumptions: the objective function is linear in quality and competitive intensity and a stronger team beats a weaker one with sufficiently high probability. Depending on parameters, only two special classes of seedings can be optimal. While one of the classes includes a seeding that is often used in practice, the seedings in the other class are very different. When we relax the assumption of linearity, we find that these classes of seedings are in fact optimal in a sizable number of cases. In contrast to existing literature on optimal seedings, our results are valid for an arbitrarily large number of participants in a tournament.

In this paper, we use a pseudo-Boolean formulation of the p-median problem and using data aggregation, provide a compact representation of p-median problem instances. We provide computational results to demonstrate this compactification in benchmark instances. We then use our representation to explain why some p-median problem instances are more difficult to solve to optimality than other instances of the same size. We also derive a preprocessing rule based on our formulation, and describe equivalent p-median problem instances, which are identical sized instances which are guaranteed to have identical optimal solutions.

In this paper, we present fixed-parameter tractable algorithms for special cases of the shortest lattice vector, integer linear programming, and simplex width computation problems, when matrices included in the problems’ formulations are near square. The parameter is the maximum absolute value of the rank minors in the corresponding matrices. Additionally, we present fixed-parameter tractable algorithms with respect to the same parameter for the problems, when the matrices have no singular rank submatrices.

In this paper we present improvements to one of the most recent and fastest branch-and-bound algorithm for the maximum clique problem—MCS algorithm by Tomita et al. (Proceedings of the 4th international conference on Algorithms and Computation, WALCOM’10, pp. 191–203, 2010). The suggested improvements include: incorporating of an efficient heuristic returning a high-quality initial solution, fast detection of clique vertices in a set of candidates, better initial colouring, and avoiding dynamic memory allocation. Our computational study shows some impressive results, mainly we have solved p_hat1000-3 benchmark instance which is intractable for MCS algorithm and got speedups of 7, 3000, and 13000 times for gen400_p0.9_55, gen400_p0.9_65, and gen400_p0.9_75 instances correspondingly.

We consider an undirected graph $G = (VG, EG)$ with a set $T \subseteq VG$ of terminals, and with nonnegative integer capacities $c(v)$ and costs $a(v)$ of nodes $v\in VG$. A path in $G$ is a \emph{$T$-path} if its ends are distinct terminals. By a \emph{multiflow} we mean a function $F$ assigning to each $T$-path $P$ a nonnegative rational \emph{weight} $F(P)$, and a multiflow is called \emph{feasible} if the sum of weights of $T$-paths through each node $v$ does not exceed $c(v)$. The emph{value} of $F$ is the sum of weights $F(P)$, and the \emph{cost} of $F$ is the sum of $F(P)$ times the cost of $P$ w.r.t. $a$, over all $T$-paths $P$. Generalizing known results on edge-capacitated multiflows, we show that the problem of finding a minimum cost multiflow among the feasible multiflows of maximum possible value admits \emph{half-integer} optimal primal and dual solutions. Moreover, we devise a strongly polynomial algorithm for finding such optimal solutions.

A new variant of multi-depot vehicle routing problem with time windows is studied. In the new variant, the depot where the vehicle ends is flexible, namely, it is not entirely the same as the depot that it starts from. An integer programming model is formulated with the minimum total traveling cost under the constrains of time window, capacity and route duration of the vehicle, the fleet size and the number of parking spaces of each depot. As the problem is an NP-Hard problem, a hybrid genetic algorithm with adaptive local search is proposed to solve it. Finally, the computational results show that the proposed method is competitive in terms of solution quality. Compared with the classic MDVRPTW, allowing flexible choice of the stop depot can further reduce total traveling cost.

We address the complexity class of several problems related to finding a path in a properly colored directed graph. A properly colored graph is defined as a graph G whose vertex set is partitioned into X(G) stable subsets, where X(G) denotes the chromatic number of G. We show that to find a simple path that meets all the colors in a properly colored directed graph is NP-complete, and so are the problems of finding a shortest and longest of such paths between two specific nodes.

We consider the coloring problem for hereditary graph classes, i.e. classes of simple unlabeled graphs closed under deletion of vertices. For the family of the hereditary classes of graphs defined by forbidden induced subgraphs with at most four vertices, there are three classes with an open complexity of the problem. For the problem and the open three cases, we present approximation polynomial-time algorithms with performance guarantees.

The complexity of the coloring problem is known for all hereditary classes defined by two connected 5-vertex forbidden induced subgraphs except 13 cases. We update this result by proving polynomial-time solvability of the problem for two of the mentioned 13 classes.