Search

We present hardness results, approximation heuristics, and exact algorithms for bottleneck labeled optimization problems arising in the context of graph theory. This long-established model partitions the set of edges into classes, each of which is identified by a unique color. The generic objective is to construct a subgraph of prescribed structure (such as that of being an s-t path, a spanning tree, or a perfect matching) while trying to avoid over-picking or under-picking edges from any given color. [ABSTRACT FROM AUTHOR]

The computation of all minimal transversals of a given hypergraph in output-polynomial time is a long standing open question known as the transversal hypergraph generation. One of the first attempts on this problem—the sequential method [Ber89]—is not output-polynomial as was shown by Takata [Tak02]. Recently, three new algorithms improving the sequential method were published and experimentally shown to perform very well in practice [BMR03, DL05, KS05]. Nevertheless, a theoretical worst-case analysis has been pending. We close this gap by proving lower bounds for all three algorithms. Thereby, we show that none of them is output-polynomial. [ABSTRACT FROM AUTHOR]

In the Planar + kvertex problem the task is to find at most k vertices whose deletion makes the given graph planar. The graphs for which there exists a solution form a minor closed class of graphs, hence by the deep results of Robertson and Seymour [19,18], there is an O(n3) time algorithm for every fixed value of k. However, the proof is extremely complicated and the constants hidden by the big-O notation are huge. Here we give a much simpler algorithm for this problem with quadratic running time, by iteratively reducing the input graph and then applying techniques for graphs of bounded treewidth. [ABSTRACT FROM AUTHOR]

We show that the mixed search number and the linear-width of interval graphs and of split graphs can be computed in linear time and in polynomial time, respectively. [ABSTRACT FROM AUTHOR]

We prove new structural properties for tree-decompositions of planar graphs that we use to improve upon the runtime of tree-decomposition based dynamic programming approaches for several NP-hard planar graph problems. We give for example the fastest algorithm for Planar Dominating Set of runtime 3tw ·nO(1), when we take the treewidth tw as the measure for the exponential worst case behavior. We also introduce a tree-decomposition based approach to solve non-local problems efficiently, such as Planar Hamiltonian Cycle in runtime 6tw ·nO(1). From any input tree-decomposition, we compute in time O(nm) a tree-decomposition with geometric properties, which decomposes the plane into disks, and where the graph separators form Jordan curves in the plane. [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]

The pathwidth of a graph G is the minimum clique number of H minus one, over all interval supergraphs H of G. Although pathwidth is a well-known and well-studied graph parameter, there are extremely few graph classes for which pathwidh is known to be tractable in polynomial time. We give in this paper an $\mathcal{O}(n^2)$-time algorithm computing the pathwidth of circular-arc graphs. [ABSTRACT FROM AUTHOR]

A circular-arc model $ {\mathcal {M}} =(C,\mathcal{A})$ is a circle C together with a collection $\mathcal{A}$ of arcs of C. If no arc is contained in any other then $\mathcal{M}$ is a proper circular-arc model, if every arc has the same length then $\mathcal{M}$ is a unit circular-arc model and if $\mathcal{A}$ satisfies the Helly Property then $\mathcal{M}$ is a Helly circular-arc model. A (proper) (unit) (Helly) circular-arc graph is the intersection graph of the arcs of a (proper) (Helly) circular-arc model. Circular-arc graphs and their subclasses have been the object of a great deal of attention in the literature. Linear time recognition algorithms have been described both for the general class and for some of its subclasses. In this article we study the circular-arc graphs which admit a model which is simultaneously proper and Helly. We describe characterizations for this class, including one by forbidden induced subgraphs. These characterizations lead to linear time certifying algorithms for recognizing such graphs. Furthermore, we extend the results to graphs which admit a model which is simultaneously unit and Helly, also leading to characterizations and a linear time certifying algorithm. [ABSTRACT FROM AUTHOR]

