Geometric separation and exact solutions for the parameterized independent set problem on disk graphs

We consider the parameterized problem, whether for a given set  of n disks (of bounded radius ratio) in the Euclidean plane there exists a set of k non-intersecting disks. For this problem, we expose an algorithm running in time that is—to our knowledge—the first algorithm with running time bounded by an exponential with a sublinear exponent. For λ-precision disk graphs of bounded radius ratio, we show that the problem is fixed parameter tractable with a running time  . The results are based on problem kernelization and a new “geometric ( -separator) theorem” which holds for all disk graphs of bounded radius ratio. The presented algorithm then performs, in a first step, a “geometric problem kernelization” and, in a second step, uses divide-and-conquer based on our new “geometric separator theorem.”     

A PTAS for minimum <Emphasis Type="Italic">d</Emphasis>-hop connected dominating set in growth-bounded graphs

In this paper, we design the first polynomial time approximation scheme for d-hop connected dominating set (d-CDS) problem in growth-bounded graphs, which is a general type of graphs including unit disk graph, unit ball graph, etc. Such graphs can represent majority types of existing wireless networks. Our algorithm does not need geometric representation (e.g., specifying the positions of each node in the plane) beforehand. The main strategy is clustering partition. We select the d-CDS for each subset separately, union them together, and then connect the induced graph of this set. We also provide detailed performance and complexity analysis.     

Fast Enumeration Algorithms for Non-crossing Geometric Graphs

A non-crossing geometric graph is a graph embedded on a set of points in the plane with non-crossing straight line segments. In this paper we present a general framework for enumerating non-crossing geometric graphs on a given point set. Applying our idea to specific enumeration problems, we obtain faster algorithms for enumerating plane straight-line graphs, non-crossing spanning connected graphs, non-crossing spanning trees, and non-crossing minimally rigid graphs. Our idea also produces efficient enumeration algorithms for other graph classes, for which no algorithm has been reported so far, such as non-crossing matchings, non-crossing red-and-blue matchings, non-crossing k-vertex or k-edge connected graphs, or non-crossing directed spanning trees. The proposed idea is relatively simple and potentially applies to various other problems of non-crossing geometric graphs.     

Restricted unimodular chordal graphs

A chordal graph is called restricted unimodular if each cycle of its vertex‐clique incidence bipartite graph has length divisible by 4. We characterize these graphs within all chordal graphs by forbidden induced subgraphs, by minimal relative separators, and in other ways. We show how to construct them by starting from block graphs and multiplying vertices subject to a certain restriction, which leads to a linear‐time recognition algorithm. We show how they are related to other classes such as distance‐hereditary chordal graphs and strongly chordal graphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 121–136, 1999     

On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs

Clique-Helly and hereditary clique-Helly graphs are polynomial-time recognizable. Recently, we presented a proof that the clique graph recognition problem is NP-complete [L. Alcón, L. Faria, C.M.H. de Figueiredo, M. Gutierrez, Clique graph recognition is NP-complete, in: Proc. WG 2006, in: Lecture Notes in Comput. Sci., vol. 4271, Springer, 2006, pp. 269-277]. In this work, we consider the decision problems: given a graph G=(V,E) and an integer k≥0, we ask whether there exists a subset V^′⊆V with |V^′|≥k such that the induced subgraph G[V^′] of G is, variously, a clique, clique-Helly or hereditary clique-Helly graph. The first problem is clearly NP-complete, from the above reference; we prove that the other two decision problems mentioned are NP-complete, even for maximum degree 6 planar graphs. We consider the corresponding maximization problems of finding a maximum induced subgraph that is, respectively, clique, clique-Helly or hereditary clique-Helly. We show that these problems are Max SNP-hard, even for maximum degree 6 graphs. We show a general polynomial-time -approximation algorithm for these problems when restricted to graphs with fixed maximum degree Δ. We generalize these results to other graph classes. We exhibit a polynomial 6-approximation algorithm to minimize the number of vertices to be removed in order to obtain a hereditary clique-Helly subgraph.     

