A Linear–time Tissue P System Based Solution for the 3–coloring Problem

In the literature, several examples of the efficiency of cell-like P systems regarding the solution of NP-complete problems in polynomial time can be found (obviously, trading space for time). Recently, different new models of tissue-like P systems have received important attention from the scientific community. In this paper we present a linear-time solution to an NP-complete problem from graph theory, the 3-coloring problem, and we discuss the suitability of tissue-like P systems as a framework to address the efficient solution to intractable problems.     

Serial and Parallel Algorithms for (k,2)-Partite Graphs

We introduce a class of layered graphs which we call (k,2)-partite and which we argue are an interesting class because of several important applications. We show that testing for (k,2)-partiteness can be done efficiently both on sequential and parallel machines, by showing that membership is in NSPACE(log n) and in NC². We show that (k,2)-partite graphs have bounded path width. We then show that a particular NP-complete problem, namely Maximum Independent Set, is solvable in linear time on bounded pathwidth graphs if the path decomposition is included in the input. Finally, we show that the Maximum Independent Set problem is in NC² for (k,2)-partite graphs. We note that linear time solutions for certain NP-complete problems have been shown for a wider class of graphs, namely partial k-trees. Our linear time algorithm is somewhat simpler in structure. We conjecture that our techniques can be used on many NP-complete problems to yield efficient algorithms for (k,2)-partite graphs.     

Some simplified NP-complete graph problems

It is widely believed that showing a problem to be NP-complete is tantamount to proving its computational intractability. In this paper we show that a number of NP-complete problems remain NP-complete even when their domains are substantially restricted. First we show the completeness of Simple Max Cut (Max Cut with edge weights restricted to value 1), and, as a corollary, the completeness of the Optimal Linear Arrangement problem. We then show that even if the domains of the Node Cover and Directed Hamiltonian Path problems are restricted to planar graphs, the two problems remain NP-complete, and that these and other graph problems remain NP-complete even when their domains are restricted to graphs with low node degrees. For Graph 3-Colorability, Node Cover, and Undirected Hamiltonian Circuit, we determine essentially the lowest possible upper bounds on node degree for which the problems remain NP-complete.     

On the Complexity of Matroid Isomorphism Problem

We study the complexity of testing if two given matroids are isomorphic. The problem is easily seen to be in S₂^p\Sigma_{2}^{p}. In the case of linear matroids, which are represented over polynomially growing fields, we note that the problem is unlikely to be S₂^p\Sigma_{2}^{p}-complete and is co NP-hard. We show that when the rank of the matroid is bounded by a constant, linear matroid isomorphism, and matroid isomorphism are both polynomial time many-one equivalent to graph isomorphism.     

Detecting Fixed Patterns in Chordal Graphs in Polynomial Time

The Contractibility problem takes as input two graphs G and H, and the task is to decide whether H can be obtained from G by a sequence of edge contractions. The Induced Minor and Induced Topological Minor problems are similar, but the first allows both edge contractions and vertex deletions, whereas the latter allows only vertex deletions and vertex dissolutions. All three problems are NP-complete, even for certain fixed graphs H. We show that these problems can be solved in polynomial time for every fixed H when the input graph G is chordal. Our results can be considered tight, since these problems are known to be W[1]-hard on chordal graphs when parameterized by the size of H. To solve Contractibility and Induced Minor, we define and use a generalization of the classic Disjoint Paths problem, where we require the vertices of each of the k paths to be chosen from a specified set. We prove that this variant is NP-complete even when k=2, but that it is polynomial-time solvable on chordal graphs for every fixed k. Our algorithm for Induced Topological Minor is based on another generalization of Disjoint Paths called Induced Disjoint Paths, where the vertices from different paths may no longer be adjacent. We show that this problem, which is known to be NP-complete when k=2, can be solved in polynomial time on chordal graphs even when k is part of the input. Our results fit into the general framework of graph containment problems, where the aim is to decide whether a graph can be modified into another graph by a sequence of specified graph operations. Allowing combinations of the four well-known operations edge deletion, edge contraction, vertex deletion, and vertex dissolution results in the following ten containment relations: (induced) minor, (induced) topological minor, (induced) subgraph, (induced) spanning subgraph, dissolution, and contraction. Our results, combined with existing results, settle the complexity of each of the ten corresponding containment problems on chordal graphs.     

The k-in-a-Path Problem for Claw-free Graphs

