Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation

We generalize the linear-time shortest-paths algorithm for planar graphs with nonnegative edge-weights of Henzinger et al. (1994) to work for any proper minor-closed class of graphs. We argue that their algorithm can not be adapted by standard methods to all proper minor-closed classes. By using recent deep results in graph minor theory, we show how to construct an appropriate recursive division in linear time for any graph excluding a fixed minor and how to transform the graph and its division afterwards, so that it has maximum degree three. Based on such a division, the original framework of Henzinger et al. can be applied. Afterwards, we show that using this algorithm, one can implement Mehlhorn’s (1988) 2-approximation algorithm for the Steiner tree problem in linear time on these graph classes.     

t-Pebbling and Extensions

Graph pebbling is the study of moving discrete pebbles from certain initial distributions on the vertices of a graph to various target distributions via pebbling moves. A pebbling move removes two pebbles from a vertex and places one pebble on one of its neighbors (losing the other as a toll). For t ≥ 1 the t-pebbling number of a graph is the minimum number of pebbles necessary so that from any initial distribution of them it is possible to move t pebbles to any vertex. We provide the best possible upper bound on the t-pebbling number of a diameter two graph, proving a conjecture of Curtis et al., in the process. We also give a linear time (in the number of edges) algorithm to t-pebble such graphs, as well as a quartic time (in the number of vertices) algorithm to compute the pebbling number of such graphs, improving the best known result of Bekmetjev and Cusack. Furthermore, we show that, for complete graphs, cycles, trees, and cubes, we can allow the target to be any distribution of t pebbles without increasing the corresponding t-pebbling numbers; we conjecture that this behavior holds for all graphs. Finally, we explore fractional and optimal fractional versions of pebbling, proving the fractional pebbling number conjecture of Hurlbert and using linear optimization to reveal results on the optimal fractional pebbling number of vertex-transitive graphs.     

Minimum Color Sum of Bipartite Graphs

The problem ofminimum color sumof a graph is to color the vertices of the graph such that the sum (average) of all assigned colors is minimum. Recently it was shown that in general graphs this problem cannot be approximated withinn^{1 − ε}, for any ε > 0, unlessNP = ZPP(Bar-Noyet al., Information and Computation140(1998), 183–202). In the same paper, a 9/8-approximation algorithm was presented for bipartite graphs. The hardness question for this problem on bipartite graphs was left open. In this paper we show that the minimum color sum problem for bipartite graphs admits no polynomial approximation scheme, unlessP = NP. The proof is byL-reducing the problem of finding the maximum independent set in a graph whose maximum degree is four to this problem. This result indicates clearly that the minimum color sum problem is much harder than the traditional coloring problem, which is trivially solvable in bipartite graphs. As for the approximation ratio, we make a further step toward finding the precise threshold. We present a polynomial 10/9-approximation algorithm. Our algorithm uses a flow procedure in addition to the maximum independent set procedure used in previous solutions.     

外平面图的弱完备染色

假设G=（V,E,F）是一个平面图。如果e₁和e₂是G中两条相邻边且在关联的面的边界上连续出现,那么称e₁和e₂面相邻。图G的一个弱完备k-染色是指存在一个从V ∪ E ∪ F到k色集合{1, …, K}的映射,使得任意两个相邻点,两个相邻面,两条面相邻的边,以及V ∪ E ∪ F中任意两个相关联的元素都染不同的颜色。若图G有一个弱完备k-染色,则称G是弱完备k-可染的。平面图G的弱完备色数是指G是弱完备k-可染的正整数k的最小值,记成χ_vef（G）。2016年,Fabrici等人猜想：每个无环且无割边的连通平面图是弱完备7-可染的。证明外平面图满足猜想,即外平面图是弱完备7-可染的。     

Linear flows and Morse graphs: Topological consequences in low dimensions

The main aim of this paper is to show some specific connections between linear dynamic and graphs. Precisely, the Morse decomposition of a linear flow on the Grassmannians induces a directed graph. We apply the results appearing in Ayala et al. (2006, 2005)  and  and Colonius et al. (2002) [4] and compute the associated graphs for linear flows in dimensions two and three.     

A forbidden subgraph characterization of line-polar bipartite graphs