Optimally super-edge-connected transitive graphs

Let X=(V,E) be a connected regular graph. X is said to be super-edge-connected if every minimum edge cut of X is a set of edges incident with some vertex. The restricted edge connectivity λ′(X) of X is the minimum number of edges whose removal disconnects X into non-trivial components. A super-edge-connected k-regular graph is said to be optimally super-edge-connected if its restricted edge connectivity attains the maximum 2k−2. In this paper, we define the λ′-atoms of graphs with respect to restricted edge connectivity and show that if X is a k-regular k-edge-connected graph whose λ′-atoms have size at least 3, then any two distinct λ′-atoms are disjoint. Using this property, we characterize the super-edge-connected or optimally super-edge-connected transitive graphs and Cayley graphs. In particular, we classify the optimally super-edge-connected quasiminimal Cayley graphs and Cayley graphs of diameter 2. As a consequence, we show that almost all Cayley graphs are optimally super-edge-connected.     

On orthogonal ray graphs

An orthogonal ray graph is an intersection graph of horizontal and vertical rays (half-lines) in the xy-plane. An orthogonal ray graph is a 2-directional orthogonal ray graph if all the horizontal rays extend in the positive x-direction and all the vertical rays extend in the positive y-direction. We first show that the class of orthogonal ray graphs is a proper subset of the class of unit grid intersection graphs. We next provide several characterizations of 2-directional orthogonal ray graphs. Our first characterization is based on forbidden submatrices. A characterization in terms of a vertex ordering follows immediately. Next, we show that 2-directional orthogonal ray graphs are exactly those bipartite graphs whose complements are circular arc graphs. This characterization implies polynomial-time recognition and isomorphism algorithms for 2-directional orthogonal ray graphs. It also leads to a characterization of 2-directional orthogonal ray graphs by a list of forbidden induced subgraphs. We also show a characterization of 2-directional orthogonal ray trees, which implies a linear-time algorithm to recognize such trees. Our results settle an open question of deciding whether a (0,1)-matrix can be permuted to avoid the submatrices .     

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

We study complexity and approximation of min weighted node coloring in planar, bipartite and split graphs. We show that this problem is NP-hard in planar graphs, even if they are triangle-free and their maximum degree is bounded above by 4. Then, we prove that min weighted node coloring is NP-hard in P₈-free bipartite graphs, but polynomial for P₅-free bipartite graphs. We next focus on approximability in general bipartite graphs and improve earlier approximation results by giving approximation ratios matching inapproximability bounds. We next deal with min weighted edge coloring in bipartite graphs. We show that this problem remains strongly NP-hard, even in the case where the input graph is both cubic and planar. Furthermore, we provide an inapproximability bound of 7/6−ε, for any ε>0 and we give an approximation algorithm with the same ratio. Finally, we show that min weighted node coloring in split graphs can be solved by a polynomial time approximation scheme.     

On minimal forbidden subgraph characterizations of balanced graphs

A graph is balanced if its clique-matrix contains no edge–vertex incidence matrix of an odd chordless cycle as a submatrix. While a forbidden induced subgraph characterization of balanced graphs is known, there is no such characterization by minimal forbidden induced subgraphs. In this work, we provide minimal forbidden induced subgraph characterizations of balanced graphs restricted to graphs that belong to one of the following graph classes: complements of bipartite graphs, line graphs of multigraphs, and complements of line graphs of multigraphs. These characterizations lead to linear-time recognition algorithms for balanced graphs within the same three graph classes.     

Mathematical programming models for some smallest-world problems

Given a weighted graph G, in the minimum-cost-edge-selection problem (MCES), a minimum weighted set of edges is chosen subject to an upper bound on the diameter of graph G. Similarly, in the minimum-diameter-edge-selection problem (MDES), a set of edges is chosen to minimize the diameter subject to an upper bound on their total weight. These problems are shown to be equivalent and proven to be NP-complete. MCES is then formulated as a 0–1 integer programming problem. The problems MCES and MDES provide models for determining smallest-world networks and for measuring the “small-worldness” of graphs.     