The k-in-a-Path problem is to test whether a graph contains an induced path spanning k given vertices. This problem is NP-complete in general graphs, already when k=3. We show how to solve it in polynomial time on claw-free graphs, when k is an arbitrary fixed integer not part of the input. As a consequence, also the k-Induced Disjoint Paths and the k-in-a-Cycle problem are solvable in polynomial time on claw-free graphs for any fixed k. The first problem has as input a graph G and k pairs of specified vertices (s _i ,t _i ) for i=1,…,k and is to test whether G contain k mutually induced paths P _i such that P _i connects s _i and t _i for i=1,…,k. The second problem is to test whether a graph contains an induced cycle spanning k given vertices. When k is part of the input, we show that all three problems are NP-complete, even for the class of line graphs, which form a subclass of the class of claw-free graphs.     

Minimum cost flows with minimum quantities

We consider a variant of the well-known minimum cost flow problem where the flow on each arc in the network is restricted to be either zero or above a given lower bound. The problem was recently shown to be weakly NP-complete even on series-parallel graphs. We start by showing that the problem is strongly NP-complete and cannot be approximated in polynomial time (unless P=NP) up to any polynomially computable function even when the graph is bipartite and the given instance is guaranteed to admit a feasible solution. Moreover, we present a pseudo-polynomial-time exact algorithm and a fully polynomial-time approximation scheme (FPTAS) for the problem on series-parallel graphs.     

On the k-path cover problem for cacti

In this paper we investigate the k-path cover problem for graphs, which is to find the minimum number of vertex disjoint k-paths that cover all the vertices of a graph. The k-path cover problem for general graphs is NP-complete. Though notable applications of this problem to database design, network, VLSI design, ring protocols, and code optimization, efficient algorithms are known for only few special classes of graphs. In order to solve this problem for cacti, i.e., graphs where no edge lies on more than one cycle, we introduce the so-called Steiner version of the k-path cover problem, and develop an efficient algorithm for the Steiner k-path cover problem for cacti, which finds an optimal k-path cover for a given cactus in polynomial time.     

Monte Carlo circuits for the abelian permutation group intersection problem

Summary We show that the problem of computing a basis for an abelian transitive permutation group is in N C ^k and also we show that the problem of computing a basis for an abelian permutation group and the problem of computing the intersection of two abelian groups acting on n points, can be solved in depth (log n)^k on a Monte Carlo Boolean circuit of polynomial size. Moreover the latter two problems are shown to be in N C ^k in the restricted case of bounded number of generators.     

An oracle builder’s toolkit

We show how to use various notions of genericity as tools in oracle creation. In particular,

1. we give an abstract definition of genericity that encompasses a large collection of different generic notions;

2. we consider a new complexity class AWPP, which contains BQP (quantum polynomial time), and infer several strong collapses relative to -generics;

3. we show that under additional assumptions these collapses also occur relative to Cohen generics;

4. we show that relative to -generics, ULIN∩co-ULINDTIME(n^k) for any k, where ULIN is unambiguous linear time, despite the fact that UP(NP∩co-NP)P relative to these generics;

5. we show that there is an oracle relative to which NP/1∩co-NP/1(NP∩co-NP)/poly; and

6. we use a specialized notion of genericity to create an oracle relative to which

NP^BPPMA.

The complexity of comparability graph recognition and coloring

Using the notion ofG-decomposition introduced in Golumbic [8, 9], we present an implementation of an algorithm which assigns a transitive orientation to a comparability graph inO(δ·|E|) time andO(|E|) space where δ is the maximum degree of a vertex and |E| is the number of edges. A quotient operation reducing the graph in question and preservingG-decomposition and transitive orientability is shown, and efficient solutions to a number ofNP-complete problems which reduce to polynomial time for comparability graphs are discussed.     

The complexity of constraint satisfaction problems for small relation algebras

Andréka and Maddux [Notre Dame J. Formal Logic 35 (4) 1994] classified the small relation algebras—those with at most 8 elements, or in other terms, at most 3 atomic relations. They showed that there are eighteen isomorphism types of small relation algebras, all representable. For each simple, small relation algebra they computed the spectrum of the algebra, namely the set of cardinalities of square representations of that relation algebra.In this paper we analyze the computational complexity of the problem of deciding the satisfiability of a finite set of constraints built on any small relation algebra. We give a complete classification of the complexities of the general constraint satisfaction problem for small relation algebras. For three of the small relation algebras the constraint satisfaction problem is NP-complete, for the other fifteen small relation algebras the constraint satisfaction problem has cubic (or lower) complexity.We also classify the complexity of the constraint satisfaction problem over fixed finite representations of any relation algebra. If the representation has size two or less then the complexity is cubic (or lower), but if the representation is square, finite and bigger than two then the complexity is NP-complete.     