Polygon-circle graphs (PC-graphs) are defined as intersection graphs of polygons inscribed into a circle, graphs of interval filaments (IFA-graphs) are intersection graphs of curves with both endpoints on prescribed line (filament), filaments above two disjoint intervals must not intersect each other. Recognition of these classes has been a long outstanding open problem. We prove that it is NP-complete to recognize both classes. [ABSTRACT FROM AUTHOR]

Cographs are those graphs without induced path on four vertices. A graph G is a probe cograph if its vertex set can be partitioned into two sets, N (non-probes) and P (probes) where N is independent and G can be extended to a cograph by adding edges between certain non-probes. A partitioned probe cograph is a probe cograph with a given partition in N and P. We characterise probe cographs in several ways. Moreover, we characterise partitioned probe cographs in terms of five forbidden induced subgraphs. Using the forbidden induced subgraph characterisation, we give a linear-time recognition algorithm for probe cographs, improving the recent quadratic-time recognition algorithm by Chandler et al. Our algorithm is a modification of the linear-time recognition algorithm for cographs by Corneil et al. [ABSTRACT FROM AUTHOR]

We divide a string into k segments, each with only one sort of symbols, so as to minimize the total number of exceptions. Motivations come from machine learning and data mining. For binary strings we develop a linear-time algorithm for any k. Key to efficiency is a special-purpose data structure, called W-tree, which reflects relations between repetition lengths of symbols. Existence of algorithms faster than obvious dynamic programming remains open for non-binary strings. Our problem is also equivalent to finding weighted independent sets of prescribed size in paths. We show that this problem in bounded-degree graphs is FPT. [ABSTRACT FROM AUTHOR]

We study a variation of the vertex cover problem where it is required that the graph induced by the vertex cover is connected. We prove that this problem is polynomial in chordal graphs, has a PTAS in planar graphs, is APX-hard in bipartite graphs and is 5/3-approximable in any class of graphs where the vertex cover problem is polynomial (in particular in bipartite graphs). [ABSTRACT FROM AUTHOR]

We deal with the asymptotic enumeration of combinatorial structures on planar maps. Prominent instances of such problems are the enumeration of spanning trees, bipartite perfect matchings, and ice models. The notion of an α-orientation unifies many different combinatorial structures, including the afore mentioned. We ask for the number of α-orientations and also for special instances thereof, such as Schnyder woods and bipolar orientations. The main focus of this paper are bounds for the maximum number of such structures that a planar map with n vertices can have. We give examples of triangulations with 2.37n Schnyder woods, 3-connected planar maps with 3.209n Schnyder woods and inner triangulations with 2.91n bipolar orientations. These lower bounds are accompanied by upper bounds of 3.56n, 8n, and 3.97n, respectively. We also show that for any planar map M and any α the number of α-orientations is bounded from above by 3.73n and we present a family of maps which have at least 2.598nα-orientations for n big enough. [ABSTRACT FROM AUTHOR]

A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. An L-cycle cover is a cycle cover in which the length of every cycle is in the set L ⊆ ℕ. We investigate how well L-cycle covers of minimum weight can be approximated. For undirected graphs, we devise a polynomial-time approximation algorithm that achieves a constant approximation ratio for all sets L. On the other hand, we prove that the problem cannot be approximated within a factor of 2 − ε for certain sets L. For directed graphs, we present a polynomial-time approximation algorithm that achieves an approximation ratio of O(n), where n is the number of vertices. This is asymptotically optimal: We show that the problem cannot be approximated within a factor of o(n). To contrast the results for cycle covers of minimum weight, we show that the problem of computing L-cycle covers of maximum weight can, at least in principle, be approximated arbitrarily well. [ABSTRACT FROM AUTHOR]

For a 3-colourable graph G, the 3-colour graph of G, denoted $\mathcal{C}_3(G)$, is the graph with node set the proper vertex 3-colourings of G, and two nodes adjacent whenever the corresponding colourings differ on precisely one vertex of G. We consider the following question : given G, how easily can we decide whether or not $\mathcal{C}_3(G)$ is connected? We show that the 3-colour graph of a 3-chromatic graph is never connected, and characterise the bipartite graphs for which $\mathcal{C}_3(G)$ is connected. We also show that the problem of deciding the connectedness of the 3-colour graph of a bipartite graph is coNP-complete, but that restricted to planar bipartite graphs, the question is answerable in polynomial time. [ABSTRACT FROM AUTHOR]

