Complexity results on restricted instances of a paint shop problem for words

We study the following problem: an instance is a word with every letter occurring twice. A solution is a 2-coloring of its letters such that the two occurrences of every letter are colored with different colors. The goal is to minimize the number of color changes between adjacent letters.This is a special case of the paint shop problem for words, which was previously shown to be NP-complete. We show that this special case is also NP-complete and even APX-hard. Furthermore, derive lower bounds for this problem and discuss a transformation into matroid theory enabling us to solve some specific instances within polynomial time.     

The polynomial dichotomy for three nonempty part sandwich problems

We classify into polynomial time or NP-complete all three nonempty part sandwich problems. This solves the polynomial dichotomy for this class of problems.     

Scheduling dual gripper robotic cell: One-unit cycles

We consider the scheduling problem of cyclic production in a bufferless dual-gripper robot cell processing a family of identical parts. The objective is to find an optimal sequence of robot moves so as to maximize the long-run average throughput rate of the cell. While there has been a considerable amount of research dealing with single-gripper robot cells, there are only a few papers devoted to scheduling in dual-gripper robotic cells. From the practical point of view, the use of a dual gripper offers the attractive prospect of an increase in the cell productivity. At the same time, the increase in the combinatorial possibilities associated with a dual-gripper robot severely complicates its theoretical analysis. The purpose of this paper is to extend the existing conceptual framework to the dual-gripper situation, and to provide some insight into the problem.We provide a notational and modelling framework for cyclic production in a dual-gripper robotic cell. Focusing on the so-called active cycles, we discuss the issues of feasibility and explore the combinatorial aspects of the problem. The main attention is on 1-unit cycles, i.e., those that restore the cell to the same initial state after the production of each unit. For an m-machine robotic cell served by a dual-gripper robot, we describe a complete family of 1-unit cycles, and derive an analytical formula to estimate their total number for a given m. In the case when the gripper switching time is sufficiently small, we identify an optimal 1-unit cycle. This special case is of particular interest as it reflects the most frequently encountered situation in real-life robotic systems. Finally, we establish the connection between a dual-gripper cell and a single-gripper cell with machine output buffers of one-unit capacity and compare the cell productivity for these two models.     

Planar 3DM is NP-complete

A restriction of the three-dimensional matching problem 3DM, in which the associated bipartite graph is planar, is shown to remain NP-complete. The restriction is inspired by that of Lichtenstein's planar 3SAT (Planar formulae and their uses, SIAM J. Comput. 11 (1982), 329–343). Like Planar 3SAT, Planar 3DM is principally a tool for use in NP-completeness proofs for planar restrictions of other problems. Several examples of its applications in this respect are given.     

On the complexity of loading shallow neural networks

We formalize a notion of loading information into connectionist networks that characterizes the training of feed-forward neural networks. This problem is NP-complete, so we look for tractable subcases of the problem by placing constraints on the network architecture. The focus of these constraints is on various families of “shallow” architectures which are defined to have bounded depth and un-bounded width. We introduce a perspective on shallow networks, called the Support Cone Interaction (SCI) graph, which is helpful in distinguishing tractable from intractable subcases: When the SCI graph is a tree or is of limited bandwidth, loading can be accomplished in polynomial time; when its bandwidth is not limited we find the problem NP-complete even if the SCI graph is a simple 2-dimensional planar grid.     

Polar permutation graphs are polynomial-time recognisable

Polar graphs generalise bipartite graphs, cobipartite graphs, and split graphs, and they constitute a special type of matrix partitions. A graph is polar if its vertex set can be partitioned into two, such that one part induces a complete multipartite graph and the other part induces a disjoint union of complete graphs. Deciding whether a given arbitrary graph is polar, is an NP$\text{NP}$-complete problem. Here, we show that for permutation graphs this problem can be solved in polynomial time. The result is surprising, as related problems like achromatic number and cochromatic number are NP$\text{NP}$-complete on permutation graphs. We give a polynomial-time algorithm for recognising graphs that are both permutation and polar. Prior to our result, polarity has been resolved only for chordal graphs and cographs.     

Combinatorial flexibility problems and their computational complexity

The concept of flexibility—originated in the context of heat exchanger networks—is associated with a substructure which guarantees the performance of the original structure, in a given range of possible states. We extend this concept to combinatorial optimization problems, and prove several computational complexity results in this new framework.Under some monotonicity conditions, we prove that a combinatorial optimization problem polynomially transforms to its associated flexibility problem, but that the converse need not be true.In order to obtain polynomial flexibility problems, we have to restrict ourselves to combinatorial optimization problems on matroids. We also prove that, when relaxing in different ways the matroid structure, the flexibility problems become NP-complete. This fact is shown by proving the NP-completeness of the flexibility problems associated with the Shortest Path, Minimum Cut and Weighted Matching problems.     

Finding short cycles in planar graphs using separators

There are many known O(n) time algorithms for detecting both a C₃ or a C₄ in a planar graph. We present O(n log n) time algorithms for detecting both a C₅ or a C₆ in a planar graph. The algorithm uses a planar separator that is a small simple cycle. The problem is open for longer cycles and is known to be NP-complete for general C_k.     

Decision-theoretic troubleshooting: Hardness of approximation

Decision-theoretic troubleshooting is one of the areas to which Bayesian networks can be applied. Given a probabilistic model of a malfunctioning man-made device, the task is to construct a repair strategy with minimal expected cost. The problem has received considerable attention over the past two decades. Efficient solution algorithms have been found for simple cases, whereas other variants have been proven NP-complete. We study several variants of the problem found in literature, and prove that computing approximate troubleshooting strategies is NP-hard. In the proofs, we exploit a close connection to set-covering problems.     

