Parameters Tied to Treewidth

Treewidth is a graph parameter of fundamental importance to algorithmic and structural graph theory. This article surveys several graph parameters tied to treewidth, including separation number, tangle number, well‐linked number, and Cartesian tree product number. We review many results in the literature showing these parameters are tied to treewidth. In a number of cases we also improve known bounds, provide simpler proofs, and show that the inequalities presented are tight.     

Oriented bipartite graphs and the Goldbach graph

In this paper, we study oriented bipartite graphs. In particular, we introduce “bitransitive” graphs. Several characterizations of bitransitive bitournaments are obtained. We show that bitransitive bitounaments are equivalent to acyclic bitournaments. As applications, we characterize acyclic bitournaments with Hamiltonian paths, determine the number of non-isomorphic acyclic bitournaments of a given order, and solve the graph-isomorphism problem in linear time for acyclic bitournaments. Next, we prove the well-known Caccetta-Häggkvist Conjecture for oriented bipartite graphs in some cases for which it is unsolved, in general, for oriented graphs. We also introduce the concept of undirected as well as oriented “odd-even” graphs. We characterize bipartite graphs and acyclic oriented bipartite graphs in terms of them. In fact, we show that any bipartite graph (acyclic oriented bipartite graph) can be represented by some odd-even graph (oriented odd-even graph). We obtain some conditions for connectedness of odd-even graphs. This study of odd-even graphs and their connectedness is motivated by a special family of odd-even graphs which we call “Goldbach graphs”. We show that the famous Goldbach's conjecture is equivalent to the connectedness of Goldbach graphs. Several other number theoretic conjectures (e.g., the twin prime conjecture) are related to various parameters of Goldbach graphs, motivating us to study the nature of vertex-degrees and independent sets of these graphs. Finally, we observe Hamiltonian properties of some odd-even graphs related to Goldbach graphs for a small number of vertices.     

Threshold functions for small subgraphs in simple graphs and multigraphs

We revisit the problem of counting the number of copies of a fixed graph in a random graph or multigraph, for various models of random (multi)graphs. For our proofs we introduce the notion of patchworks to describe the possible overlappings of copies of subgraphs. Furthermore, the proofs are based on analytic combinatorics to carry out asymptotic computations. The flexibility of our approach allows us to tackle a wide range of problems. We obtain the asymptotic number and the limiting distribution of the number of subgraphs which are isomorphic to a graph from a given set of graphs. The results apply to multigraphs as well as to (multi)graphs with degree constraints. One application is to scale-free multigraphs, where the degree distribution follows a power law, for which we show how to obtain the asymptotic number of copies of a given subgraph and give as an illustration the expected number of small cycles.     

Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem

We study the computational complexity of the Spare Capacity Allocation problem arising in optical networks that use a shared mesh restoration scheme. In this problem we are given a network with edge capacities and point-to-point demands, and the goal is to allocate two edge-disjoint paths for each demand (a working path and a so-called restoration path, which is activated only if the working path fails) so that the capacity constraints are satisfied and the total cost of the used and reserved bandwidth is minimized. We focus on the setting where we deal with a group of demands together, and select their restoration paths simultaneously in order to minimize the total cost. We investigate how the computational complexity of this problem is affected by certain parameters, such as the number of restoration paths to be selected, or the treewidth of the network graph. To analyze the complexity of the problem, we introduce a generalization of the Steiner Forest problem that we call Multicost Steiner Subgraph. We study its parameterized complexity, and identify computationally easy and hard cases by providing hardness proofs as well as efficient (fixed-parameter tractable) algorithms.     

Generalized set-valued mixed nonlinear quasi variational inequalities

In this paper we introduce and study a number of new classes of quasi variational inequalities. Using essentially the projection technique and its variant forms we prove that the generalized set-valued mixed quasivariational inequalities are equivalent to the fixed point problem and the Wiener-Hopf equations (normal maps). This equivalence enables us to suggest a number of iterative algorithms for solving the generalized variational inequalities. As a special case of the generalized set-valued mixed quasi variational inequalities, we obtain a class of quasi variational inequalities studied by Siddiqi, Husain and Kazmi [35], but there are several inaccuracies in their formulation of the problem, the statement and the proofs of their results. We have removed these inaccuracies. The correct formulation of their results can be obtained as special cases from our main results.     

Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs

Recently much attention has been focused on the theory of quasi-random graph and hypergraph properties. The class of quasi-random graphs is defined by certain equivalent graph properties possessed by random graphs. We shall investigate propertiesP which do not imply quasi-randomnes for sequences (G _n ) of graphs on their own, but do imply if they hold not only for the whole graphG _n but also for every sufficiently large subgraph ofG _n . Here the properties are strongly connected to countingnot necessarily induced subgraphs of a given type, while in a subsequent paper we shall investigate the properties connected with counting induced subgraphs.Dedicated to the memory of Paul ErdsResearch supported by OTKA N1909.     

The tricriterion shortest path problem with at least two bottleneck objective functions

The focus of this paper is on the tricriterion shortest path problem where two objective functions are of the bottleneck type, for example MinMax or MaxMin. The third objective function may be of the same kind or we may consider, for example, MinSum or MaxProd. Let p(n) be the complexity of a classical single objective algorithm responsible for this third function, where n is the number of nodes and m be the number of arcs of the graph. An O(m²p(n)) algorithm is presented that can generate the minimal complete set of Pareto-optimal solutions. Finding the maximal complete set is also possible. Optimality proofs are given and extensions for several special cases are presented. Computational experience for a set of randomly generated problems is reported.     

Graph transformations preserving the stability number

We analyse the relations between several graph transformations that were introduced to be used in procedures determining the stability number of a graph. We show that all these transformations can be decomposed into a sequence of edge deletions and twin deletions. We also show how some of these transformations are related to the notion of even pair introduced to color some classes of perfect graphs. Then, some properties of edge deletion and twin deletion are given and a conjecture is formulated about the class of graphs for which these transformations can be used to determine the stability number.     

Equivalent time-dependent scheduling problems

We introduce a general transformation of parallel-machine time-dependent scheduling problems with critical lines. Using the transformation we define the class of equivalent time-dependent scheduling problems. We show that given an initial parallel-machine time-dependent scheduling problem with linear job processing times and the total weighted starting time criterion, the problem can be transformed in a unique way into another problem of this type in such a way that both these problems are mutually dual. We prove that a schedule is optimal for the initial problem if and only if the schedule constructed by this transformation is optimal for the transformed problem. The presented results explain remarkable similarities between different time-dependent scheduling problems and simplify the proofs of properties of such problems.     

Extensions and consequences of Chvátal-Erdős' theorem

A classical result of Chvátal and Erds states that a graph with independence number smaller or equal to its connectivity contains a Hamilton cycle. In this note we discuss some extensions of this theorem and show how they can be used to proof several other results in hamiltonian graph theory. Although several of the results are known, the proofs in this note are in general essentially shorter than the original proofs, and also give an indication of the relations between the results.Supported by a grant from the Natural Sciences and Engineering Research Council of Canada     

Density theorems for bipartite graphs and related Ramsey-type results

In this paper, we present several density-type theorems which show how to find a copy of a sparse bipartite graph in a graph of positive density. Our results imply several new bounds for classical problems in graph Ramsey theory and improve and generalize earlier results of various researchers. The proofs combine probabilistic arguments with some combinatorial ideas. In addition, these techniques can be used to study properties of graphs with a forbidden induced subgraph, edge intersection patterns in topological graphs, and to obtain several other Ramsey-type statements. Research supported by an NSF Graduate Research Fellowship and a Princeton Centennial Fellowship. Research supported in part by NSF CAREER award DMS-0812005 and by USA-Israeli BSF grant.     

Efficient Testing of Large Graphs

Let P be a property of graphs. An e\epsilon -test for P is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph G with n vertices are adjacent or not, distinguishes, with high probability, between the case of G satisfying P and the case that it has to be modified by adding and removing more than en²\epsilon n^2 edges to make it satisfy P. The property P is called testable, if for every e\epsilon there exists an e\epsilon -test for P whose total number of queries is independent of the size of the input graph. Goldreich, Goldwasser and Ron [8] showed that certain individual graph properties, like k-colorability, admit an e\epsilon -test. In this paper we make a first step towards a complete logical characterization of all testable graph properties, and show that properties describable by a very general type of coloring problem are testable. We use this theorem to prove that first order graph properties not containing a quantifier alternation of type ``"$\forall \exists ' are always testable, while we show that some properties containing this alternation are not.     

Graph with given achromatic number

An irreducible (point-determining) graph is one in which distinct vertices have distinct neighbourhoods. Every graph X can be reduced to an irreducible graph X¹ by identifying all vertices with the same neighbourhood; the colourability properties of X¹ carry over to X. Hence irreducible graphs are instrumental in the study of achromatic number. We prove that there are only finitely many irreducible graphs with a given achromatic number, and describe all graphs with achromatic number less than four. We deduce certain bounds on the achromatic number X in terms of the number of vertices of X¹. In the course of the proofs we calculate the achromatic numbers of paths and cycles. Generalizations of the main theorem to homomorphisms other than colourings are discussed.     