Rooted directed path graphs are leaf powers

Leaf powers are a graph class which has been introduced to model the problem of reconstructing phylogenetic trees. A graph G=(V,E) is called k-leaf power if it admits a k-leaf root, i.e., a tree T with leaves V such that uv is an edge in G if and only if the distance between u and v in T is at most k. Moroever, a graph is simply called leaf power if it is a k-leaf power for some k∈N. This paper characterizes leaf powers in terms of their relation to several other known graph classes. It also addresses the problem of deciding whether a given graph is a k-leaf power.We show that the class of leaf powers coincides with fixed tolerance NeST graphs, a well-known graph class with absolutely different motivations. After this, we provide the largest currently known proper subclass of leaf powers, i.e, the class of rooted directed path graphs.Subsequently, we study the leaf rank problem, the algorithmic challenge of determining the minimum k for which a given graph is a k-leaf power. Firstly, we give a lower bound on the leaf rank of a graph in terms of the complexity of its separators. Secondly, we use this measure to show that the leaf rank is unbounded on both the class of ptolemaic and the class of unit interval graphs. Finally, we provide efficient algorithms to compute 2|V|-leaf roots for given ptolemaic or (unit) interval graphs G=(V,E).     

A (2 + )-Approximation Scheme for Minimum Domination on Circle Graphs

The main result of this paper is a (2 + )-approximation scheme for the minimum dominating set problem on circle graphs. We first present an O(n²) time 8-approximation algorithm for this problem and then extend it to an time (2 + )-approximation scheme for this problem. Here n and m are the number of vertices and the number of edges of the circle graph. We then present simple modifications to this algorithm that yield (3 + )-approximation schemes for the minimum connected and the minimum total dominating set problems on circle graphs. Keil (1993, Discrete Appl. Math.42, 51–63) shows that these problems are NP-complete for circle graphs and leaves open the problem of devising approximation algorithms for them. These are the first O(1)-approximation algorithms for domination problems on circle graphs.     

Parameterized complexity of even/odd subgraph problems

We study the parameterized complexity of the problems of determining whether a graph contains a k-edge subgraph (k-vertex induced subgraph) that is a Π-graph for Π-graphs being one of the following four classes of graphs: Eulerian graphs, even graphs, odd graphs, and connected odd graphs. We also consider the parameterized complexity of their parametric dual problems.For these sixteen problems, we show that eight of them are fixed parameter tractable and four are W[1]-hard. Our main techniques are the color-coding method of Alon, Yuster and Zwick, and the random separation method of Cai, Chan and Chan.     

On the interval completion of chordal graphs

For a given graph G=(V,E), the interval completion problem of G is to find an edge set F such that the supergraph H=(V,E∪F) of G is an interval graph and |F| is minimum. It has been shown that it is equivalent to the minimum sum cut problem, the profile minimization problem and a kind of graph searching problems. Furthermore, it has applications in computational biology, archaeology, and clone fingerprinting. In this paper, we show that it is NP-complete on split graphs and propose an efficient algorithm on primitive starlike graphs.     

Vertex splitting and the recognition of trapezoid graphs

Trapezoid graphs are the intersection family of trapezoids where every trapezoid has a pair of opposite sides lying on two parallel lines. These graphs have received considerable attention and lie strictly between permutation graphs (where the trapezoids are lines) and cocomparability graphs (the complement has a transitive orientation). The operation of “vertex splitting”, introduced in (Cheah and Corneil, 1996) [3], first augments a given graph G and then transforms the augmented graph by replacing each of the original graph’s vertices by a pair of new vertices. This “splitted graph” is a permutation graph with special properties if and only if G is a trapezoid graph. Recently vertex splitting has been used to show that the recognition problems for both tolerance and bounded tolerance graphs is NP-complete (Mertzios et al., 2010) [11]. Unfortunately, the vertex splitting trapezoid graph recognition algorithm presented in (Cheah and Corneil, 1996) [3] is not correct. In this paper, we present a new way of augmenting the given graph and using vertex splitting such that the resulting algorithm is simpler and faster than the one reported in (Cheah and Corneil, 1996) [3].     

