Minimum ε-equivalent Circuit Size Problem

For a Boolean function f given by its truth table (of length ) and a parameter s the problem considered is whether there is a Boolean function g -equivalent to f, i.e., , and computed by a circuit of size at most s. In this paper we investigate the complexity of this problem and show that for specific values of it is unlikely to be in P/poly. Under the same assumptions we also consider the optimization variant of the problem and prove its inapproximability.     

Construction of the nearest neighbor embracing graph of a point set

This paper gives optimal algorithms for the construction of the Nearest Neighbor Embracing Graph (NNE-graph) of a given point set V of size n in the k-dimensional space (k-D) for k = 2,3. The NNE-graph provides another way of connecting points in a communication network, which has lower expected degree at each point and shorter total length of connections with respect to those using Delaunay triangulation. In fact, the NNE-graph can also be used as a tool to test whether a point set is randomly generated or has some particular properties. We show that in 2-D the NNE-graph can be constructed in optimal time in the worst case. We also present an time algorithm, where d is the -th largest degree in the utput NNE-graph. The algorithm is optimal when . The algorithm is also sensitive to the structure of the NNE-graph, for instance when , the number of edges in NNE-graph is bounded by for any value g with . We finally propose an time algorithm for the problem in 3-D, where d and are the -th largest vertex degree and the largest vertex degree in the NNE-graph, respectively. The algorithm is optimal when the largest vertex degree of the NNE-graph is .     

On zero error algorithms having oracle access to one query

It is known that (Cai, 2001). The reverse direction of whether ZPP^NP is contained in remains open. We show that if the zero-error algorithm is allowed to ask only one query to the NP oracle (for any input and random string), then it can be simulated in . That is, we prove that . Next we consider whether the above result can be improved as and point out a difficulty in doing so. Via a simple proof, we observe that BPP ⊆ ZPP^NP[1] (a result implicitly proven in some prior work). Thus, achieving the above improvement would imply BPP ⊆ P^NP, settling a long standing open problem. We then argue that the above mentioned improvement can be obtained for the next level of the polynomial time hierarchy. Namely, we prove that . On the other hand, by adapting our proof of our main result it can be shown that . For the purpose of comparing these two results, we prove that . We conclude by observing that the above claims extend to the higher levels of the hierarchy: for k ≥ 2, and . Research supported in part by NSF grant CCR-0208013. A preliminary version of the paper was presented at COCOON′05 Cai and Chakaravarthy (2005). Part of the research was conducted while the author was at the University of Wisconsin, Madison.     

Finding a Noncrossing Steiner Forest in Plane Graphs Under a 2-Face Condition

Let G = (V,E) be a plane graph with nonnegative edge weights, and let be a family of k vertex sets , called nets. Then a noncrossing Steiner forest for in G is a set of k trees in G such that each tree connects all vertices, called terminals, in net N _i, any two trees in do not cross each other, and the sum of edge weights of all trees is minimum. In this paper we give an algorithm to find a noncrossing Steiner forest in a plane graph G for the case where all terminals in nets lie on any two of the face boundaries of G. The algorithm takes time if G has n vertices and each net contains a bounded number of terminals.     

On the Hardness of Approximating the Min-Hack Problem

We show several hardness results for the Minimum Hacking problem, which roughly can be described as the problem of finding the best way to compromise a target node given a few initial compromised nodes in a network. We give several reductions to show that Minimum Hacking is not approximable to within where δ = 1− ^c n, for any c < 1/2. We also analyze some heuristics on this problem.     

Center and Distinguisher for Strings with Unbounded Alphabet

Consider two sets and of strings of length L with characters from an unbounded alphabet , i.e., the size of is not bounded by a constant and has to be taken into consideration as a parameter for input size. A closest string s* of is a string that minimizes the maximum of Hamming¹ distance(s, s*) over all string s : s . In contrast, a farthest string t* from maximizes the minimum of Hamming distance(t*,t) over all elements t: t . A distinguisher of from is a string that is close to every string in and far away from any string in . We obtain polynomial time approximation schemes to settle the above problems.     

