Catálogo de publicaciones - libros

Our motivation for this work is the remarkable discovery that many large-scale real-world graphs ranging from Internet and World Wide Web to social and biological networks exhibit a power-law distribution: the number of nodes of a given degree is proportional to where > 0 is a constant that depends on the application domain. There is practical evidence that combinatorial optimization in power-law graphs is easier than in general graphs, prompting the basic theoretical question: Is combinatorial optimization in power-law graphs easy? Does the answer depend on the power-law exponent ? Our main result is the proof that many classical NP-hard graph-theoretic optimization problems remain NP-hard on power law graphs for certain values of . In particular, we show that some classical problems, such as CLIQUE and COLORING, remains NP-hard for all  ≥ 1. Moreover, we show that all the problems that satisfy the so-called “optimal substructure property” remains NP-hard for all > 0. This includes classical problems such as MIN VERTEX-COVER, MAX INDEPENDENT-SET, and MIN DOMINATING-SET. Our proofs involve designing efficient algorithms for constructing graphs with prescribed degree sequences that are tractable with respect to various optimization problems.

The regularity lemma of Szemerédi gives a concise approximate description of a graph via a so called regular-partition of its vertex set. In this paper we address the following problem: can a graph have two “distinct” regular partitions? It turns out that (as observed by several researchers) for the standard notion of a regular partition, one can construct a graph that has very distinct regular partitions. On the other hand we show that for the stronger notion of a regular partition that has been recently studied, all such regular partitions of the same graph must be very “similar”.

En route, we also give a short argument for deriving a recent variant of the regularity lemma obtained independently by Rödl and Schacht ([11]) and Lovász and Szegedy ([9,10]), from a previously known variant of the regularity lemma due to Alon et al.[2]. The proof also provides a deterministic polynomial time algorithm for finding such partitions.

In this paper, we give linear time algorithms to decide core stability, core largeness, exactness, and extendability of flow games on uniform networks (all edge capacities are 1). We show that a uniform flow game has a stable core if and only if the network is a balanced DAG (for all non-terminal vertices, indegree equals outdegree), which can be decided in linear time. Then we show that uniform flow games are exact, extendable, and have a large core if and only if the network is a balanced directed series-parallel graph, which again can be decided in linear time.

We consider constant depth circuits augmented with few exact threshold gates with arbitrary weights. We prove strong (up to exponential) size lower bounds for such circuits computing symmetric Boolean functions. Our lower bound is expressed in terms of a natural parameter, the , of symmetric functions. Furthermore, in the quasi-polynomial size setting our results provides an characterization of the class of symmetric functions in terms of their balance.

We investigate the problem of finding an unknown cut through querying vertices of a graph . Our complexity measure is the number of submitted queries. To avoid some worst cases, we make a few assumptions which allow us to obtain an algorithm with the worst case query complexity of in which is the number of vertices adjacent to cut-edges. We also provide a matching lowerbound and then prove if is a tree our algorithm can asymptotically achieve the information theoretic lowerbound on the query complexity. Finally, we show it is possible to remove our extra assumptions but achieve an approximate solution.

We derive quadratic lower bounds on the *-complexity of sum-of-products-of-sums () formulas for classes of polynomials that have too few partial derivatives for the techniques of Shpilka and Wigderson [10,9]. This involves a notion of “resistance” which connotes full-degree behavior of under any projection to an affine space of sufficiently high dimension. They also show stronger lower bounds over the reals than the complex numbers or over arbitrary fields. Separately, by applying a special form of the Baur-Strassen Derivative Lemma tailored to formulas, we obtain sharper bounds on + ,*-complexity than those shown for *-complexity by Shpilka and Wigderson [10], most notably for the lowest-degree cases of the polynomials they consider.

An ordered labeled tree is a tree in which the nodes are labeled and the left-to-right order among siblings is significant. The edit distance between two ordered labeled trees is the minimum cost of transforming one tree into the other by a sequence of edit operations. Among the best known tree edit distance algorithms, the majority can be categorized in terms of a framework named cover strategy. In this paper, we investigate how certain locally linear features may be utilized to improve the time complexity for computing the tree edit distance. We define structural linearity and present a method incorporating linearity which can work with existing cover-strategy based tree algorithms. We show that by this method the time complexity for an input of size becomes where is the time complexity of any cover-strategy algorithm applied to an input size , with , and the magnitude of is reversely related to the degree of linearity. This result is an improvement of previous results when and would be useful for situations in which is in general substantially smaller than , such as RNA secondary structure comparisons in computational biology.

Tandem repeated regions are closely related to some genetic diseases in human beings. Once a region containing pseudo-periodic repeats is found, it is interesting to study the history of creating the repeats. It is important to reveal the relationship between repeats and genetic diseases. The duplication model has been proposed to describe the history [3,10,11]. We design a polynomial time approximation scheme (PTAS) for the case where the size of the duplication box is 1. Our PTAS is faster than the best known algorithm in [11]. For example, to reach ratio-1.5, our algorithm takes () time while the algorithm in [11] takes () time. We also design a ratio-2 approximation algorithm for the case where the size of the duplication box is at most 2. This is the first approximation algorithm with guaranteed ratio for this case.

Greedy algorithms are simple, but their relative power is not well understood. The priority framework [5] captures a key notion of “greediness” in the sense that it processes (in some locally optimal manner) one data item at a time, depending on and only on the current knowledge of the input. This algorithmic model provides a tool to assess the computational power and limitations of greedy algorithms, especially in terms of their approximability. In this paper, we study priority algorithm approximation ratios for the Subset-Sum Problem, focusing on the power of revocable decisions. We first provide a tight bound of  ≈ 0.657 for irrevocable priority algorithms. We then show that the approximation ratio of fixed order revocable priority algorithms is between  ≈ 0.780 and  ≈ 0.852, and the ratio of adaptive order revocable priority algorithms is between 0.8 and  ≈ 0.893.

We give efficient distributed approximation algorithms for weighted versions of the maximum matching problem and the minimum dominating set problem for graphs from minor-closed families. To complement these results we indicate that no efficient distributed algorithm for the minimum weight connected dominating set exists.