Search

The Limited Packing and Multiple Domination problems in graphs have closely-related definitions and the same computational complexity on several graph classes. In this work we present two polynomial time reductions between them. Besides, we take into consideration generalized versions of these problems and obtain polynomial time reductions between each one and its generalized version. Fil: Leoni, Valeria Alejandra. Universidad Nacional de Rosario; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina Fil: Nasini, Graciela Leonor. Universidad Nacional de Rosario; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina

In the edge searching problem searchers move from vertex to vertex in a graph to capture an invisible fast intruder that may occupy either vertices or edges. Fast searching is a monotonic internal model in which at every move a new edge of the graph G must be guaranteed to be free of the intruder. That is once all searchers are placed the graph G is cleared in exactly vertical bar E(G)vertical bar moves. Such a restriction obviously necessitates a larger number of searchers. We examine this model and characterize graphs for which 2 or 3 searchers are sufficient. We prove that the corresponding decision problem is NP-complete. (C) 2013 Elsevier B.V. All rights reserved.

We show that testing if an undirected graph contains a bridgeless spanning cactus is NP-hard. As a consequence, the minimum spanning cactus problem (MSCP) on an undirected graph with 0–1 edge weights is NP-hard. For any subgraph S of Kn, we give polynomially testable necessary and sufficient conditions for S to be extendable to a cactus in Kn and the weighted version of this problem is shown to be NP-hard. A spanning tree is shown to be extendable to a cactus in Kn if and only if it has at least one node of even degree. When S is a spanning tree, we show that the weighted version can also be solved in polynomial time. Further, we give an O(n3) algorithm for computing a minimum cost spanning tree with at least one vertex of even degree on a graph on n nodes. Finally, we show that for a complete graph with edge-costs satisfying the triangle inequality, the MSCP is equivalent to a general class of optimization problems that properly includes the traveling salesman problem and they all have the same approximation hardness.

Motivated by problems in comparative genomics and paleogenomics, we study the computational complexity of the Gapped Consecutive-Ones Property ((k,δ)-C1P) Problem: given a binary matrix M and two integers k and δ, decide if the columns of M can be permuted such that each row contains at most k blocks of ones and no two neighboring blocks of ones are separated by a gap of more than δ zeros. The classical C1P decision problem, which is known to be polynomial-time solvable is equivalent to the (1,0)-C1P problem. We extend our earlier results on this problem [C. Chauve, J. Mauch, M. Patterson, On the gapped consecutive-ones property, in: Proceedings of the European Conference on Combinatorics, Graphs Theory and Applications (EuroComb), in: Electronic Notes in Discrete Mathematics, vol. 34, 2009, pp. 121-125] to show that for every k

International audience; This paper studies the following line balancing problem with uncertain operation execution times. Operations on the same product have to be assigned to the stations of a transfer line. The product moves along the stations in the same direction, and operations assigned to the same station are executed sequentially. Exclusion, inclusion and precedence relations are given on the set of operations. Operation execution times are uncertain in the sense that their set belongs to a given set of scenarios. The objective is to minimize the line cycle time, which is equal to the maximum total execution time of operations of the same station, for the worst scenario. An approach to reducing the scenario set is described. Several special cases of the problem are proved NP-hard and strongly NP-hard. Enumerative dynamic programming algorithms and problem-specific polynomial time algorithms are suggested for some cases.

International audience; We survey known results about the complexity of surjective homomorphism problems, studied in the context of related problems in the literature such as list homomorphism, retraction and compaction. In comparison with these problems, surjective homomorphism problems seem to be harder to classify and we examine especially three concrete problems that have arisen from the literature, two of which remain of open complexity.

