Catálogo de publicaciones - libros

A graph G is said to be a cluster graph if G is a disjoint union of cliques (complete subgraphs), and a bicluster graph if G is a disjoint union of bicliques (complete bipartite subgraphs). In this work, we study the parameterized version of the NP-hard Bicluster Graph Editing problem, which consists of obtaining a bicluster graph by making the minimum number of modifications in the edge set of an input bipartite graph. When at most k modifications are allowed in the edge set of any input graph ( Bicluster( k ) Graph Editing problem), this problem is FPT, solvable in O(4^ k m ) time by applying a search tree algorithm. It is shown an algorithm with O(4^ k + n + m ) time, which uses a new strategy based on modular decomposition techniques. Furthermore, the same techniques lead to a new form of obtaining a problem kernel with O( k ^2) vertices for the Cluster( k ) Graph Editing problem, in O( n + m ) time. This problem consists of obtaining a cluster graph by modifying at most k edges in an input graph. A previous FPT algorithm for this problem was presented by Gramm et al. [11]. In their solution, a problem kernel with O( k ^2) vertices and O( k ^3) edges is built in O( n ^3) time.

In this paper, we study the cluster editing problem which is fixed parameter tractable. We present the first practical implementation of a FPT based method for cluster editing, using the approach in [6,7], and compare our implementation with the straightforward greedy method and a solution based on linear programming [3]. Our experiments show that the best results are obtained by using the refined branching method in [7] together with interleaving (re-kernelization). We also observe an interesting lack of monotonicity in the running times for “yes” instances with increasing values of k .

Many parameterized problems (as the clique problem or the dominating set problem) ask, given an instance and a natural number k as parameter, whether there is a solution of size k . We analyze the relationship between the complexity of such a problem and the corresponding maximality (minimality) problem asking for a solution of size k maximal (minimal) with respect to set inclusion. As our results show maximality problems may increase the parameterized complexity, while “in terms of the W-hierarchy” minimality problems do not increase the complexity.

We show that every problem in MAX SNP has a lower bound on the optimum solution size that is unbounded and that the above guarantee question with respect to this lower bound is fixed parameter tractable. We next introduce the notion of “tight” upper and lower bounds for the optimum solution and show that the parameterized version of a variant of the above guarantee question with respect to the tight lower bound cannot be fixed parameter tractable unless P = NP , for a class of NP -optimization problems.

We prove that each parameterized counting problem in the class #[P] has a randomized fpt approximation algorithm using a W[P] oracle. Analoguous statements hold for #W[ t ] and #A[ t ] for each t ≥1. These results are parameterized analogues of a theorem due to O.Goldreich and L.Stockmeyer.

An ordering of a graph G =( V , E ) is a one-to-one mapping α : V →{1,2,..., | V |}. The profile of an ordering α of G is prf_ α ( G )=∑_ v  ∈  V ( α ( v )– min { α ( u ): u ∈ N [ v ]}); here N [ v ] denotes the closed neighborhood of  v . The profile prf( G ) of G is the minimum of prf_ α ( G ) over all orderings α of G . It is well-known that prf( G ) equals the minimum number of edges in an interval graph H that contains G as a subgraph. We show by reduction to a problem kernel of linear size that deciding whether the profile of a connected graph G =( V , E ) is at most | V |–1+ k is fixed-parameter tractable with respect to the parameter k . Since | V |–1 is a tight lower bound for the profile of a connected graph G =( V , E ), the parameterization above the guaranteed value | V |–1 is of particular interest.

We study the size of OBDDs (ordered binary decision diagrams) for representing the adjacency function f _ G of a graph G on n vertices. Our results are as follows: -) For graphs of bounded tree-width there is an OBDD of size O (log n ) for f _ G that uses encodings of size O (log n ) for the vertices; -) For graphs of bounded clique-width there is an OBDD of size O ( n ) for f _ G that uses encodings of size O ( n ) for the vertices; -) For graphs of bounded clique-width such that there is a reduced term for G (to be defined below) that is balanced with depth O (log n ) there is an OBDD of size O ( n ) for f _ G that uses encodings of size O (log n ) for the vertices; -) For cographs, i.e. graphs of clique-width at most 2, there is an OBDD of size O ( n ) for f _ G that uses encodings of size O (log n ) for the vertices. This last result improves a recent result by Nunkesser and Woelfel [14].

Matching and packing problems have formed an important class of NP-hard problems. There have been a number of recently developed techniques for parameterized algorithms for these problems, including greedy localization, color-coding plus dynamic programming, and randomized divide-and-conquer. In this paper, we provide further theoretical study on the structures of these problems, and develop improved algorithmic methods that combine existing and new techniques to obtain improved algorithms for matching and packing problems. For the 3-set packing problem, we present a deterministic algorithm of time O ^*(4.61^3k), which significantly improves the previous best deterministic algorithm of time O ^*(12.8^3k). For the 3-d matching problem, we develop a new randomized algorithm of running time O ^*(2.32^3k) and a new deterministic algorithm of running time O ^*(2.77^3k). Our randomized algorithm improves the previous best randomized algorithm of running time O ^*(2.52^3k), and our deterministic algorithm significantly improves the previous best deterministic algorithm of running time O ^*(12.8^3k). Our results also imply improved algorithms for various triangle packing problems in graphs.

The notion of fixed-parameter approximation is introduced to investigate the approximability of optimization problems within the framework of fixed-parameter computation. This work partially aims at enhancing the world of fixed-parameter computation in parallel with the conventional theory of computation that includes both exact and approximate computations. In particular, it is proved that fixed-parameter approximability is closely related to the approximation of small-cost solutions in polynomial time. It is also demonstrated that many fixed-parameter intractable problems are not fixed-parameter approximable. On the other hand, fixed-parameter approximation appears to be a viable approach to solving some inapproximable yet important optimization problems. For instance, all problems in the class MAX SNP admit fixed-parameter approximation schemes in time O (2 $^{O((1-{\epsilon}/{\it O}(1)){\it k})}$ p ( n )) for any small ε > 0.

Combining classical approximability questions with parameterized complexity, we introduce a theory of parameterized approximability . The main intention of this theory is to deal with the efficient approximation of small cost solutions for optimisation problems.