An Improved Randomized Approximation Algorithm for Max TSP

We present an O(n³)-time randomized approximation algorithm for the maximum traveling salesman problem whose expected approximation ratio is asymptotically , where n is the number of vertices in the input (undirected) graph. This improves the previous best.Part of work done while visiting City University of Hong Kong.     

Augmenting a Submodular and Posi-modular Set Function by a Multigraph

Given a finite set V and a set function , we consider the problem of constructing an undirected multigraph G = (V,E) such that the cut function together has value at least 2 for all non-empty and proper subsets of V. If f is intersecting submodular and posi-modular, and satisfies the tripartite inequality, then we show that such a multigraph G with the minimum number of edges can be found in time, where is the time to compute the value of f(X) for a subset .     

Finding disjoint paths with related path costs

We consider routing in survivable networks that provide protection against node or link failures. In these networks resilience against failures is provided by routing connections on pairs of disjoint paths called primary and backup paths. The primary path of a connection carries its traffic under normal circumstances and in the eventuality of a network failure effecting the primary path the connection traffic (all or some portion of it) is rerouted over its backup path. In an online setting as connection requests arrive a pair of disjoint primary and backup paths of least total cost (under some link cost metric) are selected to route the connections. In many situations the cost metric used for the primary path differs from the cost metric used for the backup path. Also in many realistic settings these two cost metrics are related to each other. In this paper we study the problem of finding a pair of edge or node disjoint paths of least total cost where the cost of the primary path is the total cost of its links while the cost for the backup path is α times the sum of the cost of its links, for some given α < 1. We show that the problem is hard to approximate to within a factor for any positive . In addition we show that the problem is complete for a set of hard to approximate problems. On the positive side we show that a simple algorithm achieves an approximation ratio of for the problem.     

Simple Approximation Algorithms for MAXNAESP and Hypergraph 2-colorability

Hypergraph 2-colorability, also known as set splitting, is a widely studied problem in graph theory. In this paper we study the maximization version of the same. We recast the problem as a special type of satisfiability problem and give approximation algorithms for it. Our results are valid for hypergraph 2-colorability, set splitting and MAX-CUT (which is a special case of hypergraph 2-colorability) because the reductions are approximation preserving. Here we study the MAXNAESP problem, the optimal solution to which is a truth assignment of the literals that maximizes the number of clauses satisfied. As a main result of the paper, we show that any locally optimal solution (a solution is locally optimal if its value cannot be increased by complementing assignments to literals and pairs of literals) is guaranteed a performance ratio of . This is an improvement over the ratio of attributed to another local improvement heuristic for MAX-CUT (C. Papadimitriou, Computational Complexity, Addison Wesley, 1994). In fact we provide a bound of for this problem, where k 3 is the minimum number of literals in a clause. Such locally optimal algorithms appear to subsume typical greedy algorithms that have been suggested for problems in the general domain of satisfiability. It should be noted that the NAESP problem where each clause has exactly two literals, is equivalent to MAX-CUT. However, obtaining good approximation ratios using semi-definite programming techniques (M. Goemans and D.P. Williamson, in Proceedings of the 26th Annual ACM Symposium on Theory of Computing, 1994a, pp. 422–431) appears difficult. Also, the randomized rounding algorithm as well as the simple randomized algorithm both (M. Goemans and D.P. Williamson, SIAM J. Disc. Math, vol. 7, pp. 656–666, 1994b) yield a bound of for the MAXNAESP problem. In contrast to this, the algorithm proposed in this paper obtains a bound of for this problem.     

Requiring Connectivity in the Set Covering Problem