Graph theoretic approach to parallel gene assembly

We study parallel complexity of signed graphs motivated by the highly complex genetic recombination processes in ciliates. The molecular gene assembly operations have been modeled by operations of signed graphs, i.e., graphs where the vertices have a sign + or −. In the optimization problem for signed graphs one wishes to find the parallel complexity by which the graphs can be reduced to the empty graph. We relate parallel complexity to matchings in graphs for some natural graph classes, especially bipartite graphs. It is shown, for instance, that a bipartite graph G has parallel complexity one if and only if G has a unique perfect matching. We also formulate some open problems of this research topic.     

Learning marginal AMP chain graphs under faithfulness revisited

Marginal AMP chain graphs are a recently introduced family of models that is based on graphs that may have undirected, directed and bidirected edges. They unify and generalize the AMP and the multivariate regression interpretations of chain graphs. In this paper, we present a constraint based algorithm for learning a marginal AMP chain graph from a probability distribution which is faithful to it. We show that the marginal AMP chain graph returned by our algorithm is a distinguished member of its Markov equivalence class. We also show that our algorithm performs well in practice. Finally, we show that the extension of Meek's conjecture to marginal AMP chain graphs does not hold, which compromises the development of efficient and correct score+search learning algorithms under assumptions weaker than faithfulness.     

Solving the path cover problem on circular-arc graphs by using an approximation algorithm

A path cover of a graph G=(V,E) is a family of vertex-disjoint paths that covers all vertices in V. Given a graph G, the path cover problem is to find a path cover of minimum cardinality. This paper presents a simple O(n)-time approximation algorithm for the path cover problem on circular-arc graphs given a set of n arcs with endpoints sorted. The cardinality of the path cover found by the approximation algorithm is at most one more than the optimal one. By using the result, we reduce the path cover problem on circular-arc graphs to the Hamiltonian cycle and Hamiltonian path problems on the same class of graphs in O(n) time. Hence the complexity of the path cover problem on circular-arc graphs is the same as those of the Hamiltonian cycle and Hamiltonian path problems on circular-arc graphs.     

Gray Code Enumeration of Plane Straight-Line Graphs

We develop Gray code enumeration schemes for geometric straight-line graphs in the plane. The considered graph classes include plane graphs, connected plane graphs, and plane spanning trees. Previous results were restricted to the case where the underlying vertex set is in convex position. Research supported by the FWF Joint Research Project Industrial Geometry S9205-N12 and Projects MCYT-FEDER BFM2003-00368 and Gen. Cat 2005SGR00692.     

Efficient Algorithms for Variants of Weighted Matching and Assignment Problems

Obtaining a matching in a graph satisfying a certain objective is an important class of graph problems. Matching algorithms have received attention for several decades. However, while there are efficient algorithms to obtain a maximum weight matching, not much is known about the maximum weight maximum cardinality, and maximum cardinality maximum weight matching problems for general graphs. Our contribution in this work is to show that for bounded weight input graphs one can obtain an algorithm for both maximum weight maximum cardinality (for real weights), and maximum cardinality maximum weight matching (for integer weights) by modifying the input and running the existing maximum weight matching algorithm. Also, given the current state of the art in maximum weight matching algorithms, we show that, for bounded weight input graphs, both maximum weight maximum cardinality, and maximum cardinality maximum weight matching have algorithms of similar complexities to that of maximum weight matching. Subsequently, we also obtain approximation algorithms for maximum weight maximum cardinality, and maximum cardinality maximum weight matching.