This paper is aimed at investigating some computational aspects of different isoperimetric problems on weighted trees. In this regard, we consider different connectivity parameters called minimum normalized cuts/isoperimetric numbers defined through taking the minimum of the maximum or the mean of the normalized outgoing flows from a set of subdomains of vertices, where these subdomains constitute a partition/subpartition. We show that the decision problem for the case of taking k-partitions and the maximum (called the max normalized cut problem NCPM), and the other two decision problems for the mean version (referred to as IPPm and NCPm) are NP-complete problems for weighted trees. On the other hand, we show that the decision problem for the case of taking k-subpartitions and the maximum (called the max isoperimetric problem IPPM) can be solved in linear time for any weighted tree and any k≥2. On the basis of this fact, we provide polynomial time O(k)-approximation algorithms for all different versions of the kth isoperimetric numbers considered.Moreover, for when the number of partitions/subpartitions, k, is a fixed constant, we prove, as an extension of a result of Mohar (1989) [20] for the case k=2 (usually referred to as the Cheeger constant), that the max and mean isoperimetric numbers of weighted trees, and their max minimum normalized cut can be computed in polynomial time. We also prove some hardness results for the case of simple unweighted graphs and trees.

We address an optimization problem in which two agents, each with a set of weighted items, compete in order to maximize the total weight of their winning sets. The latter are built according to a sequential game consisting in a fixed number of rounds. In every round each agent submits one item for possible inclusion in its winning set. We study two natural rules to decide the winner of each round.For both rules we deal with the problem from different perspectives. From a centralized point of view, we investigate (i) the structure and the number of efficient (i.e. Pareto optimal) solutions, (ii) the complexity of finding such solutions, (iii) the best–worst ratio, i.e. the ratio between the efficient solution with largest and smallest total weight, and (iv) existence of Nash equilibria.Finally, we address the problem from a single agent perspective. We consider preventive or maximin strategies, optimizing the objective of the agent in the worst case, and best response strategies, where the items submitted by the other agent are known in advance either in each round (on-line) or for the whole game (off-line).

This note presents a generic approach to proving NP-hardness of unconstrained partition type problems, namely partitioning a given set of entities into several subsets such that a certain objective function of the partition is optimized. The idea is to represent the objective function of the problem as a function of aggregate variables, whose optimum is achieved only at the points where problem Partition (if proving ordinary NP-hardness), or problem 3-Partition or Product Partition (if proving strong NP-hardness) has a solution. The approach is demonstrated on a number of discrete optimization and scheduling problems.

We investigate the complexity of satisfiability problems for {∪,∩,−,+,×}-circuits computing sets of natural numbers. These problems are a natural generalization of membership problems for expressions and circuits studied by Stockmeyer and Meyer (1973) [10] and McKenzie and Wagner (2003) [8].Our work shows that satisfiability problems capture a wide range of complexity classes such as NL, P, NP, PSPACE, and beyond. We show that in several cases, satisfiability problems are harder than membership problems. In particular, we prove that testing satisfiability for {∩,+,×}-circuits is already undecidable. In contrast to this, the satisfiability for {∪,+,×}-circuits is decidable in PSPACE.

In this paper, we analyse the computational complexity of an optimization version of the Simplified Partial Digest Problem (SPDP), which is a mathematical model for DNA mapping based on the results of a simplified partial digest experiment. We prove that recognizing 46.16% of the elements of the DNA map in the error-free simplified partial digest experiment is NP-hard in the strong sense. This implies that the problem of maximizing the number of correct elements of the DNA map in the error-free simplified partial digest experiment is pseudopolynomially non-approximable with the approximation ratio ρ=136.

Given a digraph D, the Minimum Leaf Out-Branching problem (MinLOB) is the problem of finding in D an out-branching with the minimum possible number of leaves, i.e., vertices of out-degree zero. Gutin, Razgon and Kim [G. Gutin, I. Razgon, E.J. Kim, Minimum leaf out-branching problems, in: Proc. 4th International Conference on Algorithmic Aspects in Information and Management, AAIM’08, in: Lect. Notes Comput. Sci., vol. 5034 2008, pp. 235–246] proved that MinLOB is polynomial time solvable for acyclic digraphs which are exactly the digraphs of directed path-width (DAG-width, directed tree-width, respectively) 0. We investigate how much one can extend this polynomiality result. We prove that already for digraphs of directed path-width (directed tree-width, DAG-width, respectively) 1, MinLOB is NP-hard. On the other hand, we show that for digraphs of restricted directed tree-width (directed path-width, DAG-width, respectively) and a fixed integer k, the problem of checking whether there is an out-branching with at most k leaves is polynomial time solvable.