The effectiveness of finite improvement algorithms for finding global optima

This paper investigates the effectiveness of using finite improvement algorithms for solving decision, search, and optimization problems. Finite improvement algorithms operate in a finite number of iterations, each taking a polynomial amount of work, where strict improvement is required from iteration to iteration. The hardware, software, and way of measuring complexity found in the polynomial setting are modified to identify the concept of repetition and define the new classes of decision problems,FI andNFI. A firstNFI-complete problem is given using the idea ofFI-transformations. Results relating these new classes toP, NP, andNP-complete are given. It is shown that if an optimization problem in a new classPGS isNP-hard, thenNP=co-NP. TwoPGS problems are given for which no polynomial algorithms are known to exist.     

Cyclic scheduling of a 2-machine robotic cell with tooling constraints

In this study, we deal with the robotic cell scheduling problem with two machines and identical parts. In an ideal FMS, CNC machines are capable of performing all the required operations as long as the required tools are stored in their tool magazines. However, this assumption may be unrealistic at times since the tool magazines have limited capacity and in many practical instances the required number of tools exceeds this capacity. In this respect, our study assumes that some operations can only be processed on the first machine while some others can only be processed on the second machine due to tooling constraints. Remaining operations can be processed on either machine. The problem is to find the allocation of the remaining operations to the machines and the optimal robot move cycle that jointly minimize the cycle time. We prove that the optimal solution is either a 1-unit or a 2-unit robot move cycle and we present the regions of optimality. Finally, a sensitivity analysis on the results is conducted.     

A polynomial algorithm for 2-cyclic robotic scheduling: A non-Euclidean case

In this paper we consider the problem of no-wait cyclic scheduling of identical parts in an m-machine production line in which a robot is responsible for moving each part from a machine to another. The aim is to find the minimum cycle time for the so-called 2-cyclic schedules, in which exactly two parts enter and two parts leave the production line during each cycle. The earlier known polynomial-time algorithms for this problem are applicable only under the additional assumption that the robot travel times satisfy the triangle inequalities. We lift this assumption on robot travel times and present a polynomial-time algorithm with the same time complexity as in the metric case, O(m⁵logm).     

On pedigree polytopes and Hamiltonian cycles

In this paper we define a combinatorial object called a pedigree, and study the corresponding polytope, called the pedigree polytope. Pedigrees are in one-to-one correspondence with the Hamiltonian cycles on K_n. Interestingly, the pedigree polytope seems to differ from the standard tour polytope, Q_n with respect to the complexity of testing whether two given vertices of the polytope are nonadjacent. A polynomial time algorithm is given for nonadjacency testing in the pedigree polytope, whereas the corresponding problem is known to be NP-complete for Q_n. We also discuss some properties of the pedigree polytope and illustrate with examples.     

Intersection graphs of curves in the plane

Let V be a set of curves in the plane. The corresponding intersection graph has V as the set of vertices, and two vertices are connected by an edge if and only if the two corresponding curves intersect in the plane.It is shown that the set of intersection graphs of curves in the plane is a proper subset of the set of all undirected graphs. Furthermore, the set of intersection graphs of straight line-segments is a proper subset of the set of the intersection graphs of curves in the plane. Finally, it is shown that for every k ≥ 3, the problem of determining whether an intersection graph of straight line-segments is k-colorable is NP-complete.     

The satisfactory partition problem

The SATISFACTORY PARTITION problem consists in deciding if a given graph has a partition of its vertex set into two nonempty parts such that each vertex has at least as many neighbors in its part as in the other part. This problem was introduced by Gerber and Kobler [Partitioning a graph to satisfy all vertices, Technical report, Swiss Federal Institute of Technology, Lausanne, 1998; Algorithmic approach to the satisfactory graph partitioning problem, European J. Oper. Res. 125 (2000) 283-291] and further studied by other authors but its complexity remained open until now. We prove in this paper that SATISFACTORY PARTITION, as well as a variant where the parts are required to be of the same cardinality, are NP-complete. However, for graphs with maximum degree at most 4 the problem is polynomially solvable. We also study generalizations and variants of this problem where a partition into k nonempty parts (k?3) is requested.     

On the problem of finding disjoint cycles and dicycles in a digraph

We study the following problem: Given a digraph D, decide if there is a cycle B in D and a cycle C in its underlying undirected graph UG(D) such that V (B)??V (C)=?. Whereas the problem is NP-complete if, as additional part of the input, a vertex x is prescribed to be contained in C, we prove that one can decide the existence of B,C in polynomial time under the (mild) additional assumption that D is strongly connected. Our methods actually find B,C in polynomial time if they exist. The behaviour of the problem as well as our solution depend on the cycle transversal number ?? (D) of D, i.e. the smallest cardinality of a set T of vertices in D such that D-T is acyclic: If ?? (D)??3 then we employ McCuaig??s framework on intercyclic digraphs to (always) find these cycles. If ?? (D) = 2 then we can characterize the digraphs for which the answer is ??yes?? by using topological methods relying on Thomassen??s theorem on 2-linkages in acyclic digraphs. For the case ?? (D)??1 we provide an algorithm independent from any earlier work.     

The path partition problem and related problems in bipartite graphs

We prove that it is NP-complete to decide whether a bipartite graph of maximum degree three on nk vertices can be partitioned into n paths of length k. Finally, we propose some approximation and inapproximation results for several related problems.