Some provably hard crossing number problems

This paper presents a connection between the problem of drawing a graph with the minimum number of edge crossings, and the theory of arrangements of pseudolines, a topic well-studied by combinatorialists. In particular, we show that any given arrangement can be forced to occur in every minimum crossing drawing of an appropriate graph. Using some recent results of Goodman, Pollack, and Sturmfels, this yields that there exists no polynomial-time algorithm for producing a straight-line drawing of a graph, which achieves the minimum number of crossings from among all such drawings. While this result has no bearing on the P versus NP question, it is fairly negative with regard to applications. We also study the problem of drawing a graph with polygonal edges, to achieve the (unrestricted) minimum number of crossings. Here we obtain a tight bound on the smallest number of breakpoints which are required in the polygonal lines. This work was partially supported by the Center for Telecommunications Research, Columbia University.     

Lower bounds on the pathwidth of some grid-like graphs

We present proofs of lower bounds on the node search number of some grid-like graphs including two-dimensional grids, cylinders, tori and a variation we call “orb-webs”. Node search number is equivalent to pathwidth and vertex separation, which are all important graph parameters. Since matching upper bounds are not difficult to obtain, this implies that the pathwidth of these graphs is easily computed, because the bounds are simple functions of the graph dimensions. We also show matching upper and lower bounds on the node search number of equidimensional tori which are one less than the obvious upper bound.     

Classification of interpolation theorems for spanning trees and other families of spanning subgraphs

We say that a graphical invariant i of a graph interpolates over a family F of graphs if i satisfies the following property: If m and M are the minimum and maximum values (respectively) of i over all graphs in F then for each k, m ? k ? M, there is a graph H in F for which i(H)= k. In previous works it was shown that when F is the set of spanning trees of a connected graph G, a large number of invariants interpolate (some of these invariants require the additional assumption that G be 2-connected). Although the proofs of all these results use the same basic idea of gradually transforming one tree into another via a sequence of edge exchanges, some of these processes require sequences that use more properties of trees than do others. We show that the edge exchange proofs can be divided into three types, in accordance with the extent to which the exchange sequence depends upon properties of spanning trees. This idea is then used to obtain new interpolation results for some invariants, and to show how the exchange methods and interpolation results on spanning trees can be extended to other families of spanning subgraphs.     

Using Laplacian Eigenvalues and Eigenvectors in the Analysis of Frequency Assignment Problems

A Frequency Assignment Problem (FAP) is the problem that arises when frequencies have to be assigned to a given set of transmitters so that spectrum is used efficiently and the interference between the transmitters is minimal. In this paper we see the frequency assignment problem as a generalised graph colouring problem, where transmitters are presented by vertices and interaction between two transmitters by a weighted edge. We generalise some properties of Laplacian matrices that hold for simple graphs. We investigate the use of Laplacian eigenvalues and eigenvectors as tools in the analysis of properties of a FAP and its generalised chromatic number (the so-called span).     

Girth and Euclidean distortion

Let G be a k-regular graph, , with girth g. We prove that every embedding has distortion . Two proofs are given, one based on Markov type [B] and the other on quadratic programming. In the core of both proofs are some Poincaré-type inequalities on graph metrics. Submitted: July 2001, Revised: September 2001.     

On the Hardness of Approximating the Chromatic Number

k -colorable for some fixed . Our main result is that it is NP-hard to find a 4-coloring of a 3-chromatic graph. As an immediate corollary we obtain that it is NP-hard to color a k-chromatic graph with at most colors. We also give simple proofs of two results of Lund and Yannakakis [20]. The first result shows that it is NP-hard to approximate the chromatic number to within for some fixed ε > 0. We point here that this hardness result applies only to graphs with large chromatic numbers. The second result shows that for any positive constant h, there exists an integer , such that it is NP-hard to decide whether a given graph G is -chromatic or any coloring of G requires colors. Received April 11, 1997/Revised June 10, 1999     

The inverse problem for certain tree parameters

Let p be a graph parameter that assigns a positive integer value to every graph. The inverse problem for p asks for a graph within a prescribed class (here, we will only be concerned with trees), given the value of p. In this context, it is of interest to know whether such a graph can be found for all or at least almost all integer values of p. We will provide a very general setting for this type of problem over the set of all trees, describe some simple examples and finally consider the interesting parameter “number of subtrees”, where the problem can be reduced to some number-theoretic considerations. Specifically, we will prove that every positive integer, with only 34 exceptions, is the number of subtrees of some tree.