Search

Chordal graphs, also called triangulated graphs, are important in algorithmic graph theory. In this paper we generalise the definition of chordal graphs to the class of directed graphs. Several structural properties of chordal graphs that are crucial for algorithmic applications carry over to the directed setting, including notions like simplicial vertices, perfect elimination orderings, and characterisation by forbidden subgraphs resembling chordless cycles. Moreover, just as chordal graphs are related to treewidth, the chordal digraphs will be related to Kelly-width. Chordal digraphs coincide with the perfect elimination digraphs arising in the study of Gaussian elimination on sparse linear systems [Haskins and Rose, 1973]. [ABSTRACT FROM AUTHOR]

Cluster Editing is a classical graph theoretic approach to tackle the problem of data set clustering: it consists of modifying a similarity graph into a disjoint union of cliques, i.e, clusters. As pointed out in a number of recent papers, the cluster editing model is too rigid to capture common features of real data sets. Several generalizations have thereby been proposed. In this paper, we introduce (p,q)-cluster graphs, where each cluster misses at most p edges to be a clique, and there are at most q edges between a cluster and other clusters. Our generalization is the first one that allows a large number of false positives and negatives in total, while bounding the number of these locally for each cluster by p and q. We show that recognizing (p,q)-cluster graphs is NP-complete when p and q are input. On the positive side, we show that (0,q)-cluster, (p,1)-cluster, (p,2)-cluster, and (1,3)-cluster graphs can be recognized in polynomial time. [ABSTRACT FROM AUTHOR]

Boolean-width is a recently introduced graph invariant. Similar to tree-width, it measures the structural complexity of graphs. Given any graph G and a decomposition of G of boolean-width k, we give algorithms solving a large class of vertex subset and vertex partitioning problems in time ]> . We relate the boolean-width of a graph to its branch-width and to the boolean-width of its incidence graph. For this we use a constructive proof method that also allows much simpler proofs of similar results on rank-width in [S. Oum. Rank-width is less than or equal to branch-width. Journal of Graph Theory 57(3):239–244, 2008]. For an n-vertex random graph, with a uniform edge distribution, we show that almost surely its boolean-width is Θ(log2n) – setting boolean-width apart from other graph invariants – and it is easy to find a decomposition witnessing this. Combining our results gives algorithms that on input a random graph on n vertices will solve a large class of vertex subset and vertex partitioning problems in quasi-polynomial time ]> . [ABSTRACT FROM AUTHOR]

The Feedback Vertex Set problem asks whether a graph contains q vertices meeting all its cycles. This is not a local property, in the sense that we cannot check if q vertices meet all cycles by looking only at their neighbors. Dynamic programming algorithms for problems based on non-local properties are usually more complicated. In this paper, given a graph G of cliquewidth cw and a cw-expression of G, we solve the Minimum Feedback Vertex Set problem in time ]> . Our algorithm applies a non-standard dynamic programming on a so-called k-module decomposition of a graph, as defined by Rao [26], which is easily derivable from a k-expression of the graph. The related notion of module-width of a graph is tightly linked to both cliquewidth and nlc-width, and in this paper we give an alternative equivalent characterization of module-width. [ABSTRACT FROM AUTHOR]

In the Star System problem we are given a set system and asked whether it is realizable by the multi-set of closed neighborhoods of some graph, i.e., given subsets S1,S2, … ,Sn of an n-element set V does there exist a graph G = (V,E) with {N[v]: v ϵ V} = {S1,S2, … ,Sn}? For a fixed graph H the H-free Star System problem is a variant of the Star System problem where it is asked whether a given set system is realizable by closed neighborhoods of a graph containing no H as an induced subgraph. We study the computational complexity of the H-free Star System problem. We prove that when H is a path or a cycle on at most 4 vertices the problem is polynomial time solvable. In complement to this result, we show that if H belongs to a certain large class of graphs the H-free Star System problem is NP-complete. In particular, the problem is NP-complete when H is either a cycle or a path on at least 5 vertices. This yields a complete dichotomy for paths and cycles. [ABSTRACT FROM AUTHOR]