A graph is polar if the vertex set can be partitioned into A and B in such a way that the subgraph induced by A is a complete multipartite graph and the subgraph induced by B is a disjoint union of cliques. Polar graphs are a common generalization of bipartite, cobipartite, and split graphs. However, recognizing polar graphs is an NP-complete problem in general. This led to the study of the polarity of special classes of graphs such as cographs and chordal graphs, cf. Ekim et al. (2008) [7] and [5]. In this paper, we study the polarity of line graphs and call a graph line-polar if its line graph is polar. We characterize line-polar bipartite graphs in terms of forbidden subgraphs. This answers a question raised in the fist reference mentioned above. Our characterization has already been used to develop a linear time algorithm for recognizing line-polar bipartite graphs, cf. Ekim (submitted for publication) [6].     

Polarity of chordal graphs

Polar graphs are a common generalization of bipartite, cobipartite, and split graphs. They are defined by the existence of a certain partition of vertices, which is NP-complete to decide for general graphs. It has been recently proved that for cographs, the existence of such a partition can be characterized by finitely many forbidden subgraphs, and hence tested in polynomial time. In this paper we address the question of polarity of chordal graphs, arguing that this is in essence a question of colourability, and hence chordal graphs are a natural restriction. We observe that there is no finite forbidden subgraph characterization of polarity in chordal graphs; nevertheless we present a polynomial time algorithm for polarity of chordal graphs. We focus on a special case of polarity (called monopolarity) which turns out to be the central concept for our algorithms. For the case of monopolar graphs, we illustrate the structure of all minimal obstructions; it turns out that they can all be described by a certain graph grammar, permitting our monopolarity algorithm to be cast as a certifying algorithm.     

Toughness, hamiltonicity and split graphs

Related to Chvátal's famous conjecture stating that every 2-tough graph is hamiltonian, we study the relation of toughness and hamiltonicity on special classes of graphs.

First, we consider properties of graph classes related to hamiltonicity, traceability and toughness concepts and display some algorithmic consequences. Furthermore, we present a polynomial time algorithm deciding whether the toughness of a given split graph is less than one and show that deciding whether the toughness of a bipartite graph is exactly one is coNP-complete.

We show that every split graph is hamiltonian and that there is a sequence of non-hamiltonian split graphs with toughness converging to .     

A Planar linear arboricity conjecture

The linear arboricity la(G) of a graph G is the minimum number of linear forests (graphs where every connected component is a path) that partition the edges of G. In 1984, Akiyama et al. [Math Slovaca 30 (1980), 405–417] stated the Linear Arboricity Conjecture (LAC) that the linear arboricity of any simple graph of maximum degree Δ is either ?Δ/2? or ?(Δ + 1)/2?. In [J. L. Wu, J Graph Theory 31 (1999), 129–134; J. L. Wu and Y. W. Wu, J Graph Theory 58(3) (2008), 210–220], it was proven that LAC holds for all planar graphs. LAC implies that for Δ odd, la(G) = ?Δ/2?. We conjecture that for planar graphs, this equality is true also for any even Δ?6. In this article we show that it is true for any even Δ?10, leaving open only the cases Δ = 6, 8. We present also an O(n logn) algorithm for partitioning a planar graph into max{la(G), 5} linear forests, which is optimal when Δ?9. © 2010 Wiley Periodicals, Inc. J Graph Theory     

An implicit representation of chordal comparability graphs in linear time

Ma and Spinrad have shown that every transitive orientation of a chordal comparability graph is the intersection of four linear orders. That is, chordal comparability graphs are comparability graphs of posets of dimension four. Among other uses, this gives an implicit representation of a chordal comparability graph using O(n) integers so that, given two vertices, it can be determined in O(1) time whether they are adjacent, no matter how dense the graph is. We give a linear time algorithm for finding the four linear orders, improving on their bound of O(n²).     

Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs

We investigate the complexity of several domination problems on the complements of bounded tolerance graphs and the complements of trapezoid graphs. We describe an O(n² log⁵ n) time and O(n²) space algorithm to solve the domination problem on the complement of a bounded tolerance graph, given a square embedding of that graph. We also prove that domination, connected domination and total domination are all NP-complete on co-trapezoid graphs.     

Treelike comparability graphs

An undirected graph is a treelike comparability graph if it admits a transitive orientation such that its transitive reduction is a tree. We show that treelike comparability graphs are distance hereditary. Utilizing this property, we give a linear time recognition algorithm. We then characterize permutation graphs that are treelike. Finally, we consider the Partitioning into Bounded Cliques problem on special subgraphs of treelike permutation graphs.     

Planar segment visibility graphs