We study the competitive ratio of certain online algorithms for a well-studied class of load balancing problems. These algorithms are obtained and analyzed according to a method by Crescenzi et al (2004). We show that an exact analysis of their competitive ratio on certain "uniform" instances would resolve a fundamental conjecture by Caccetta and Häggkvist (1978). The conjecture is that any digraph on n nodes and minimum outdegree d must contain a directed cycle involving at most ⌈n/d ⌉ nodes. Our results are the first relating this conjecture to the competitive analysis of certain algorithms, thus suggesting a new approach to the conjecture itself. We also prove that, on "uniform" instances, the analysis by Crescenzi et al (2004) gives only trivial upper bounds, unless we find a counterexample to the conjecture. This is in contrast with other (notable) examples where the same analysis yields optimal (non-trivial) bounds. [ABSTRACT FROM AUTHOR]

A linear-time algorithm that does not need a planar embedding is presented for the problem of computing two vertex-disjoint paths, each with prescribed endpoints, in an undirected 3-connected planar graph. [ABSTRACT FROM AUTHOR]

It has been shown in [9] that there exist planar digraphs that require exponential area in every upward straight-line planar drawing. On the other hand, upward poly-line planar drawings of planar graphs can be realized in Θ(n2) area [9]. In this paper we consider families of DAGs that naturally arise in practice, like DAGs whose underlying graph is a tree (directed trees), is a bipartite graph (directed bipartite graphs), or is an outerplanar graph (directed outerplanar graphs). Concerning directed trees, we show that optimal Θ(n logn) area upward straight-line/poly-line planar drawings can be constructed. However, we prove that if the order of the neighbors of each node is assigned, then exponential area is required for straight-line upward drawings and quadratic area is required for poly-line upward drawings, results surprisingly and sharply contrasting with the area bounds for planar upward drawings of undirected trees. After having established tight bounds on the area requirements of planar upward drawings of several families of directed trees, we show how the results obtained for trees can be exploited to determine asymptotic optimal values for the area occupation of planar upward drawings of directed bipartite graphs and directed outerplanar graphs. [ABSTRACT FROM AUTHOR]

Modularity is a recently introduced quality measure for graph clusterings. It has immediately received considerable attention in several disciplines, and in particular in the complex systems literature, although its properties are not well understood. We study the problem of finding clusterings with maximum modularity, thus providing theoretical foundations for past and present work based on this measure. More precisely, we prove the conjectured hardness of maximizing modularity both in the general case and with the restriction to cuts, and give an Integer Linear Programming formulation. This is complemented by first insights into the behavior and performance of the commonly applied greedy agglomaration approach. [ABSTRACT FROM AUTHOR]

For a graph G and a positive integer k, the k-power of G is the graph Gk with V(G) as its vertex set and {(u,v) u, v ∈ V(G), dG(u, v) ≤ k} as its edge set where dG(u,v) is the distance between u and v in graph G. The k-Steiner root problem on a graph G asks for a tree T with V(G) ⊆ V(T) and G is the subgraph of Tk induced by V(G). If such a tree T exists, we call it a k-Steiner root of G. This paper gives a linear time algorithm for the 3-Steiner root problem. Consider an unrooted tree T with leaves one-to-one labeled by the elements of a set V. The k-leaf power of T is a graph, denoted $T_{L}^{k}$, with $T_{L}^{k} = (V, E)$, where E = {(u,v) u, v ∈ V and dT(u,v) ≤ k}. We call T a k-leaf root of $T_{L}^{k}$. The k-leaf power recognition problem is to decide whether a graph has such a k-leaf root. The complexity of this problem is still open for k ≥ 5 [6]. It can be solved in polynomial time if the (k − 2)-Steiner root problem can be solved in polynomial time [6]. Our result implies that the k-leaf power recognition problem can be solved in linear time for k = 5. [ABSTRACT FROM AUTHOR]