The computation of all minimal transversals of a given hypergraph in output-polynomial time is a long standing open question known as Transversal Hypergraph Generation. One of the first attempts at this problem—the sequential method [Claude Berge, Hypergraphs, in: North-Holland Mathematical Library, vol. 45, North-Holland, 1989]—is not output-polynomial as was shown by Takata [Ken Takata, A worst-case analysis of the sequential method to list the minimal hitting sets of a hypergraph, SIAM Journal on Discrete Mathematics 21 (4) (2007) 936–946]. Recently, three new algorithms improving the sequential method were published and experimentally shown to perform very well in practice [James Bailey, Thomas Manoukian, Kotagiri Ramamohanarao, A fast algorithm for computing hypergraph transversals and its application in mining emerging patterns, in: Proceedings of the 3rd IEEE International Conference on Data Mining, ICDM 2003, 19–22 December 2003, Melbourne, FL, USA, IEEE Computer Society, 2003, pp. 485–488; Guozhu Dong, Jinyan Li, Mining border descriptions of emerging patterns from dataset pairs, Knowledge and Information Systems 8 (2) (2005) 178–202; Dimitris J. Kavvadias, Elias C. Stavropoulos, An efficient algorithm for the transversal hypergraph generation, Journal of Graph Algorithms and Applications 9 (2) (2005) 239–264]. Nevertheless, a theoretical worst-case analysis has been pending. We close this gap by proving lower bounds for all three algorithms. Thereby, we show that none of them are output-polynomial.

We study the University Course Timetabling Problem (UCTP). In particular we deal with the following question: is it possible to decompose UCTP into two problems, namely, (i) a time scheduling, and (ii) a space scheduling. We have arguments that it is not possible. Therefore we study UCTP with the assumption that each room belongs to exactly one type of room. A type of room is a set of rooms, which have similar properties. We prove that in this case UCTP is polynomially reducible to time scheduling. Hence we solve UCTP with the following method: at first we solve time scheduling and subsequently we solve space scheduling with a polynomial O(n3) algorithm. In this way we obtain a radical (exponential) speed-up of algorithms for UCTP. The method was applied at P.J. Šafárik University.

Clustering problems with relational constraints in which the underlying graph is a tree arise in a variety of applications: hierarchical data base paging, communication and distribution networks, districting, biological taxonomy, and others. They are formulated here as optimal tree partitioning problems. In a previous paper, it was shown that their computational complexity strongly depends on the nature of the objective function and, in particular, that minimizing the total within-cluster dissimilarity or the diameter is computationally hard. We propose heuristics that find good partitions within a reasonable time, even for instances of relatively large size. Such heuristics are based on the solution of continuous relaxations of certain integer (or almost integer) linear programs. Experimental results on over 2000 randomly generated instances with up to 500 entities show that the values (total within-cluster dissimilarity or diameter) of the solutions provided by these heuristics are quite close to the minimum one.

When piling a set of items in a single stack, one often does not pay attention to the order. Real-life experience suggests that, whenever a specific item is suddenly requested, we need to dig very deep into the stack to extract it.In this paper we investigate stack reordering strategies aiming at minimizing the number of pop and push operations. In particular we focus on three versions of the problem in which reordering can take place in different phases: when unloading the stack, when loading it or in both phases. We show that the first two variants can be solved in linear time, while for the third one we devise a dynamic programming method with quadratic complexity.

The restricted homomorphism problem RHP(H,Y) asks: given an input digraph G and a homomorphism g:G→Y, does there exist a homomorphism f:G→H? We prove that if H is hereditarily hard and Y↛H, then RHP(H,Y) is NP-complete. Since non-bipartite graphs are hereditarily hard, this settles in the affirmative a conjecture of Hell and Nešetřil.