A graph G on n vertices is a k-leaf power ( ]> ) if it is isomorphic to a graph that can be ˵generated″ from a tree T that has n leaves, by taking the leaves to represent vertices of G, and making two vertices adjacent if and only if they are at distance at most k in T. We address two questions in this paper: (1) As k increases, do we always have ]> ? Answering an open question of Andreas Brandstädt and Van Bang Le [2,3,1], we show that the answer, perhaps surprisingly, is ˵no.″ (2) How should one design algorithms to determine, for k-leaf powers, if they have some property? One way this can be done is to use the fact that k-leaf powers have bounded cliquewidth. This fact, plus the FPT cliquewidth approximation algorithm of Oum and Seymour [14], combined with the results of Courcelle, Makowsky and Rotics [7], allows us to conclude that properties expressible in a general logic formalism, can be decided in FPT time for k-leaf powers, parameterizing by k. This is wildly inefficient. We explore a different approach, under the assumption that a generating tree is given with the graph. We show that one can use the tree directly to decide the property, by means of a finite-state tree automaton. (A more general theorem has been independently obtained by Blumensath and Courcelle [5].) We place our results in a general context of ˵tree-definable″ graph classes, of which k-leaf powers are one particular example. [ABSTRACT FROM AUTHOR]

Tree decompositions of graphs are of fundamental importance in structural and algorithmic graph theory. Planar decompositions generalise tree decompositions by allowing an arbitrary planar graph to index the decomposition. We prove that every graph that excludes a fixed graph as a minor has a planar decomposition with bounded width and a linear number of bags. The crossing number of a graph is the minimum number of crossings in a drawing of the graph in the plane. We prove that planar decompositions are intimately related to the crossing number, in the sense that a graph with bounded degree has linear crossing number if and only if it has a planar decomposition with bounded width and linear order. It follows from the above result about planar decompositions that every graph with bounded degree and an excluded minor has linear crossing number. Analogous results are proved for the convex and rectilinear crossing numbers. In particular, every graph with bounded degree and bounded tree-width has linear convex crossing number, and every K3,3-minor-free graph with bounded degree has linear rectilinear crossing number. [ABSTRACT FROM AUTHOR]

Kelly-width is a parameter of directed graphs recently proposed by Hunter and Kreutzer as a directed analogue of treewidth. We give several alternative characterizations of directed graphs of bounded Kelly-width in support of this analogy. We apply these results to give the first polynomial-time algorithm recognizing directed graphs of Kelly-width 2. For an input directed graph G = (V, A) the algorithm will output a vertex ordering and a directed graph H = (V, B) with A ⊆ B witnessing either that G has Kelly-width at most 2 or that G has Kelly-width at least 3, in time linear in H. [ABSTRACT FROM AUTHOR]

In this paper we introduce semi-nice tree-decompositions and show that they combine the best of both branchwidth and treewidth. We first give simple algorithms to transform a given tree-decomposition or branch-decomposition into a semi-nice tree-decomposition. We then give two templates for dynamic programming along a semi-nice tree-decomposition, one for optimization problems over vertex subsets and another for optimization problems over edge subsets. We show that the resulting runtime will match or beat the runtimes achieved by doing dynamic programming directly on either a branch- or tree-decomposition. For example, given a graph G on n vertices with path-, tree- and branch-decompositions of width pw,tw and bw respectively, the Minimum Dominating Set problem on G is solved in time by a single dynamic programming algorithm along a semi-nice tree-decomposition. [ABSTRACT FROM AUTHOR]

Branchwidth is a connectivity parameter of graphs closely related to treewidth. Graphs of treewidth at most k can be generated algorithmically as the subgraphs of k-trees. n this paper, we investigate the family of edge-maximal graphs of branchwidth k, that we call k-branches. The k-branches are, just as the k-trees, a subclass of the chordal graphs where all minimal separators have size k. However, a striking difference arises when considering subgraph-minimal members of the family. Whereas Kk+1 is the only subgraph-minimal k-tree, we show that for any k ≥7 a minimal k-branch having q maximal cliques exists for any value of $q \not\in \{3,5\}$, except for k=8,q=2. We characterize subgraph-minimal k-branches for all values of k. Our investigation leads to a generation algorithm, that adds one or two new maximal cliques in each step, producing exactly the k-branches. [ABSTRACT FROM AUTHOR]

