Search

International audience; We present subexponential parameterized algorithms on planar graphs for a family of problems of the following shape: given a graph, find a connected (induced) subgraph with bounded maximum degree and with maximum number of edges (or vertices). These problems are natural generalisations of the Longest Path problem. Our approach uses bidimensionality theory combined with novel dynamic programming techniques over branch decompositions of the input graph. These techniques can be applied to a more general family of problems that deal with finding connected subgraphs under certain degree constraints.

A conjecture by D. Seese states that if a set of graphs has a decidable monadic second-order theory, then it is the image of a set of trees under a transformation of relational structures defined by monadic second-order formulas, or equivalently, has bounded clique-width. We prove that this conjecture is true if and only if it is true for the particular cases of bipartite undirected graphs, of directed graphs, of partial orders and of comparability graphs. We also prove that it is true for line graphs, for interval graphs and for partial orders of dimension 2. Our treatment of certain countably infinite graphs uses a representation of countable linear orders by binary trees that can be constructed by monadic second-order formulas. By using a counting argument, we show the intrinsic limits of the methods used here to handle this conjecture.

We first present new structural properties of a two-pair in various graphs. A two-pair is used in a well-known characterization of weakly chordal graphs. Based on these properties, we prove the main theorem: a graph G is a weakly chordal (K"2","3,4P"2@?,P"2@?P"4@?,P"6@?,H"1,H"2,H"3)-free graph if and only if G 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 an 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.

The Q-index of a simple graph G is the largest eigenvalue of the matrix Q, the signless Laplacian of G. It is well-known that in the set of connected graphs with fixed order and size, the graphs with maximal Q-index are the nested split graphs (also known as threshold graphs). In this paper, we focus our attention on the eigenvector techniques for getting some (lower and upper) bounds on the Q-index of nested split graphs. In addition, we give some computational results in order to compare these bounds.

We investigate the maximum number of edges in a graph with a prescribed number of 1-factors. We also examine the structure of such extremal graphs.

A team of mobile agents, called guards, tries to keep an intruder out of an assigned area by blocking all possible attacks. In a graph model for this setting, the guards and the intruder are located on the vertices of a graph, and they move from node to node via connecting edges. The area protected by the guards is an induced subgraph of the given graph. We investigate the algorithmic aspects of the guarding problem, which is to find the minimum number of guards sufficient to patrol the area. We show that the guarding problem is PSPACE-hard and provide a set of approximation algorithms. All approximation algorithms are based on the study of a variant of the game where the intruder must reach the guarded area in a single step in order to win. This variant of the game appears to be a 2-approximation for the guarding problem, and for graphs without cycles of length 5 the minimum number of required guards in both games coincides. We give a polynomial time algorithm for solving the one-step guarding problem in graphs of bounded treewidth, and complement this result by showing that the problem is W[1]-hard parameterized by the treewidth of the input graph. We also show that the problem is fixed parameter tractable (FPT) parameterized by the treewidth and maximum degree of the input graph. Finally, we turn our attention to a large class of sparse graphs, including planar graphs and graphs of bounded genus, namely apex-minor-free graphs. We prove that the one-step guarding problem is FPT and possess a PTAS on apex-minor-free graphs.

International audience; In this paper we consider graphs G whose vertices can be represented as single-bend paths (i.e., paths with at most one turn) on a rectangular grid, such that two vertices are adjacent in G if and only if the corresponding paths share at least one edge of the grid. These graphs, called B1-EPG graphs, were first introduced in Golumbic et al. (2009) [13]. Here we show that the neighborhood of every vertex in a B1-EPG graph induces a weakly chordal graph. From this we conclude that the family F of B1-EPG graphs satisfies the Erdős–Hajnal property with View the MathML source, i.e., that every B1-EPG graph on n vertices contains either a clique or a stable set of size at least View the MathML source. Finally we give a characterization of B1-EPG graphs among some subclasses of chordal graphs, namely chordal bull-free graphs, chordal claw-free graphs, chordal diamond-free graphs, and special cases of split graphs.