A minimal triangulation of a graph is a chordal graph obtained from adding an inclusion-minimal set of edges to the graph. For permutation graphs, i.e., graphs that are both comparability and cocomparability graphs, it is known that minimal triangulations are interval graphs. We (negatively) answer the question whether every interval graph is a minimal triangulation of a permutation graph. We give a non-trivial characterisation of the class of interval graphs that are minimal triangulations of permutation graphs and obtain as a surprising result that only "a few" interval graphs are minimal triangulations of permutation graphs. [ABSTRACT FROM AUTHOR]

NLC-width is a variant of clique-width with many application in graph algorithmic. This paper is devoted to graphs of NLC-width two. After giving new structural properties of the class, we propose a O(n2m)-time algorithm, improving Johansson's algorithm [14]. Moreover, our alogrithm is simple to understand. The above properties and algorithm allow us to propose a robust O(n2m)-time isomorphism algorithm for NLC-2 graphs. As far as we know, it is the first polynomial-time algorithm. [ABSTRACT FROM AUTHOR]

The k-power graph of a graph G is the graph in which two vertices are adjacent if and only if there is a path between them in G of length at most k. We show that (1.) the k-power graph of a tree has NLC-width at most k + 2 and clique-width at most $k+2+\max(\lfloor \frac{k}{2}\rfloor -1,0)$, (2.) the k-leaf-power graph of a tree has NLC-width at most k and clique-width at most $k+ \max(\lfloor \frac{k}{2}\rfloor -2,0)$, and (3.) the k-power graph of a graph of tree-width l has NLC-width at most (k + 1)l + 1− 1 and clique-width at most 2·(k + 1)l + 1− 2. [ABSTRACT FROM AUTHOR]

Graph complexity measures like tree-width, clique-width, NLC-width and rank-width are important because they yield Fixed Parameter Tractable algorithms. Rank-width is based on ranks of adjacency matrices of graphs over GF(2). We propose here algebraic operations on graphs that characterize rank-width. For algorithmic purposes, it is important to represent graphs by balanced terms. We give a unique theorem that generalizes several "balancing theorems" for tree-width and clique-width. New results are obtained for rank-width and a variant of clique-width, called m-clique-width. [ABSTRACT FROM AUTHOR]

The class of 2-interval graphs has been introduced for modelling scheduling and allocation problems, and more recently for specific bioinformatics problems. Some of those applications imply restrictions on the 2-interval graphs, and justify the introduction of a hierarchy of subclasses of 2-interval graphs that generalize line graphs: balanced 2-interval graphs, unit 2-interval graphs, and (x,x)-interval graphs. We provide instances that show that all inclusions are strict. We extend the NP-completeness proof of recognizing 2-interval graphs to the recognition of balanced 2-interval graphs. Finally we give hints on the complexity of unit 2-interval graphs recognition, by studying relationships with other graph classes: proper circular-arc, quasi-line graphs, K1,5-free graphs... [ABSTRACT FROM AUTHOR]

It is well known that boundedness of tree-width implies polynomial-time solvability of many algorithmic graph problems. The converse statement is generally not true, i.e., polynomial-time solvability does not necessarily imply boundedness of tree-width. However, in graphs of bounded vertex degree, for some problems, the two concepts behave in a more consistent way. In the present paper, we study this phenomenon with respect to three important graph problems - dominating set, independent dominating set and induced matching - and obtain several results toward revealing the equivalency between boundedness of the tree-width and polynomial-time solvability of these problems in bounded degree graphs. [ABSTRACT FROM AUTHOR]

