Catálogo de publicaciones - libros

Search games are attractive for their correspondence with classical width parameters. For instance, the search number (a.k.a. search number) of a graph is equal to its pathwidth plus 1, and the search number of a graph is equal to its treewidth plus 1. The variants of these games ask for search strategies that are connected, i.e., at every step of the strategy, the searched part of the graph induces a connected subgraph. We focus on search strategies, i.e., strategies for which every node is searched exactly once. It is known that the monotone connected visible search number of an -node graph is at most (log) times its visible search number. First, we prove that this logarithmic bound is tight. Precisely, we prove that there is an infinite family of graphs for which the ratio monotone connected visible search number over visible search number is Ω(log). Second, we prove that, as opposed to the non-connected variant of visible graph searching, “recontamination helps” for connected visible search. Precisely, we describe an infinite family of graphs for which any monotone connected visible search strategy for any graph in this family requires strictly more searchers than the connected visible search number of the graph.

We first present new structural properties of a two-pair in various graphs. A two-pair is used for characterizing weakly chordal graphs. Based on these properties, we prove the main theorem: a graph is a weakly chordal (, , , , , , )-free graph if and only if is an edge intersection graph of subtrees on a tree with maximum degree 4. This characterizes the so called [4,4,2] graphs. The proof of the theorem constructively finds the representation. Thus, we obtain a algorithm to construct an edge intersection model of subtrees on a tree with maximum degree 4 for such a given graph. This is a recognition algorithm for [4,4,2] graphs.

We consider the dynamic recognition problem for the class of -sparse graphs: the objective is to handle edge/vertex additions and deletions, to recognize if each such modification yields a -sparse graph, and if yes, to update a representation of the graph. Our approach relies on maintaining the modular decomposition tree of the graph, which we use for solving the recognition problem. We establish conditions for each modification to yield a -sparse graph and obtain a fully dynamic recognition algorithm which handles edge modifications in (1) time and vertex modifications in () time for a vertex of degree . Thus, our algorithm implies an optimal edges-only dynamic algorithm and a new optimal incremental algorithm for -sparse graphs. Moreover, by maintaining the children of each node of the modular decomposition tree in a binomial heap, we can handle vertex deletions in (log) time, at the expense of needing (log) time for each edge modification and ( log) time for the addition of a vertex adjacent to vertices.

A of a graph is a subset of inducing a complete subgraph. A is a maximal complete set. Denote by the of . The of , denoted by (), is the intersection graph of . Say that is if there exists a graph such that =(). The clique graph recognition problem asks whether a given graph is a clique graph. A sufficient condition was given by Hamelink in 1968, and a characterization was proposed by Roberts and Spencer in 1971. We prove that the clique graph recognition problem is NP-complete.

In this paper, a new general decomposition theory inspired from modular graph decomposition is presented. Our main result shows that, within this general theory, most of the nice algorithmic tools developed for modular decomposition are still efficient.

This theory not only unifies the usual modular decomposition generalisations such as modular decomposition of directed graphs and of 2-structures, but also decomposition by star cutsets.

We give two new algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs. The algorithms either provide a model for the input graph, or a certificate that proves that such a model does not exist and can be authenticated in () time.

We discuss eleven well-known basic models of distributed computing: four message-passing models that differ by the (non-)existence of port-numbers and a hierarchy of seven local computations models. In each of these models, we study the computational complexity of the decision problem whether the leader election and/or naming problem can be solved on a given network. It is already known that this problem is solvable in polynomial time for two models and co-NP-complete for another one. Here, we settle the computational complexity for the remaining eight problems by showing co-NP-completeness. The results for six models and the already known co-NP-completeness result follow from a more general result on graph labelings.

A matching is called flexible if there exists an alternating cycle with respect to . Given a graph =(,) and  ⊆ , a flexible matching  ⊆  is sought which covers a maximum number of vertices belonging to . It is proved that the existence of such a matching is decidable in time, and a concrete flexible maximum -matching can also be found in the same amount of time.

We study the problem of simultaneously embedding several graphs on the same vertex set in such a way that edges common to two or more graphs are represented by the same curve. This problem is known as . We show that this problem is closely related to the problem: Can a graph be drawn such that all edge crossings occur in a given set of edge pairs? By exploiting this relationship we can explain why the simultaneous embedding problem is challenging, both from a computational and a combinatorial point of view.

More precisely, we prove that simultaneously embedding graphs with fixed edges is NP-complete even for three planar graphs. For two planar graphs the complexity status is still open.

A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. An -cycle cover is a cycle cover in which the length of every cycle is in the set  ⊆ ℕ. For most sets , the problem of computing -cycle covers of maximum weight is NP-hard and APX-hard.

We devise polynomial-time approximation algorithms for -cycle covers. More precisely, we present a factor 2 approximation algorithm for computing -cycle covers of maximum weight in undirected graphs and a factor 20/7 approximation algorithm for the same problem in directed graphs. Both algorithms work for arbitrary sets . To do this, we develop a general decomposition technique for cycle covers.

Finally, we show tight lower bounds for the approximation ratios achievable by algorithms based on such decomposition techniques.