Catálogo de publicaciones - libros

This paper gives a short survey on algorithmic aspects of the treewidth of graphs. Some alternative characterizations and some applications of the notion are given. The paper also discusses algorithms to compute the treewidth of given graphs, and how these are based on the different characterizations, with an emphasis on algorithms that have been experimentally tested.

We prove that in the List version, the problem of deciding the existence of a locally injective homomorphism to a parameter graph performs a full dichotomy. Namely we show that it is polynomially time solvable if every connected component of has at most one cycle and NP-complete otherwise.

We fully characterise the situations where the existence of a homomorphism from a digraph  to at least one of a finite set  of directed graphs is determined by a finite number of forbidden subgraphs. We prove that these situations, called , are characterised by the non-existence of a homomorphism to  from a finite set of forests.

Furthermore, we characterise all finite maximal antichains in the partial order of directed graphs ordered by the existence of homomorphism. We show that these antichains correspond exactly to the generalised dualities. This solves a problem posed in [1]. Finally, we show that it is NP-hard to decide whether a finite set of digraphs forms a maximal antichain.

It is known to be NP-hard to decide whether a graph can be made chordal by the deletion of vertices. Here we present a uniformly polynomial-time algorithm for the problem: the running time is () for some constant not depending on and some depending only on . For large values of , such an algorithm is much better than trying all the () possibilities. Therefore, the chordal deletion problem parameterized by the number of vertices to be deleted is fixed-parameter tractable. This answers an open question of Cai [2].

We present a fixed-parameter algorithm which computes for a set of points in the plane in time a minimum weight triangulation. The parameter is the number of points in that lie in the interior of the convex hull of and .

We introduce , a new technique for the solution of hard graph problems. It is a combination of the well-known paradigm and [2]. Our approach first randomly colors all edges or nodes of a graph black and white, and then solves the problem recursively on the two induced parts.

We demonstrate this technique by giving new randomized algorithms for the solution of two important problems. These yield runtime bounds of (4) for finding a simple path of length  and (4) for finding edge-disjoint (resp. vertex-disjoint) copies of a graph with edges (resp. nodes) in a given graph. Derandomization gives deterministic algorithms for these problems with running times (2) and (2), respectively.

All these results significantly improve over the currently known best bounds. In particular, our generic algorithms beat specialized ones that have been designed to find triangles or paths of length two.

We propose three algorithms for enumeration problems; given a graph , to find every chordal supergraph (in K) of , to find every interval supergraph (in K) of , and to find every interval subgraph of in K. The algorithms are based on the reverse search method. A graph is chordal if and only if it has no induced chordless cycle of length more than three. A graph is an interval graph if and only if it has an interval representation. To the best of our knowledge, ours are the first results about the enumeration problems to list every interval subgraph of the input graph and to list every chordal/interval supergraph of the input graph in polynomial time. The time complexities of the first algorithm is O((+)) for each output graph, and those for the rest two algorithms are O() for each output graph, where is the number of edges of input graph . We also show that a straight-forward depth-first search type algorithm is not appropriate for these problems.

A dominating set of a graph =(,) is a subset of vertices such that every vertex in has at least one neighbour in . Moreover if is an independent set, i.e. no vertices in are pairwise adjacent, then is said to be an independent dominating set. Finding a minimum independent dominating set in a graph is an NP-hard problem. We give an algorithm computing a minimum independent dominating set of a graph on vertices in time (1.3575). Furthermore, we show that Ω(1.3247) is a lower bound on the worst-case running time of this algorithm.

We show an (1.344)=(2) algorithm for edge-coloring an -vertex graph using three colors. Our algorithm uses polynomial space. This improves over the previous, (2) algorithm of Beigel and Eppstein [1]. We extend a very natural approach of generating inclusion-maximal matchings of the graph. The time complexity of our algorithm is estimated using the “measure and conquer” technique.

e and e graphs are classes of graphs close to graphs in a graph class . They are the classes of graphs obtained by adding or deleting at most edges from a graph in . In this paper, we consider vertex coloring of comparability+e and comparability–e graphs. We show that for comparability+e graphs, vertex coloring is solved in polynomial time for =1 and NP-complete for ≥2. We also show that vertex coloring of comparability–1e graphs is solved in polynomial time.