In graph searching, a team of searchers is aiming at capturing a fugitive moving in a graph. In the initial variant, called invisible graph searching, the searchers do not know the position of the fugitive until they catch it. In another variant, the searchers know the position of the fugitive, i.e. the fugitive is visible. This latter variant is called visible graph searching. A search strategy that catches any fugitive in such a way that, the part of the graph reachable by the fugitive never grows is called monotone. A priori, monotone strategies may require more searchers than general strategies to catch any fugitive. This is however not the case for visible and invisible graph searching. Two important consequences of the monotonicity of visible and invisible graph searching are: (1) the decision problem corresponding to the computation of the smallest number of searchers required to clear a graph is in NP, and (2) computing optimal search strategies is simplified by taking into account that there exist some that never backtrack. Fomin et al. (2005) introduced an important graph searching variant, called non-deterministic graph searching, that unifies visible and invisible graph searching. In this variant, the fugitive is invisible, and the searchers can query an oracle that knows the current position of the fugitive. The question of the monotonicity of non-deterministic graph searching is however left open. In this paper, we prove that non-deterministic graph searching is monotone. In particular, this result is a unified proof of monotonicity for visible and invisible graph searching. As a consequence, the decision problem corresponding to non-determinisitic graph searching belongs to NP. Moreover, the exact algorithms designed by Fomin et al. do compute optimal non-deterministic search strategies. [ABSTRACT FROM AUTHOR]

We define helicopter cop and robber games with multiple robbers, extending previous research, which only considered the pursuit of a single robber. Our model is defined for robbers that are visible (the cops know their position) and active (able to move at every turn) but is easily adapted to other common variants of the game. The game with many robbers is non-monotone: more cops are needed if their moves are restricted so as to monotonically decrease the space available to the robbers. Because the cops may decide their moves based on the robbers' current position, strategies in the game are interactive but the game becomes, in a sense, less interactive as the initial number of robbers increases. We prove that the main parameter emerging from the game captures a hierarchy of parameters between proper pathwidth and proper treewidth. We give a complete characterization of the parameter for trees and an upper bound for general graphs. [ABSTRACT FROM AUTHOR]

A graph G = (V,E) is a tolerance graph if each vertex v ∈ V can be associated with an interval of the real line Iv and a positive real number tv in such a way that (uv) ∈ E if and only if Iv ∩ Iu ≥ min (tv,tu). No algorithm for recognizing tolerance graphs in general is known. In this paper we present an O(n + m) algorithm for recognizing tolerance graphs that are also bipartite, where n and m are the number vertices and edges of the graph, respectively. We also give a new structural characterization of these graphs based on the algorithm. [ABSTRACT FROM AUTHOR]

The so called (σ,ρ)-domination, introduced by J.A. Telle, is a concept which provides a unifying generalization for many variants of domination in graphs. (A set S of vertices of a graph G is called (σ,ρ)-dominating if for every vertex v ∈ S, S ∩ N(v) ∈ σ, and for every v ∉ S, S ∩ N(v) ∈ ρ, where σ and ρ are sets of nonnegative integers and N(v) denotes the open neighborhood of the vertex v in G.) It was known that for any two nonempty finite sets σ and ρ (such that 0 ∉ ρ), the decision problem whether an input graph contains a (σ,ρ)-dominating set is NP-complete, but that when restricted to chordal graphs, some polynomial time solvable instances occur. We show that for chordal graphs, the problem performs a complete dichotomy: it is polynomial time solvable if σ, ρ are such that every chordal graph contains at most one (σ,ρ)-dominating set, and NP-complete otherwise. The proof involves certain flavor of existentionality - we are not able to characterize such pairs (σ,ρ) by a structural description, but at least we can provide a recursive algorithm for their recognition. If ρ contains the 0 element, every graph contains a (σ,ρ)-dominating set (the empty one), and so the nontrivial question here is to ask for a maximum such set. We show that MAX-(σ,ρ)-domination problem is NP-complete for chordal graphs whenever ρ contains, besides 0, at least one more integer. [ABSTRACT FROM AUTHOR]