A survey is given of the main techniques in parameterized algorithm design, with a focus on formal descriptions of the less familiar techniques. A taxonomy of techniques is proposed, under the four main headings of Branching, Kernelization, Induction and Win/Win. In this classification the Extremal Method is viewed as the natural maximization counterpart of Iterative Compression, under the heading of Induction. The formal description given of Greedy Localization generalizes the application of this technique to a larger class of problems. [ABSTRACT FROM AUTHOR]

We provide new tools, such as k-troikas and good subtree-representations, that allow us to give fast and simple algorithms computing branchwidth. We show that a graph G has branchwidth at most k if and only if it is a subgraph of a chordal graph in which every maximal clique has a k-troika respecting its minimal separators. Moreover, if G itself is chordal with clique tree T then such a chordal supergraph exists having clique tree a minor of T. We use these tools to give a straightforward O(m+n+q2) algorithm computing branchwidth for an interval graph on m edges, n vertices and q maximal cliques. We also prove a conjecture of F. Mazoit [13] by showing that branchwidth is polynomial on a chordal graph given with a clique tree having a polynomial number of subtrees. [ABSTRACT FROM AUTHOR]

We consider three types of locally constrained graph homomorphisms: bijective, injective and surjective. We show that the three orders imposed on graphs by existence of these three types of homomorphisms are partial orders. We extend the well-known connection between degree refinement matrices of graphs and locally bijective graph homomorphisms to locally injective and locally surjective homomorphisms by showing that the orders imposed on degree refinement matrices by our locally constrained graph homomorphisms are also partial orders. We provide several equivalent characterizations of degree (refinement) matrices, e.g. in terms of the dimension of the cycle space of a graph related to the matrix. As a consequence we can efficiently check whether a given matrix M is a degree matrix of some graph and also compute the size of a smallest graph for which it is a degree matrix in polynomial time. [ABSTRACT FROM AUTHOR]

Degree refinement matrices have tight connections to graph homomorphisms that locally, on the neighborhoods of a vertex and its image, are constrained to three types: bijective, injective or surjective. If graph G has a homomorphism of given type to graph H, then we say that the degree refinement matrix of G is smaller than that of H. This way we obtain three partial orders. We present algorithms that will determine whether two matrices are comparable in these orders. For the bijective constraint no two distinct matrices are comparable. For the injective constraint we give a PSPACE algorithm, which we also apply to disprove a conjecture on the equivalence between the matrix orders and universal cover inclusion. For the surjective constraint we obtain some partial complexity results. [ABSTRACT FROM AUTHOR]

We consider the NP-complete problem of deciding whether an input graph on n vertices has k vertex-disjoint copies of a fixed graph H. For H=K3 (the triangle) we give an O(22klog k +1.869kn2) algorithm, and for general H an O(2kHlog k +2kHlog HnH) algorithm. We introduce a preprocessing (kernelization) technique based on crown decompositions of an auxiliary graph. For H=K3 this leads to a preprocessing algorithm that reduces an arbitrary input graph of the problem to a graph on O(k3) vertices in polynomial time. [ABSTRACT FROM AUTHOR]

A ρ-independent set S in a graph is parameterized by a set ρ of non-negative integers that constrains how the independent set S can dominate the remaining vertices (fV υ ∋ S: ¦N(υ) ∩ S¦ ∃ ρ.) For all values of ρ, we classify as either NP-complete or polynomial-time solvable the problems of deciding if a given graph has a ρ-independent set. We complement this with approximation algorithms and inapproximability results, for all the corresponding optimization problems. These approximation results extend also to several related independence problems. In particular, we obtain a √m approximation of the Set Packing problem, where m is the number of base elements, as well as a √n approximation of the maximum independent set in power graphs Gt, for t even. [ABSTRACT FROM AUTHOR]

This paper addresses memory requirement issues arising in implementations of algorithms on graphs of bounded treewidth. Such dynamic programming algorithms require a large data table for each vertex of a tree-decomposition T of the input graph. We give a lineartime algorithm that finds the traversal order of T minimizing the number of tables stored simultaneously. We show that this minimum value is lower-bounded by the pathwidth of T plus one, and upper bounded by twice the pathwidth of T plus one. We also give a linear-time algorithm finding the depth-first traversal order minimizing the sum of the sizes of tables stored simultaneously. [ABSTRACT FROM AUTHOR]