On the efficiency of maximum-flow algorithms on networks with small integer capacities

The performance of maximum-flow algoirthms that work in phases is studied as a function of the maximum arc capacity,C, of the network and a quantity we call thetotal potential, P, of the network, which is related to the average amount of flow that can be sent through a node. Extending results by Even and Tarjan, we derive a tightO(min{C ^1/3¦V¦^2/3,P ^1/2, ¦V¦}) upper bound on the number of phases. AnO(min{P log¦V¦,C¦V¦^3/2, ¦V¦²¦E¦}) upper bound is derived on the total length of the augmenting paths used by Dinic's algorithm. The latter quantity is useful in estimating the performance of Dinic's method on certain inputs. Our results show that on a natural class of networks, the performance of Dinic's algorithm is significantly better than would be apparent from a bound based on ¦V¦ and ¦E¦ alone. We present an application of our bounds to the maximum subgraph density problem.     

The lexicographically first maximal subgraph problems:P-completeness andNC algorithms

The lexicographically first maximal (lfm) subgraph problem for a property is to compute the lfm vertex set whose induced subgraph satisfies . The main contribution of this paper is theP-completeness of the lfm subgraph problem for any nontrivial hereditary property. We also observe that most of the lfm subgraph problems are stillP-complete even if the instances are restricted to graphs with degree 3. However, some exceptions are found. For example, it is shown that the lfm 4-cycle free subgraph problem is inNC ² for graphs with degree 3 but turns out to beP-complete for graphs with degree 4. Further, we analyze the complexity of the lfmedge-induced subgraph problem for some graph properties and show that it has a different complexity feature.This work was done while the author visited Universität-GH-Paderborn and a part of this paper was presented at the 14th ICALP, Karlsruhe, 1987.     

Parameterized complexity of the induced subgraph problem in directed graphs

In this Letter, we consider the parameterized complexity of the following problem: Given a hereditary property P on digraphs, an input digraph D and a positive integer k, does D have an induced subdigraph on k vertices with property P? We completely characterize hereditary properties for which this induced subgraph problem is W[1]-complete for two classes of directed graphs: general directed graphs and oriented graphs. We also characterize those properties for which the induced subgraph problem is W[1]-complete for general directed graphs but fixed parameter tractable for oriented graphs. These results are among the very few parameterized complexity results on directed graphs.     

A fast algorithm for computing sparse visibility graphs

AnO(¦E¦log² n) algorithm is presented to construct the visibility graph for a collection ofn nonintersecting line segments, where ¦E¦ is the number of edges in the visibility graph. This algorithm is much faster than theO(n ²)-time andO(n ²)-space algorithms by Asanoet al., and by Welzl, on sparse visibility graphs. Thus we partially resolve an open problem raised by Welzl. Further, our algorithm uses onlyO(n) working storage.     

Tree-Based Parallel Algorithm Design

In this paper a systematic method for the design of efficient parallel algorithms for the dynamic evaluation of computation trees and/or expressions is presented. This method involves the use of uniform closure properties of certain classes of unary functions. Using this method, optimal parallel algorithms are given for many computation tree problems which are important in parallel algebraic and numerical computation, and parallel code generation on exclusive read and exclusive write parallel random access machines. Our algorithmic result is complemented by a P-complete tree problem. Received February 13, 1995; revised March 25, 1996.     

Solution methods and computational investigations for the Linear Bottleneck Assignment Problem

The Linear Bottleneck Assignment ProblemLBAP is analyzed from a computational point of view. Beside a brief review of known algorithms new methods are developed using only sparse subgraphs for their computation. The practical behaviour of both types of algorithms is investigated. The most promising algorithm consists of computing a maximum cardinality matching with all edge costs smaller than a previously determined bound and augmenting this matching to an assignment. The methods on sparse subgraphs are useful in the case of memory restrictions and are superior if the subgraph selection can be improved by some previously generated structure. Other treated questions are how to select a suitable subgraph for the new methods, how to deal with non regular data and what connections to asymptotic results for theLBAP can be detected. Supported by the SFB F003 ‘Optimierung und Kontrolle’, Bereich Diskrete Optimierung.     