The notion of strong p-Helly hypergraphs was introduced by Golumbic and Jamison in 1985 [M.C. Golumbic, R.E. Jamison, The edge intersection graphs of paths in a tree, J. Combin. Theory Ser. B 38 (1985) 8–22]. Independently, other authors [A. Bretto, S. Ubéda, J. Žerovnik, A polynomial algorithm for the strong Helly property. Inform. Process. Lett. 81 (2002) 55–57, E. Prisner, Hereditary clique-Helly graphs, J. Combin. Math. Combin. Comput. 14 (1993) 216–220, W.D. Wallis, Guo-Hui Zhang, On maximal clique irreducible graphs. J. Combin. Math. Combin. Comput. 8 (1990) 187–193.] have also considered the strong Helly property in other contexts. In this paper, we characterize strong p-Helly hypergraphs. This characterization leads to an algorithm for recognizing such hypergraphs, which terminates within polynomial time whenever p is fixed. In contrast, we show that the recognition problem is co-NP-complete, for arbitrary p. Further, we apply the concept of strong p-Helly hypergraphs to the cliques of a graph, leading to the class of strong p-clique-Helly graphs. For p=2, this class is equivalent to that of hereditary clique-Helly graphs [E. Prisner, Hereditary clique-Helly graphs, J. Combin. Math. Combin. Comput. 14 (1993) 216–220]. We describe a characterization for this class and obtain an algorithm for recognizing such graphs. Again, the algorithm has polynomial-time complexity for p fixed, and we show the corresponding recognition problem to be NP-hard, for arbitrary p.

By use of elementary geometric arguments we prove the existence of a special integral solution of a certain system of linear equations. The existence of such a solution then yields the NP-hardness of the decision problem on the existence of locally injective homomorphisms to Theta graphs with three distinct odd path lengths.

The following problem is considered: given a Boolean formula f, generate another formula g such that: (i) If f is unsatisfiable then g is also unsatisfiable. (ii) If f is satisfiable then g is also satisfiable and furthermore g is “easier” than f. For the measure of this easiness, we use the density of a formula f which is defined as (the number of satisfying assignments)/2n, where n is the number of Boolean variables of f. In this paper, we mainly consider the case that the input formula f is given as a 3-CNF formula and the output formula g may be any formula using Boolean AND, OR and negation. Two different approaches to this problem are presented: one is to obtain g by reducing the number of variables and the other by increasing the number of variables, both of which are based on existing SAT algorithms. Our performance evaluation shows that, a little surprisingly, better SAT algorithms do not always give us better density-condensation algorithms.

The minimum vertex ranking spanning tree problem (MVRST) is to find a spanning tree of G whose vertex ranking is minimum. In this paper, we show that MVRST is NP-hard. To prove this, we polynomially reduce the 3-dimensional matching problem to MVRST. Moreover, we present a (⌈Ds/2⌉+1)/(⌊log2(Ds+1)⌋+1)-approximation algorithm for MVRST where Ds is the minimum diameter of spanning trees of G.

The objective of this study was to distinguish within a population of patients with and without breast cancer. The study was based on the University of Wisconsin's dataset of 569 patients, of whom 212 were subsequently found to have breast cancer. A subset-conjunctive model, which is related to Logical Analysis of Data, is described to distinguish between the two groups of patients based on the results of a non-invasive procedure called Fine Needle Aspiration, which is often used by physicians before deciding on the need for a biopsy. We formulate the problem of inferring subset-conjunctive rules as a 0–1 integer program, show that it is NP-Hard, and prove that it admits no polynomial-time constant-ratio approximation algorithm. We examine the performance of a randomized algorithm, and of randomization using LP rounding. In both cases, the expected performance ratio is arbitrarily bad. We use a deterministic greedy algorithm to identify a Pareto-efficient set of subset-conjunctive rules; describe how the rules change with a re-weighting of the type-I and type-II errors; how the best rule changes with the subset size; and how much of a tradeoff is required between the two types of error as one selects a more stringent or more lax classification rule. An important aspect of the analysis is that we find a sequence of closely related efficient rules, which can be readily used in a clinical setting because they are simple and have the same structure as the rules currently used in clinical diagnosis.

The paper proves that data-independent neighborhood functions with the smooth property (all strict local optima are global optima) for maximum 3-satisfiability (MAX 3-SAT) must contain all possible solutions for large instances. Data-independent neighborhood functions with the smooth property for 0–1 knapsack are shown to have size with the same order of magnitude as the cardinality of the solution space. Data-independent neighborhood functions with the smooth property for traveling salesman problem (TSP) are shown to have exponential size. These results also hold for certain polynomially solvable sub-problems of MAX 3-SAT, 0–1 knapsack and TSP.