We study various optimization problems in t-subtree graphs, the intersection graphs of t-subtrees, where a t-subtree is the union of t disjoint subtrees of some tree. This graph class generalizes both the class of chordal graphs and the class of t-interval graphs, a generalization of interval graphs that has recently been studied from a combinatorial optimization point of view. We present approximation algorithms for the Maximum Independent Set, Minimum Coloring, Minimum Vertex Cover, Minimum Dominating Set, and Maximum Clique problems.

The d-dimensional hypercube, H"d, is the graph on 2^d vertices, which correspond to the 2^dd-vectors whose components are either 0 or 1, two of the vertices being adjacent when they differ in just one coordinate. The notion of Hamming graphs (denoted by K"q^d) generalizes the notion of hypercubes: The vertices correspond to the q^dd-vectors where the components are from the set {0,1,2,...,q-1}, and two of the vertices are adjacent if and only if the corresponding vectors differ in exactly one component. In this paper we show that the pw(H"d)=@?"m"="0^d^-^1mm2 and the tw(K"q^d)=@q(q^d/d).

We show that the class of unit grid intersection graphs properly includes both of the classes of interval bigraphs and of P6-free chordal bipartite graphs. We also demonstrate that the classes of unit grid intersection graphs and of chordal bipartite graphs are incomparable.

Let Y be a subset of real numbers. A Y-dominating function of a graph G=(V,E) is a function f:V->Y such that @?"u"@?"N"""G"["v"]f(u)>=1 for all vertices [email protected]?V, where N"G[v]={v}@?{u|(u,v)@?E}. Let f(S)[email protected]?"u"@?"Sf(u) for any subset S of V and let f(V) be the weight of f. The Y-domination problem is to find a Y-dominating function of minimum weight for a graph G=(V,E). In this paper, we study the variations of Y-domination such as {k}-domination, k-tuple domination, signed domination, and minus domination for some classes of graphs. We give formulas to compute the {k}-domination, k-tuple domination, signed domination, and minus domination numbers of paths, cycles, n-fans, n-wheels, n-pans, and n-suns. Besides, we present a unified approach to these four problems on strongly chordal graphs. Notice that trees, block graphs, interval graphs, and directed path graphs are subclasses of strongly chordal graphs. This paper also gives complexity results for the problems on doubly chordal graphs, dually chordal graphs, bipartite planar graphs, chordal bipartite graphs, and planar graphs.

Permutation graphs form a well-studied subclass of cocomparability graphs. Permutation graphs are the cocomparability graphs whose complements are also cocomparability graphs. A triangulation of a graph G is a graph H that is obtained by adding edges to G to make it chordal. If no triangulation of G is a proper subgraph of H then H is called a minimal triangulation. The main theoretical result of the paper is a characterisation of the minimal triangulations of a permutation graph, that also leads to a succinct and linear-time computable representation of the set of minimal triangulations. We apply this representation to devise linear-time algorithms for various minimal triangulation problems on permutation graphs, in particular, we give linear-time algorithms for computing treewidth and minimum fill-in on permutation graphs.

Multiple-interval graphs are a natural generalization of interval graphs where each vertex may have more than one interval associated with it. Many applications of interval graphs also generalize to multiple-interval graphs, often allowing for more robustness in the modeling of the specific application. With this motivation in mind, a recent systematic study of optimization problems in multiple-interval graphs was initiated. In this sequel, we study multiple-interval graph problems from the perspective of parameterized complexity. The problems under consideration are k-Independent Set, k-Dominating Set, and k-Clique, which are all known to be W[1]-hard for general graphs, and NP-complete for multiple-interval graphs. We prove that k-Clique is in FPT, while k-Independent Set and k-Dominating Set are both W[1]-hard. We also prove that k-Independent Dominating Set, a hybrid of the two above problems, is also W[1]-hard. Our hardness results hold even when each vertex is associated with at most two intervals, and all intervals have unit length. Furthermore, as an interesting byproduct of our hardness results, we develop a useful technique for showing W[1]-hardness via a reduction from the k-Multicolored Clique problem, a variant of k-Clique. We believe this technique has interest in its own right, as it should help in simplifying W[1]-hardness results which are notoriously hard to construct and technically tedious.