Given a bipartite graph with bipartition V and W, a cover is a subset C V such that each node of W is adjacent to at least one node in C. The set covering problem seeks a minimum cardinality cover. Set covering has many practical applications. In the context of reserve selection for conservation of species, V is a set of candidate sites from a reserve network, W is the set of species to be protected, and the edges describe which species are represented in each site. Some covers however may assume spatial configurations which are not adequate for conservational purposes. Indeed, for sustainability reasons the fragmentation of existing natural habitats should be avoided, since this is recognized as being disruptive to the species adapted to the habitats. Thus, connectivity appears to be an important issue for protection of biological diversity. We therefore consider along with the bipartite graph, a graph G with node set V, describing the adjacencies of the elements of V, and we look for those covers C V for which the subgraph of G induced by C is connected. We call such covers connected covers. In this paper we introduce and study some valid inequalities for the convex hull of the set of incidence vectors of connected covers.MSC2000: 90C10, 90C57This authors research was financially supported by the Portuguese Foundation for Science and Technology (FCT).This paper is part of this authors Ph.D. research.     

Efficient algorithms for shared backup allocation in networks with partial information

We study efficient algorithms for establishing reliable connections with bandwidth guarantees in communication networks. In the normal mode of operation, each connection uses a primary path to deliver packets from the source to the destination. To ensure continuous operation in the event of an edge failure, each connection uses a set of backup bridges, each bridge protecting a portion of the primary path. To meet the bandwidth requirement of the connection, a certain amount of bandwidth must be allocated the edges of the primary path, as well as on the backup edges. In this paper, we focus on minimizing the amount of required backup allocation by sharing backup bandwidth among different connections. We consider efficient sharing schemes that require only partial information about the current state of the network. Specifically, the only information available for each edge is the total amount of primary allocation and the cost of allocating backup bandwidth on this edge. We consider the problem of finding a minimum cost backup allocation together with a set of bridges for a given primary path. We prove that this problem is NP-hard and present an approximation algorithm whose performance is within of the optimum, where n is the number of edges in the primary path. We also consider the problem of finding both a primary path and backup allocation of minimal total cost. A preliminary version of this paper appears in the Proceedings of 13th Annual European Symposium on Algorithms - ESA 2005, Mallorca, Spain. J. (Seffi) Naor: This research is supported in part by a foundational and strategical research grant from the Israeli Ministry of Science, and by a US-Israel BSF Grant 2002276.     

Approximation hardness of edge dominating set problems

We provide the first interesting explicit lower bounds on efficient approximability for two closely related optimization problems in graphs, MINIMUM EDGE DOMINATING SET and MINIMUM MAXIMAL MATCHING. We show that it is NP-hard to approximate the solution of both problems to within any constant factor smaller than . The result extends with negligible loss to bounded degree graphs and to everywhere dense graphs. An extended abstract of this paper was accepted at the 14th Annual International Symposium on Algorithms and Computation, ISAAC 2003.     

A {{10}}-Approximation Algorithm for a Generalization of the Weighted Edge-Dominating Set Problem

We study the approximability of the weighted edge-dominating set problem. Although even the unweighted case is NP-Complete, in this case a solution of size at most twice the minimum can be efficiently computed due to its close relationship with minimum maximal matching; however, in the weighted case such a nice relationship is not known to exist. In this paper, after showing that weighted edge domination is as hard to approximate as the well studied weighted vertex cover problem, we consider a natural strategy, reducing edge-dominating set to edge cover. Our main result is a simple -approximation algorithm for the weighted edge-dominating set problem, improving the existing ratio, due to a simple reduction to weighted vertex cover, of 2r _WVC, where r _WVC is the approximation guarantee of any polynomial-time weighted vertex cover algorithm. The best value of r _WVC currently stands at . Furthermore we establish that the factor of is tight in the sense that it coincides with the integrality gap incurred by a natural linear programming relaxation of the problem.     

Inverse Problems of Matroid Intersection

In this paper we study the inverse problem of matroid intersection: Two matroids M ₁ = (E, ₁) and M ₂ = (E, ₂), their intersection B, and a weight function w on E are given. We try to modify weight w, optimally and with bounds, such that B becomes a maximum weight intersection under the modified weight. It is shown in this paper that the problem can be formulated as a combinatorial linear program and can be further transformed into a minimum cost circulation problem. Hence it can be solved by strongly polynomial time algorithms. We also give a necessary and sufficient condition for the feasibility of the problem. Finally we extend the discussion to the version of the problem with Multiple Intersections.     