Given a set of n disjoint line segments in the plane, the segment visibility graph is the graph whose 2n vertices correspond to the endpoints of the line segments and whose edges connect every pair of vertices whose corresponding endpoints can see each other. In this paper we characterize and provide a polynomial time recognition algorithm for planar segment visibility graphs. Actually, we characterize segment visibility graphs that do not contain the complete graph K₅ as a minor, and show that this class is the same as the class of planar segment visibility graphs. We use and prove the fact that every segment visibility graph contains K₄ as a subgraph. In fact, we prove a stronger result: every set of n line segments determines at least n−3 empty convex quadrilaterals.     

Minimum edge ranking spanning trees of split graphs

Given a graph G, the minimum edge ranking spanning tree problem (MERST) is to find a spanning tree of G whose edge ranking is minimum. However, this problem is known to be NP-hard for general graphs. In this paper, we show that the problem MERST has a polynomial time algorithm for split graphs, which have useful applications in practice. The result is also significant in the sense that this is a first non-trivial graph class for which the problem MERST is found to be polynomially solvable. We also show that the problem MERST for threshold graphs can be solved in linear time, where threshold graphs are known to be split.     

Four classes of perfectly orderable graphs

A graph is called “perfectly orderable” if its vertices can be ordered in such a way that, for each induced subgraph F, a certain “greedy” coloring heuristic delivers an optimal coloring of F. No polynomial-time algorithm to recognize these graphs is known. We present four classes of perfectly orderable graphs: Welsh–Powell perfect graphs, Matula perfect graphs, graphs of Dilworth number at most three, and unions of two threshold graphs. Graphs in each of the first three classes are recognizable in a polynomial time. In every graph that belongs to one of the first two classes, we can find a largest clique and an optimal coloring in a linear time.     

A mathematical programming viewpoint for solving the ultimate pit problem

In 1965 Helmut Lerchs and Ingo Grossmann presented to the mining community an algorithm to find the optimum design for an open pit mine. In their words, “the objective is to design the contour of a pit so as to maximize the difference between total mine value of the ore extracted and the total extraction cost of ore and waste”. They modeled the problem in graph theoretic terms and showed that an optimal solution of the ultimate pit problem is equivalent to finding the maximum closure of their graph based model. In this paper, we develop a network flow algorithm based on the dual to solve the same problem. We show how this algorithm is closely related to Lerchs and Grossmann's and how the steps in their algorithm can be viewed in mathematical programming terms. This analysis adds insight to the algorithm of Lerchs and Grossmann and shows where it can be made more efficient. As in the case Lerchs and Grossmann, our algorithm allows us to use very efficient data structures based on graphs that represent the data and constraints.. 1782 1528 V 3     

A Faster Katz Status Score Algorithm

A new graph theoretical algorithm to calculate Katz status scores reduces computational complexity from time O(n ³) to O(n + m). Randomly-generated graphs as well as data from a large empiric study are used to test the performance of two commercial network analysis packages (GRADAP and UCINET V), compared to the performance achieved by the authors' algorithm, implemented in Visual Basic.     

Paralleling of computational processes with loops and branchings

A model of a computational process with loops and branchings, viz., a bilogic graph, is studied. An algorithm for partitioning a bilogic graph into a sequence of linear segments is described. A class of graphs is distinguished, for which the set of all staticodynamic schedules coincides with the set of schedules for the sequence of linear segments.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdelenlya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 90, pp. 210–226, 1979     

Computation of the center and diameter of outerplanar graphs

The center of a graph is the set of vertices with minimum eccentricity. An outerplanar graph is a planar segmentation of a polygon. We define a notion of edge eccentricities for the edges of an outerplanar graph. We present an algorithm which efficiently computes these edge eccentricities. Knowledge of the edge eccentricities allows subsequent linear time computation of the center and diameter of outerplanar graphs. The computation of edge eccentricities is shown to require linear time for certain subclasses of outerplanar graphs.     

An algorithm to recognize a middle graph

A graph F is called middle if there exists a graph G such that there is a one-to-one correspondence between the vertices of F and the vertices and edges of G such that two vertices of F are adjacent if and only if the corresponding elements (considered as subsets of the set of vertices) have a non-empty intersection.In this paper we present a linear time algorithm for the recognition of the middle graphs. The algorithm is based on a computer-oriented characterization of middle graphs. We show also how the algorithm can be generalized to recognize the middle graphs of hypergraphs.