Flit-serial packet routing on meshes and tori

In this paper we consider theflit-serial packet-routing problem, where each packet consists of a sequence ofk flits and is, thus, called asnake. Based on the properties of the snake during the routing, we give a formal definition of three different packet-routing models, namely, thestore-and-forward model, thecut-through model, and thecut-through with partial cuts model. Surprisingly, all previous work has focused on the store-and-forward model. We also introduce therestricted cut-through model, which is unrealistic, but is proved to be a very powerful tool in the effort to bound the time required by a routing problem. We study the cut-through with partial cuts model which is most commonly used in practice. We present the first algorithms, deterministic and probabilistic, based on this model for the permutation routing problem on a chain, on a square mesh, and on a square torus.     

Scalable Parallel Algorithms for Geometric Pattern Recognition

This paper considers a variety of geometric pattern recognition problems on input sets of size n using a coarse grained multicomputer model consisting of p processors with Ω(n/p) local memory each (i.e., Ω(n/p) memory cells of Θ(log n) bits apiece), where the processors are connected to an arbitrary interconnection network. It introduces efficient scalable parallel algorithms for a number of geometric problems including the rectangle finding problem, the maximal equally spaced collinear points problem, and the point set pattern matching problem. All of the algorithms presented are scalable in that they are applicable and efficient over a very wide range of ratios of problem size to number of processors. In addition to the practicality imparted by scalability, these algorithms are easy to implement in that all required communications can be achieved by a small number of calls to standard global routing operations.     

A sublinear algorithm for approximate keyword searching

Given a relatively short query stringW of lengthP, a long subject stringA of lengthN, and a thresholdD, theapproximate keyword search problem is to find all substrings ofA that align withW with not more than D insertions, deletions, and mismatches. In typical applications, such as searching a DNA sequence database, the size of the databaseA is much larger than that of the queryW, e.g.,N is on the order of millions or billions andP is a hundred to a thousand. In this paper we present an algorithm that given a precomputedindex of the databaseA, finds rare matches in time that issublinear inN, i.e.,N ^c for somec<1. The sequenceA must be overa. finite alphabet . More precisely, our algorithm requires 0(DN ^pow() logN) expected-time where =D/P is the maximum number of differences as a percentage of query length, and pow() is an increasing and concave function that is 0 when =0. Thus the algorithm is superior to current O(DN) algorithms when is small enough to guarantee that pow() < 1. As seen in the paper, this is true for a wide range of , e.g., . up to 33% for DNA sequences (¦¦=4) and 56% for proteins sequences (¦¦=20). In preliminary practical experiments, the approach gives a 50-to 500-fold improvement over previous algorithms for prolems of interest in molecular biology.This work was supported in part by the National Institutes of Health under Grant R01 LM04960-01 and the Aspen Center for Physics.     

Adaptive parallel algorithms for integral knapsack problems

In this paper, the design of a time-efficient and processor-efficient parallel algorithm for the integral knapsack problem is considered. A parallel integral knapsack algorithm is presented, which is adaptive to all parameters, especially to the maximum size of items. The parallel complexity of another important packing problem, the integral exactly-packing problem, is also considered. An optimal O(log n log m) time, parallel integral exactly-packing algorithm is given. Since the partition problem has a constant time, constant processor reduction to the exactly-packing problem, our parallel integral exactly-packing algorithm can be used for job scheduling, task partition, and many other important practical problems. Moreover, the methods and techniques used in this paper can be used for developing processor-efficient and time-efficient parallel algorithms for many other problems. Using the new parallel integral knapsack algorithm, the previously known parallel approximation schemes for the 0–1 knapsack problem and the binpacking problem, by E. W. Mayr and P. S. Gopalkrishnan, are improved upon significantly.     

A series of approximation algorithms for the acyclic directed steiner tree problem

