Catálogo de publicaciones - libros

We study the problem of finding occurrences of motifs in vertex-colored graphs, where a motif is a multiset of colors, and an occurrence of a motif is a subset of connected vertices whose multiset of colors equals the motif. This problem has applications in metabolic network analysis, an important area in bioinformatics. We give two positive results and three negative results that together draw sharp borderlines between tractable and intractable instances of the problem.

We prove that finding a rooted subtree with at least leaves in a digraph is a fixed parameter tractable problem. A similar result holds for finding rooted spanning trees with many leaves in digraphs from a wide family that includes all strong and acyclic digraphs. This settles completely an open question of Fellows and solves another one for digraphs in . Our algorithms are based on the following combinatorial result which can be viewed as a generalization of many results for a ‘spanning tree with many leaves’ in the undirected case, and which is interesting on its own: If a digraph of order with minimum in-degree at least 3 contains a rooted spanning tree, then contains one with at least (/2)− 1 leaves.

We give an fpt approximation algorithm for the directed vertex disjoint cycle problem. Given a directed graph with vertices and a positive integer , the algorithm constructs a family of at least /() disjoint cycles of if the graph has a family of at least disjoint cycles (and otherwise may still produce a solution, or just report failure). Here is a computable function such that /() is nondecreasing and unbounded. The running time of our algorithm is polynomial.

The directed vertex disjoint cycle problem is hard for the parameterized complexity class W1, and to the best of our knowledge our algorithm is the first fpt approximation algorithm for a natural W1-hard problem.

We develop a generic framework for deriving linear-size problem kernels for NP-hard problems on planar graphs. We demonstrate the usefulness of our framework in several concrete case studies, giving new kernelization results for , , , and on planar graphs. On the route to these results, we present effective, problem-specific data reduction rules that are useful in any approach attacking the computational intractability of these problems.

We consider the problem of constructing efficient locally decodable codes in the presence of a computationally bounded adversary. Assuming the existence of one-way functions, we construct locally decodable codes with positive information rate and (almost optimal) query complexity which can correctly decode any given bit of the message from constant channel error rate . This compares favorably to our state of knowledge locally-decodable codes without cryptographic assumptions. For all our constructions, the probability for any polynomial-time adversary, that the decoding algorithm incorrectly decodes any bit of the message is negligible in the security parameter.

In the dedicated-key setting, one uses a compression function :{0,1} × {0,1} →{0,1} to build a family of hash functions indexed by a key space . This is different from the more traditional design approach used to build hash functions such as MD5 or SHA-1, in which compression functions and hash functions do not have dedicated key inputs. We explore the benefits and drawbacks of building hash functions in the dedicated-key setting (as compared to the more traditional approach), highlighting several unique features of the former. Should one choose to build hash functions in the dedicated-key setting, we suggest utilizing multi-property-preserving (MPP) domain extension transforms. We analyze seven existing dedicated-key transforms with regard to the MPP goal and propose two simple new MPP transforms.

Secure use of the BGLS [1] aggregate signature schemes is restricted to the aggregation of distinct messages (for the basic scheme) or per-signer distinct messages (for the enhanced, prepend-public-key version of the scheme). We argue that these restrictions preclude interesting applications, make usage of the schemes error-prone and are generally undesirable in practice. Via a new analysis and proof, we show how the restrictions can be lifted, yielding the first truly unrestricted aggregate signature scheme. Via another new analysis and proof, we show that the distinct signer restriction on the sequential aggregate signature schemes of [2] can also be dropped, yielding an unrestricted sequential aggregate signature scheme.

Ring signatures, introduced by Rivest, Shamir and Tauman, enable a user to sign a message anonymously on behalf of a “ring”. A ring is a group of users, which includes the signer. We propose a ring signature scheme that has size where is the number of users in the ring. An additional feature of our scheme is that it has perfect anonymity.

Our ring signature like most other schemes uses the common reference string model. We offer a variation of our scheme, where the signer is guaranteed anony- mity even if the common reference string is maliciously generated.

The construction of perfect hash functions is a well-studied topic. In this paper, this concept is generalized with the following definition. We say that a family of functions from [] to [] is a -balanced (,)-family of perfect hash functions if for every  ⊆ [], || = , the number of functions that are 1-1 on is between / and for some constant  > 0. The standard definition of a family of perfect hash functions requires that there will be at least one function that is 1-1 on , for each of size . In the new notion of balanced families, we require the number of 1-1 functions to be almost the same (taking to be close to 1) for every such . Our main result is that for any constant > 1, a -balanced (,)-family of perfect hash functions of size 2 log can be constructed in time 2 log. Using the technique of color-coding we can apply our explicit constructions to devise approximation algorithms for various counting problems in graphs. In particular, we exhibit a deterministic polynomial time algorithm for approximating both the number of simple paths of length and the number of simple cycles of size for any in a graph with vertices. The approximation is up to any fixed desirable relative error.

In this paper we present a new approximation algorithm for the (MEBR) problem in ad hoc wireless networks that has exponentially better approximation factor than the well-known Minimum Spanning Tree (MST) heuristic. Namely, for any instance where a minimum spanning tree of the set of stations is guaranteed to cost at most times the cost of an optimal solution for MEBR, we prove that our algorithm achieves an approximation ratio bounded by 2ln  − 2 ln 2 + 2. This result is particularly relevant for its consequences on Euclidean instances where we significantly improve previous results.