We say that, for k ≥ 2 and ℓ> k, a tree T is a (k,ℓ)-leaf root of a graph G = (VG,EG) if VG is the set of leaves of T, for all edges xy ∈ EG, the distance dT(x,y) in T is at most k and, for all non-edges $xy \not\in E_G$, dT(x,y) is at least ℓ. A graph G is a (k,ℓ)-leaf power if it has a (k,ℓ)-leaf root. This new notion modifies the concept of k-leaf power which was introduced and studied by Nishimura, Ragde and Thilikos motivated by the search for underlying phylogenetic trees. Recently, a lot of work has been done on k-leaf powers and roots as well as on their variants phylogenetic roots and Steiner roots. For k = 3 and k = 4, structural characterisations and linear time recognition algorithms of k-leaf powers are known, and, recently, a polynomial time recognition of 5-leaf powers was given. For larger k, the recognition problem is open. We give structural characterisations of (k,ℓ)-leaf powers, for some k and ℓ, which also imply an efficient recognition of these classes, and in this way we also improve and extend a recent paper by Kennedy, Lin and Yan on strictly chordal graphs and leaf powers. [ABSTRACT FROM AUTHOR]

Motivated by the frequency assignment problem in heterogeneous multihop radio networks, where different radio stations may have different transmission ranges, we introduce two new types of coloring of graphs, which generalize the well-known Distance-k-Coloring. Let G=(V,E) be a graph modeling a radio network, and assume that each vertex v of G has its own transmission radius r(v), a non-negative integer. We define r-coloring (r+-coloring) of G as an assignment Φ: V↦{0,1,2,...} of colors to vertices such that Φ(u)=Φ(v) implies dG(u,v)>r(v)+r(u) (dG(u,v)>r(v)+r(u)+1, respectively). The r-Coloring problem (the r+-Coloring problem) asks for a given graph G and a radius-function r: V↦N∪{0}, to find an r-coloring (an r+-coloring, respectively) of G with minimum number of colors. Using a new notion of generalized powers of graphs, we investigate the complexity of the r-Coloring and r+-Coloring problems on several families of graphs. [ABSTRACT FROM AUTHOR]

Clique separators in graphs are a helpful tool used by Tarjan as a divide-and-conquer approach for solving various graph problems such as the Maximum Weight Stable Set (MWS) Problem, Coloring and Minimum Fill-in but few examples are known where this approach was used. We combine decomposition by clique separators and by homogeneous sets and show that the resulting binary tree gives an efficient way for solving the MWS problem. Moreover, we combine this approach with the concept of nearly chordal and nearly perfect and obtain some new graph classes where MWS is solvable in polynomial time by our approach. On some of these classes, the unweighted Maximum Stable Set (MS) Problem was known to be solvable in polynomial time by the struction method or by augmenting techniques, respectively, but the complexity of the MWS problem was open. A graph is nearly chordal if for each of its vertices, the subgraph induced by the set of its nonneighbors is chordal, and analogously for nearly perfect graphs. [ABSTRACT FROM AUTHOR]

Graph decompositions such as decomposition by clique separators and modular decomposition are of crucial importance for designing efficient graph algorithms. Clique separators in graphs were used by Tarjan as a divide-and-conquer approach for solving various problems such as the Maximum Weight Stable Set (MWS) Problem, Coloring and Minimum Fill-in. The basic tool is a decomposition tree of the graph whose leaves have no clique separator (so-called atoms), and the problem can be solved efficiently on the graph if it is efficiently solvable on its atoms. We give new examples where the clique separator decomposition works well for the MWS problem which also improves and extends various recently published results. In particular, we describe the atom structure for some new classes of graphs whose atoms are P5-free (the P5 is the induced path with 5 vertices) and obtain new polynomial time results for MWS. [ABSTRACT FROM AUTHOR]

Clique-width of graphs is a major new concept with respect to efficiency of graph algorithms. The notion of clique-width extends the one of treewidth, since bounded treewidth implies bounded clique-width. We give a complete classification of all graph classes defined by forbidden induced subgraphs of at most four vertices with respect to bounded or unbounded clique-width. [ABSTRACT FROM AUTHOR]

In this paper we describe together with an overview about other results the main ideas of our polynomial time approximation schemes for the maximum weight independent set problem (selecting a set of disjoint disks in the plane of maximum total weight) in disk graphs and for the maximum bisection problem (finding a partition of the vertex set into two subsets of equal cardinality with maximum number of edges between the subsets) in unit-disk graphs. [ABSTRACT FROM AUTHOR]