Two-stage hybrid flow shop scheduling with dynamic job arrivals

Motivated by applications in semiconductor manufacturing industry, we consider a two-stage hybrid flow shop where a discrete machine is followed by a batching machine. In this paper, we analyze the computational complexity of a class of two-machine problems with dynamic job arrivals. For the problems belonging to P we present polynomial algorithms. For the NP-complete problems we propose the heuristics, and then establish the upper bounds on the worst case performance ratios of the heuristics. In addition, we give the improved heuristics that can achieve better performances.     

Unbalanced Graph Partitioning

We investigate the unbalanced cut problems. A cut (A,B) is called unbalanced if the size of its smaller side is at most k (called k-size) or exactly k (called Ek-size), where k is an input parameter. We consider two closely related unbalanced cut problems, in which the quality of a cut is measured with respect to the sparsity and the conductance, respectively. We show that even if the input graph is restricted to be a tree, the Ek-Sparsest Cut problem (to find an Ek-size cut with the minimum sparsity) is still NP-hard. We give a bicriteria approximation algorithm for the k-Sparsest Cut problem (to find a k-size cut with the minimum sparsity), which outputs a cut whose sparsity is at most O(logn) times the optimum and whose smaller side has size at most O(logn)k. As a consequence, this leads to a (O(logn),O(logn))-bicriteria approximation algorithm for the Min k-Conductance problem (to find a k-size cut with the minimum conductance).     

The Complexity of Read-Once Resolution

We investigate the complexity of deciding whether a propositional formula has a read-once resolution proof. We give a new and general proof of Iwama–Miynano's theorem which states that the problem whether a formula has a read-once resolution proof is NP-complete. Moreover, we show for fixed k2 that the additional restriction that in each resolution step one of the parent clauses is a k-clause preserves the NP-completeness. If we demand that the formulas are minimal unsatisfiable and read-once refutable then the problem remains NP-complete. For the subclasses MU(k) of minimal unsatisfiable formulas we present a pol-time algorithm deciding whether a MU(k)-formula has a read-once resolution proof. Furthermore, we show that the problems whether a formula contains a MU(k)-subformula or a read-once refutable MU(k)-subformula are NP-complete.     

Small Vertex Cover makes Petri Net Coverability and Boundedness Easier

The coverability and boundedness problems for Petri nets are known to be Expspace-complete. Given a Petri net, we associate a graph with it. With the vertex cover number k of this graph and the maximum arc weight W as parameters, we show that coverability and boundedness are in ParaPspace. This means that these problems can be solved in space $\mathcal{O} ({\mathit{ef}}(k, W){\mathit{poly}}(n) )$ , where ef(k,W) is some super-polynomial function and poly(n) is some polynomial in the size of the input n. We then extend the ParaPspace result to model checking a logic that can express some generalizations of coverability and boundedness.     

Some observations on NP real numbers and P-selective sets

We show that each standard left cut of a real number is a p-selective set. Classification results about NP real numbers and recursively enumerable real numbers follow from similar results about p-selective and semirecursive sets. In particular, it is proved that no left cut can be NP-hard unless the polynomial hierarchy collapses to ?₂^P. This result is surprising because it shows that the McLaughlin-Martin construction of a ?_tt-complete r.e. semirecursive set fails at the polynomial time complexity level.     

Packet Routing and PRAM Emulation on Star Graphs and Leveled Networks

We consider the problem of permutation routing on a star graph, an interconnection network which has better properties than the hypercube. In particular, its degree and diameter are sublogarithmic in the network size. We present optimal randomized routing algorithms that run in O(D) steps (where D is the network diameter) for the worst-case input with high probability. We also show that for the n-way shuffle network with N = nⁿ nodes, there exists a randomized routing algorithm which runs in O(n) time with high probability. Another contribution of this paper is a universal randomized routing algorithm that could do optimal routing for a large class of networks (called leveled networks) which includes the star graph. The associative analysis is also network-independent. In addition, we present a deterministic routing algorithm, for the star graph, which is near optimal. All the algorithms we give are oblivious. As an application of our routing algorithms, we also show how to emulate a PRAM optimally on this class of networks.     

Generic case completeness

In this note we introduce a notion of a generically (strongly generically) NP-complete problem and show that the randomized bounded version of the halting problem is strongly generically NP-complete.