In this paper we investigate the problem of computing optimal lottery schemes. From a computational complexity point of view, we prove that the variation of this problem in which the sets to be covered are specified in the input is log |I|-approximable (where I denotes the collection of sets to be covered) and it cannot be approximated within a factor smaller than log |I|, unless P = NP. From a combinatorial point of view, we propose new constructions based on the combination of the partitioning technique and of known results regarding the construction of sets of coverings. By means of this combination we will be able to improve several upper bounds on the cardinality of optimal lottery schemes.

In several applications the solutions of combinatorial optimization problems (COP) are required to satisfy an additional cardinality constraint, that is to contain a fixed number of elements. So far the family of (COP) with cardinality constraints has been little investigated. The present work tackles a new problem of this class: the k-cardinality minimum cut problem (k-card cut). For a number of variants of this problem we show complexity results in the most significant graph classes. Moreover, we develop several heuristic algorithms for the k-card cut problem for complete, complete bipartite, and general graphs. Lower bounds are obtained through an SDP formulation, and used to show the quality of the heuristics. Finally, we present a randomized SDP heuristic and numerical results.

This paper considers the problem of computing the squared volume of a largest j-dimensional simplex in an arbitrary d-dimensional polytope P given by its vertices (a "V-polytope"), for arbitrary integers j and d with 1 ≤ j ≤ d. The problem was shown by Gritzmann, Klee and Larman to be NP-hard. This paper examines the possible accuracy of deterministic polynomial-time approximation algorithms for the problem. On the negative side, it is shown that unless P = NP, no such algorithm can approximately solve the problem within a factor of less than 1.09. It is also shown that the NP-hardness and inapproximability continue to hold when the polytope P is restricted to be an affine crosspolytope.On the positive side, a simple deterministic polynomial-time approximation algorithm for the problem is described. The algorithm takes as input integers j and d with 1 ≤ j ≤ d and a V-polytope P of dimension d. It returns a j-simplex S ⊂ P such that vol2(T)/vol2(S) ≤ A(Bj)j, where T is any largest j-simplex in P, and A and B are positive constants independent of j, d, P.

This paper concerns the optimal partition of a graph into p connected clusters of vertices, with various constraints on their topology and weight. We consider different objectives, depending on the cost of the trees spanning the clusters. This rich family of problems mainly applies to telecommunication network design, but it can be useful in other fields. We achieve a complete characterization of its computational complexity, previously studied only for special cases: a polynomial algorithm based on a new matroid solves the easy cases; the others are strongly NP-hard by direct reduction from SAT. Finally, we give results on special graphs.

In this paper we introduce the concept of a boundary class, which is a helpful tool for classification of hereditary classes of graphs according to the complexity of the independent set problem. It is shown that in a class X defined by a finite set of forbidden induced subgraphs, the problem is NP-hard if and only if X includes a boundary class. The paper presents a particular boundary class and establishes several new polynomially solvable cases for the independent set problem.

This paper introduces a new subclass of machine scheduling problems in which due dates are treated as variables and must be assigned to the individual jobs. A solution then is a sequence of jobs along with due date assignments. In contrast to existing due date assignment models, solutions to the proposed problems do not depend on predetermined rules or the requirement that due dates be assigned in the same order as the sequence. The single machine case is investigated in detail. Complexity results are presented for all common objective functions and processing restrictions. The analysis shows that in a number of instances polynomial time algorithms are available though most problems that are intractable under traditional due date definitions remain so.

A mixed hypergraph is a pair H = (V, E ∪ A), where V is the vertex set and E (A) the edge (the co-edge) set of H. A legal colouring of H gives the same (different) colour(s) to at least two vertices of any co-edge (of any edge). The upper chromatic number of H is the maximum number X(H) of colours that can be used in a legal colouring. After giving a general upper bound to X(H), we here consider the co-hypergraph J = (X,φ ∪ I), where I is a (v3,b2)- configuration I over X. We prove that computing X(J) is NP-hard, but there exists a polynomial-time algorithm returning a colouring with ≥ 5/6 X(J) colours. We also provide an example showing that this approximation factor is tight.