Improved Approximation for Breakpoint Graph Decomposition and Sorting by Reversals

Sorting by Reversals (SBR) is one of the most widely studied models of genome rearrangements in computational molecular biology. At present, is the best known approximation ratio achievable in polynomial time for SBR. A very closely related problem, called Breakpoint Graph Decomposition (BGD), calls for a largest collection of edge disjoint cycles in a suitably-defined graph. It has been shown that for almost all instances SBR is equivalent to BGD, in the sense that any solution of the latter corresponds to a solution of the former having the same value. In this paper, we show how to improve the approximation ratio achievable in polynomial time for BGD, from the previously known to for any > 0. Combined with the results in (Caprara, Journal of Combinatorial Optimization, vol. 3, pp. 149–182, 1999b), this yields the same approximation guarantee for n! – O((n – 5)!) out of the n! instances of SBR on permutations with n elements. Our result uses the best known approximation algorithms for Stable Set on graphs with maximum degree 4 as well as for Set Packing where the maximum size of a set is 6. Any improvement in the ratio achieved by these approximation algorithms will yield an automatic improvement of our result.     

On the adjacent vertex-distinguishing total chromatic numbers of the graphs with Δ (G) = 3

Let be a simple graph and T(G) be the set of vertices and edges of G. Let C be a k-color set. A (proper) total k-coloring f of G is a function such that no adjacent or incident elements of T(G) receive the same color. For any , denote . The total k-coloring f of G is called the adjacent vertex-distinguishing if for any edge . And the smallest number of colors is called the adjacent vertex-distinguishing total chromatic number of G. In this paper, we prove that for all connected graphs with maximum degree three. This is a step towards a conjecture on the adjacent vertex-distinguishing total coloring. MSC: 05C15     

On Approximability of Boolean Formula Minimization

For a Boolean function given by a Boolean formula (or a binary circuit) S we discuss the problem of building a Boolean formula (binary circuit) of minimal size, which computes the function g equivalent to , or -equivalent to , i.e., . In this paper we prove that if P NP then this problem can not be approximated with a good approximation ratio by a polynomial time algorithm.     

Fast algorithms for computing the tripartition-based distance between phylogenetic networks

Consider two phylogenetic networks and ’ of size n. The tripartition-based distance finds the proportion of tripartitions which are not shared by and ’. This distance is proposed by Moret et al. (2004) and is a generalization of Robinson-Foulds distance, which is orginally used to compare two phylogenetic trees. This paper gives an -time algorithm to compute this distance, where h is the number of hybrid nodes in and ’ while k is the maximum number of hybrid nodes among all biconnected components in and ’. Note that $k \ll h \ll n$ in a phylogenetic network. In addition, we propose algorithms for comparing galled-trees, which are an important, biological meaningful special case of phylogenetic network. We give an $O(n)$-time algorithm for comparing two galled-trees. We also give an -time algorithm for comparing a galled-tree with another general network, where h and k are the number of hybrid nodes in the latter network and its biggest biconnected component respectively.     

Tight Performance Bounds of CP-Scheduling on Out-Trees

The worst-case behavior of the critical path (CP) algorithm for multiprocessor scheduling with an out-tree task dependency structure is studied. The out-tree is not known in advance and the tasks are released on-line over time (each task is released at the completion time of its direct predecessor task in the out-tree). For each task, the processing time and the remainder (the length of the longest chain of the future tasks headed by this task) become known at its release time. The tight worst-case ratio and absolute error are derived for this strongly clairvoyant on-line model. For out-trees with a specific simple structure, essentially better worst-case ratio and absolute error are derived. Our bounds are given in terms of t _max, the length of the longest chain in the out-tree, and it is shown that the worst-case ratio asymptotically approaches 2 for large t _max when the number of processors , where is an integer close to . A non-clairvoyant on-line version (without knowledge of task processing time and remainder at the release time of the task) is also considered and is shown that the worst-case behavior of width-first search is better or the same as that of the depth-first search.