Catálogo de publicaciones - libros

The (CR) problem measures how far a tree of characters differs from exhibiting a so-called “perfect phylogeny”. For input consisting of a vertex-colored tree , the problem is to determine whether recoloring at most vertices can achieve a convex coloring, meaning by this a coloring where each color class induces a connected subtree. The problem was introduced by Moran and Snir, who showed that CR is NP-hard, and described a search-tree based FPT algorithm with a running time of ((/log)). The Moran and Snir result did not provide any nontrivial kernelization. Subsequently, a kernelization with a large polynomial bound was established. Here we give the strongest FPT results to date on this problem: (1) We show that in polynomial time, a problem kernel of size () can be obtained, and (2) We prove that the problem can be solved in linear time for fixed . The technique used to establish the second result appears to be of general interest and applicability for bounded treewidth problems.

We investigate the maximum number of simple cycles and the maximum number of Hamiltonian cycles in a planar graph with vertices. Using the transfer matrix method we construct a family of graphs which have at least 2.4262 simple cycles and at least 2.0845 Hamilton cycles.

Based on counting arguments for perfect matchings we prove that 2.3404 is an upper bound for the number of Hamiltonian cycles. Moreover, we obtain upper bounds for the number of simple cycles of a given length with a face coloring technique. Combining both, we show that there is no planar graph with more than 2.8927 simple cycles. This reduces the previous gap between the upper and lower bound for the exponential growth from 1.03 to 0.46.

It is shown that the traveling salesman problem for graphs of degree at most three with vertices can be solved in time (1.251), improving the previous bound (1.260) by Eppstein.

Geometric intersection graphs are intensively studied both for their practical motivation and interesting theoretical properties. Many such classes are hard to recognize. We ask the question if imposing restrictions on the girth (the length of a shortest cycle) of the input graphs may help in finding polynomial time recognition algorithms. We give examples in both directions. First we present a polynomial time recognition algorithm for intersection graphs of polygons inscribed in a circle for inputs of girth greater than four (the general recognition problem is NP-complete). On the other hand, we prove that recognition of intersection graphs of segments in the plane remains NP-hard for graphs with arbitrarily large girth.

We use the connection between resource-bounded dimension and the online mistake-bound model of learning to show that the following classes have polynomial-time dimension zero. As corollary, all sets which are hard for exponential time under these reductions are exponentially dense. The first item subsumes two previous results and the second item answers a question of Lutz and Mayordomo. Our proofs use Littlestone’s Winnow2 algorithm for learning -of- threshold functions and Maass and Turán’s algorithm for learning halfspaces.

In a graph  = (,), a vertex subset  ⊆  of size  is called -isolated if it has less than · outgoing edges. We repair a nontrivially flawed algorithm for enumerating all -isolated cliques due to Ito et al. [European Symposium on Algorithms 2005] and obtain an algorithm running in (4··||) time. We describe a speedup trick that also helps parallelizing the enumeration. Moreover, we introduce a more restricted and a more general isolation concept and show that both lead to faster enumeration algorithms. Finally, we extend our considerations to -plexes (a relaxation of the clique notion), pointing out a W[1]-hardness result and providing a fixed-parameter algorithm for enumerating isolated -plexes.

Sequence alignment is a central problem in bioinformatics. The classical dynamic programming algorithm aligns two sequences by optimizing over possible insertions, deletions and substitution. However, other evolutionary events can be observed, such as inversions, tandem duplications or moves (transpositions). It has been established that the extension of the problem to move operations is NP-complete. Previous work has shown that an extension restricted to non-overlapping inversions can be solved in () with a restricted scoring scheme. In this paper, we show that the alignment problem extended to non-overlapping moves can be solved in () for general scoring schemes, (log) for concave scoring schemes and () for restricted scoring schemes. Furthermore, we show that the alignment problem extended to non-overlapping moves, inversions and tandem duplications can be solved with the same time complexities. Finally, an example of an alignment with non-overlapping moves is provided.

We show how to count all minimum weighted dominating sets of a graph on vertices in time . Our algorithm is a combination of branch and bound approach along with dynamic programming on graphs with bounded treewidth. To achieve bound we introduce a technique of measuring running time of our algorithm by combining approach with linear programming.

We consider the problem of scheduling a set of equal-length intervals arriving online, where each interval is associated with a weight and the objective is to maximize the total weight of completed intervals. An optimal 4-competitive algorithm has long been known in the deterministic case, but the randomized case remains open. We give the first randomized algorithm for this problem, achieving a competitive ratio of 3.618. We also prove a randomized lower bound of 4/3, which is an improvement over the previous 5/4 result, and a lower bound of 2 for a class of barely random algorithms which include our new algorithm. We also show that the techniques can be carried to the deterministic multiprocessor case, giving a 3.618-competitive 2-processor algorithm, a 5/4 lower bound for any number of processors, and a 2 lower bound for 2 processors.

This paper deals with problems which fall into the domain of selfish scheduling: a protocol is in charge of building a schedule for a set of tasks without directly knowing their length. The protocol gets these informations from agents who control the tasks. The aim of each agent is to minimize the completion time of her task while the protocol tries to minimize the maximal completion time. When an agent reports the length of her task, she is aware of what the others bid and also of the protocol’s algorithm. Then, an agent can bid a false value in order to optimize her individual objective function. With erroneous information, even the most efficient algorithm may produce unreasonable solutions. An algorithm is truthful if it prevents the selfish agents from lying about the length of their task. The central question in this paper is: We study the problem of scheduling selfish tasks on parallel identical machines. This question has been raised by Christodoulou et al [8] in a distributed system, but it is also relevant in centrally controlled systems. Without considering side payments, our goal is to give a picture of the performance under the condition of truthfulness.