In this paper we propose a general algorithm for the asymmetric traveling salesman problem (ATSP) on a complete digraph on n nodes which computes a tour with cost no more than a pre-specified upper bound. A special case of this algorithm is shown to have complexity O(n2) and domination number at least ∑ k=0 n−2 (k!) . Extending this result, we show that by investing O(nk) effort, for k⩾2 and integer, it is possible to obtain a solution which is at least as good as θ= ∑ i=0 ⌊(n−2)/(k−1)⌋ (n−1−i(k−1))! n−k−i(k−1)! −(n−k−1−i(k−1)))! +(z−2)! alternative tours, where z=n mod (k−1) . Further, we present a patching algorithm for the ATSP and show that it has a domination number at least (n−2)!. Since the symmetric traveling salesman problem can be formulated as an ATSP, these algorithms are applicable in this case too. However, in this case the guaranteed lower bound on the domination number would be half that of the corresponding ATSP algorithm.

In a recent paper [Discrete Appl. Math. 43 (1993) 115–129], Kern formulates two conjectures on the relationship between the computational complexity of computing the depth function of a discrete optimization problem and the computational complexity of solving this optimization problem to optimality. In this note (that might be considered to be a kind of erratum to Kern's paper), we exhibit simple counterexamples to both conjectures under the assumption P≠NP.

We consider two graph invariants that are used as a measure of nonplanarity: the splitting number of a graph and the size of a maximum planar subgraph. The splitting number of a graph G is the smallest integer k ≥ 0, such that a planar graph can be obtained from G by k splitting operations. Such operation replaces a vertex v by two nonadjacent vertices v1 and v2, and attaches the neighbors of v either to v1 or to v2. We prove that the splitting number decision problem is NP-complete, even when restricted to cubic graphs. We obtain as a consequence that planar subgraph remains NP-complete when restricted to cubic graphs. Note that NP-completeness for cubic graphs also implies NP-completeness for graphs not containing a subdivision of K5 as a subgraph.

A visit of a graph is a permutation of its vertices which establishes the order in which these are considered. In this paper we deal with the problem of determining visits that perform well in terms of accumulated edges, where at a given step of the visit an edge is accumulated iff both its endpoints have already been considered at that step. Several visits of this kind are here defined, the notion of strong and weak visiability presented, and the problem of deciding whether a graph can be correctly visited or not is considered. Such a problem is computationally hard in various versions. We then analyze necessary and sufficient conditions for graph visitability, characterize some a.e. visitable classes of graphs, describe polynomial-time algorithms to solve particular problem instances, and give heuristics and approximation algorithms for some intractable cases.

We provide two polynomial-time exact algorithms to compute a maximum stable set in graphs that are respectively ( P 6 , triangle)-free, and ( P 6 , C 4 )-free. The algorithm devised for ( P 6 , C 4 )-free graphs is based on the search of simple augmenting trees and can be extended to heuristically solve the problem in a general graph.

In this paper we address the complexity of postoptimality analysis of 0 1 programs with a linear objective function. After an optimal solution has been determined for a given cost vector, one may want to know how much each cost coefficient can vary individually without affecting the optimality of the solution. We show that, under mild conditions, the existence of a polynomial method to calculate these maximal ranges implies a polynomial method to solve the 0 1 program itself. As a consequence, postoptimality analysis of many well-known NP-hard problems cannot be performed by polynomial methods, unless P =NP. A natural question that arises with respect to these problems is whether it is possible to calculate in polynomial time reasonable approximations of the maximal ranges. We show that it is equally unlikely that there exists a polynomial method that calculates conservative ranges for which the relative deviation from the true ranges is guaranteed to be at most some constant. Finally, we address the issue of postoptimality analysis ofe-optimal solutions of NP-hard 0 1 problems. It is shown that for an e-optimal solution that has been determined in polynomial time, it is not possible to calculate in polynomial time the maximal amount by which a cost coefficient can be increased such that the solution remains e-optimal, unless P = NP.

We discuss the computational complexity of the multidimensional periodic scheduling problem. This problem originates from the assignment of periodic tasks to processing units over time and it is related to the design of high-performance video signal processors. We present a model of multidimensional periodic operations and introduce the multidimensional periodic scheduling problem. Next, we show that this problem and two related sub-problems are NP-hard. Further-more, we identify several special cases induced by practical situations, of which some are proven to be polynomially solvable.

Let Qc,r be the integer hull of the intersection of the assignment polytope with a given hyper-plane H = {x = (xij) ϵ Rn × n: ∑ni = 1 ∑nj = 1 cijxij = r}. We show that the problem of checking whether two given extreme points of Qc,r are nonadjacent on Qc,r is solvable in O (n5) time if c = (cij) is a 0–1 matrix, and that it is NP-Complete if c is a general integer matrix.

We suggest a uniform game-theoretic approach to “width” graph parameters. We consider a search problem on a graph in which one cop in a helicopter flying from vertex to vertex tries to catch the robber. The existence of the winning program for the cop in this problem depends only on the robber's speed. We investigate the problem of finding the minimal robber's speed which prevents the cop from winning. We examine two cases of the problem. In the first one the cop can visit each vertex of a graph only once. In the second case the cop cannot afford “recontamination” of vertices. We show that in the first case the problem of finding the minimal robber's speed is equivalent to the bandwidth minimization problem. In the second case we show that the problem is equivalent to the natural generalization of the bandwidth problem and is closely approximated by the pathwidth. Also we show that the problem of computing the minimal robber's speed is NP-hard in both cases.

The problem of scheduling a set of unit-time jobs on m uniform machines is studied. Some jobs may require a unit of an additional single resource during their execution. The resource is renewable but the total resource consumption is limited by the same value at each time instant. The objective is to find a feasible schedule minimizing the maximum job completion time. We show that an approach suggested in the literature to solve this problem is incorrect. Then we present an O(m log m) algorithm for the problem with no machine idle times and a linear-time algorithm for the problem with identical machines.

In the well-knownSubset Sum Problem, we are given positive integersa1, ..., an andt and are to determine if some subset of theai sums tot. We investigate the boundary between easy and hard variations of this problem. In particular, we consider the cases where the sequencea1, ..., an is an arithmetic progression, a chain or superincreasing and where theai may be replicated. We also consider related problems.

This paper studies the notion of “depth” of a combinatorial optimization problem, which has already been touched on by several other authors (cf. Weber or Hajek). This notion can be defined as follows: Consider a discrete optimization problem min { c ( x | x ∈ X }. Usually hill climbing algorithms work as follows: First, a neighbourhood structure has to be specified on X . Then, starting from an arbitrary solution, say x 0 , one constructs a sequence x 0 , x 1 , x 2 … (hopefully leading to an optimum) such that x i is a neighbour of x i −1 for all i . For x 0 ∈ X , the depth d ( x 0 ) is defined to be the smallest d ≥ 0 such that there exists a sequence x 0 , x 1 ,…, x n with c ( x n ) c ( x 0 ) and all intermediate solutions x i having objective value c ( x i ) ≤ c ( x 0 ) + d . The depth of the problem is defined to be the maximum depth of a solution x 0 ∈ X . This notion plays an important role in the theory of Simulated Annealing. Here we want to show that the depth is of some interest in its own right. We will prove some upper bounds and investigate the computational complexity of the depth function for some selected examples.

It is well known that one can obtain facets and valid inequalities for the knapsack polytope by lifting simple inequalities associated with minimal covers. We study the complexity of lifting. We show that recognizing integral lifted facets or valid inequalities can be done in O(n2) time, even if the minimal cover from which they are lifted is not given. We show that the complexities of recognizing nonintegral lifted facets and valid inequalities are similar, respectively, to those of recognizing general (not necessarily lifted) facets and valid inequalities. Finally, we show that recognizing valid inequalities is in co- NPC while recognizing facets is in Dn. The question of whether recognizing facets is complete for Dn is open.

We consider a family of generalized matching problems called k-feasible matching (k-RM) problems, where k ϵ {1,2,3,…} ∪ {∞}. We show each k-FM problem to be NP-complete even for very restricted cases. We develop a dynamic programming algorithm that solves in polynomial time the k-FM problem for graphs with width bounded by 2k. We also show that for any subset S of {1,2,…} ∪ {∞}, there is a set D of problem instances such that for k in S the k-FM problem is NP-complete on D, while for k not in S the k-FM problem is polynomially solvable on D.