Given an acyclic directed network, a subsetS of nodes (terminals), and a rootr, theacyclic directed Steiner tree problem requires a minimum-cost subnetwork which contains paths fromr to each terminal. It is known that unlessNP⊆DTIME[n ^polylogn ] no polynomial-time algorithm can guarantee better than (lnk)/4-approximation, wherek is the number of terminals. In this paper we give anO(k ^ε)-approximation algorithm for any ε>0. This result improves the previously knownk-approximation. This research was supported in part by Volkswagen-Stiftung and Packard Foundation.     

Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree

The vertex updating problem for a minimum spanning tree (MST) is defined as follows: Given a graphG=(V, E _G) and an MSTT forG, find a new MST forG to which a new vertexz has been added along with weighted edges that connectz with the vertices ofG. We present a set of rules that produce simple optimal parallel algorithms that run inO(lgn) time usingn/lgn EREW PRAM processors, wheren=¦V¦. These algorithms employ any valid tree-contraction schedule that can be produced within the stated resource bounds. These rules can also be used to derive simple linear-time sequential algorithms for the same problem. The previously best-known parallel result was a rather complicated algorithm that usedn processors in the more powerful CREW PRAM model. Furthermore, we show how our solution can be used to solve the multiple vertex updating problem: Update a given MST whenk new vertices are introduced simultaneously. This problem is solved inO(lgk·lgn) parallel time using (k·n)/(lgk·lgn) EREW PRAM processors. This is optimal for graphs having (kn) edges.Part of this work was done while P. Metaxas was with the Department of Mathematics and Computer Science, Dartmouth College.     

A Computational Study of a Cutting Plane Algorithm for University Course Timetabling

In this paper, we describe a case-study where a Branch-and-Cut algorithm yields the “optimal” solution of a real-world timetabling problem of University courses (University Course Timetabling problem). The problem is formulated as a Set Packing problem with side constraints. To tighten the initial formulation, we utilize well-known valid inequalities of the Set Packing polytope, namely Clique and Lifted Odd-Hole inequalities. We also analyze the combinatorial properties of the problem to introduce new families of cutting planes that are not valid for the Set Packing polytope, and their separation algorithms. These cutting planes turned out to be very effective to yield the optimal solution of a set of real-world instances with up to 69 courses, 59 teachers, and 15 rooms.     

Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems

Summary A bipartite graph G=(A, B, E) is convex on the vertex set A if A can be ordered so that for each element b in the vertex set B the elements of A connected to b form an interval of A; G is doubly convex if it is convex on both A and B. Letting ¦A¦=m and ¦B¦=n, in this paper we describe maximum matching algorithms which run in time O(m + nA(n)) on convex graphs (where A(n) is a very slowly growing function related to a functional inverse of Ackermann's function), and in time O(m+n) on doubly convex graphs. We also show that, given a maximum matching in a convex bipartite graph G, a corresponding maximum set of independent vertices can be found in time O(m+n). Finally, we briefly discuss some generalizations of convex bipartite graphs and some extensions of the previously discussed techniques to instances in scheduling theory.On leave from the Institute of Computer Science, Polish Academy of Sciences, P.O. Box 22, 00-901 Warsaw PKiN, PolandAlso with the Departments of Electrical Engineering and of Computer Science     

Inverse NP Problems

The inverse problem relative to a verifier V of proofs of membership for a NP language is the problem of deciding, given a set π of proofs, whether or not there exists a string x having exactly π as its set of proofs. In this paper, we study the complexity of inverse problems. We develop a new notion of reduction which allows one to compare the complexity of inverse problems. Using this notion, we classify as coNP-complete the inverse problems for the “natural” verifiers of many NP-complete problems. We also show that the inverse complexity of a verifier for a language L cannot be predicted solely from the complexity of L, but rather, is highly dependent upon the choice of verifier used to accept L. In this context, a verifier with a Σ₂ ^p -complete inverse problem is exhibited, giving a new and natural example of a Σ₂ ^p -complete problem.      

Three ∑ P 2 -complete problems in computational learning theory

The consistency problem associated with a concept classC is to determine, given two setsA andB of examples, whether there exists a conceptc inC such that eachx inA is a positive example ofc and eachy inB is a negative example ofc. We explore in this paper the following intuition: for a concept classC, if the membership problem of determining whether a given example is positive for a concept isNP-complete, then the corresponding consistency problem is likely to be _P ² -complete. To support this intuition, we prove that the following three consistency problems for concept classes of patterns, graphs and generalized Boolean formulas, whose membership problems are known to beNP-complete, are _P ² -complete: (a) given two setsA andB of strings, determine whether there exists a patternp such that every string inA is in the languageL(p) and every string inB is not in the languageL(p); (b) given two setsA andB of graphs, determine whether there exists a graphG such that every graph inA is isomorphic to a subgraph ofG and every graph inB is not isomorphic to any subgraph ofG; and (c) given two setsA andB of Boolean formulas, determine whether there exists a 3-CNF Boolean formula such that for every A, is satisfiable and for every B, is not satisfiable. These results suggest that consistendy problems in machine learning are natural candidates for _P ² -complete problems if the corresponding membership problems are known to beNP-complete.In addition, we prove that the corresponding prediction problems for concept classes of polynomial-time nondeterministic Turing machines, nondeterministic Boolean circuits, generalized Boolean formulas, patterns and graphs are prediction-complete for the classR _NP of all concept classes whose membership problems are inNP.     

Parallel Algorithms for Maximal Acyclic Sets

Given a graph G=(V,E), the well-known spanning forest problem of G can be viewed as the problem of finding a maximal subset F of edges in G such that the subgraph induced by F is acyclic. Although this problem has well-known efficient NC algorithms, its vertex counterpart, the problem of finding a maximal subset U of vertices in G such that the subgraph induced by U is acyclic, has not been shown to be in NC (or even in RNC) and is not believed to be parallelizable in general. In this paper we present NC algorithms for solving the latter problem for two special cases. First, we show that, for a planar graph with n vertices, the problem can be solved in time with O(n) processors on an EREW PRAM. Second, we show that the problem is solvable in NC if the input graph G has only vertex-induced paths of length polylogarithmic in the number of vertices of G. As a consequence of this result, we show that certain natural extensions of the well-studied maximal independent set problem remain solvable in NC. Moreover, we show that, for a constant-degree graph with n vertices, the problem can be solved in time with O(n ² ) processors on an EREW PRAM. Received July 3, 1995; revised April 1, 1996.     

A linear-time algorithm for finding a sparsek-connected spanning subgraph of ak-connected graph

We show that anyk-connected graphG = (V, E) has a sparsek-connected spanning subgraphG = (V, E) with ¦E¦ =O(k¦V¦) by presenting anO(¦E¦)-time algorithm to find one such subgraph, where connectivity stands for either edge-connectivity or node-connectivity. By using this algorithm as preprocessing, the time complexities of some graph problems related to connectivity can be improved. For example, the current best time boundO(max{k ²¦V¦^1/2,k¦V¦}¦E¦) to determine whether node-connectivityK(G) of a graphG = (V, E) is larger than a given integerk or not can be reduced toO(max{k ³¦V¦^3/2,k ²¦V¦²}).The first author was partially supported by the Grant-in-Aid for Encouragement of Young Scientists of the Ministry of Education, Science and Culture of Japan and by the subvention to young scientists by the Research Foundation of Electrotechnology of Chubu.     

多编码树GPU并行轴心子图匹配

子图同构问题是非确定多项式(NP)完全问题,而轴心子图同构是一种特殊的子图同构问题.针对现在已经有许多高效的子图同构算法,然而对于轴心子图同构问题目前并没有基于GPU的搜索算法,且通过改造已有的子图同构算法来解决轴心子图匹配问题会产生大量不必要的中间结果这一问题,提出了一种基于GPU的轴心子图同构算法.首先,通过一种新...