GENERAL SCIENTIFIC ACTIVITY

October  5, 2022
THE FIELDS INSTITUTE FOR RESEARCH IN MATHEMATICAL SCIENCES

May 5-6, 2014
Workshop on
Graphs and Algorithms
In honour of Derek Corneil's contributions to graph theory and computer science

Fields Institute, 222 College Street, Toronto
(Mapto Fields)

Back to main index

Invited speakers

Feodor Dragan --Kent State University
Following Derek's footsteps (slides)

I will give a short review of the results of my collaboration with Derek and discuss a few recent results that were obtained by following Derek's footsteps.

Ekki Koehler --Brandenburg University of Technology
AT-free Graphs and their linear structure

Graphs without asteroidal triples have been studied extensively in the last 20 years. Their close relationship to interval graphs and cocomparability graphs suggested a whole variety of properties of these graphs that are especially helpful for finding fast algorithms for hard problems when restricted to AT-free graphs.
One main feature of interval graphs and cocomparability graphs is the linear structure that is induced by the underlying partial order of their complement graphs. For asteroidal triple free graphs this linear structure has been pointed out by different authors using different arguments. Still it is not really clear for these graphs what this linear structure looks like and how one could prove their existence.
In this talk we will try once more to capture the linear structure of AT-free graphs. For this we will look at the different notions of linearity for this graph family that have been studied before and we will try to put them in a new perspective by studying them using the knotting graph, a very helpful auxiliary graph structure that has been introduced by Gallai a long time ago for characterizing comparability graphs. As this knotting graph is defined in the complement graph, we look at AT-free graphs from the complementary side of the world, or in other words, we look at properties of coAT-free graphs.

Michel Habib --Université Paris Diderot - Paris 7
On some new practical applications of graph searches

When the size of the graph (or network) you study is huge, (i.e. so big that no exact algorithms having a quadratic complexity can be applied in the biggest computer you have access to), then you are forced to use or invent new linear time heuristics or linear time approximation algorithms.
So when dealing with huge graphs even for polynomial problems it is worth to consider linear time processing.
Graph search is a very efficient tool to deal with huge graphs : easy to implement, and no need to store the whole graph in memory. At each step only the adjacency list of the current vertex is needed. Furthermore using a series of dependant consecutive graph searches may help to find some of the structure of a given graph.
I will explain in full details our results on computing centers and diameter of huge graphs, using very few successive Breadth First Searches (BFS). I will try to explain why our experimental results are so good. Such an approach could be extended to the computation of other graph parameters such as delta-hyperbolicity, betweenness or some other centrality parameters.
For example "smoothing" the graph in order to find an approximate modular decomposition.
I will describe new results and some research directions in this area. Also for max flow problems several polynomial time algorithms are known, but no linear time approximation algorithms is known yet. This could be a good challenge to apply graph search to this goal.

Mike Molloy-- University of Toronto
Algorithms for random k-SAT and colouring random graphs. (slides)

Random instances of k-SAT have long been recognized as being very challenging to solve algorithmically. Random graphs are also very difficult to colour. A series of hypotheses arising from statistical physics provides much insight into why these problems are so challenging. These hypotheses also give rise to some algorithms which, in practice, perform remarkably well on random instances of k-SAT and on k-colouring random graphs for small values of k. The most notable such algorithm is Survey Propagation, a variation of belief propagation.
This talk will provide an overview of these algorithms, including intuition as to why they seem to perform well and hypotheses regarding their performance for large values of k. We will also discuss what has been proven and what we hope to prove.

Contributed talks (speaker abstracts)

Therese Biedl, University of Waterloo
Carving-width, tree-width, and area-optimal planar graph drawing (slides)

In this talk, I will survey results about some graph parameters, and how they relate to the area required for planar drawings of graphs. Specifically, I will sketch why minimizing the area is NP-hard even for graphs of bounded treewidth or pathwidth, but becomes polynomial for graphs of bounded carving width. For convex planar drawings, having bounded treewidth is already enough to find the planar drawing of minimum area.

Andreas Brandstaedt, University of Rostock
(joint work with Anne Berry and Konrad Engel)
On the Dilworth Number of Auto-Chordal Bipartite Graphs (.pdf abstract)

The mirror (or bipartite complement) $mir(B)$ of a bipartite graph $B=(X,Y,E)$ has the same color classes $X$ and $Y$ as $B$, and two vertices $x \in X$ and $y \in Y$ are adjacent in $mir(B)$ if and only if $xy \notin E$. A bipartite graph is chordal bipartite if none of its induced subgraphs is a chordless cycle with at least six vertices. In this paper, we deal with chordal bipartite graphs whose mirror is chordal bipartite as well; we call these graphs auto-chordal bipartite graphs (ACB graphs for short). We describe the relationship to some known graph classes such as interval and strongly chordal graphs and we present several characterizations of ACB graphs. We show that ACB graphs have unbounded Dilworth number, and we characterize ACB graphs with Dilworth number $k$.

Jason Brown, Dalhousie University
$G$-Convexity of Graphs

A convexity on a finite set $V$ is a collection of subsets of $V$ containing the empty set, and the whole set $V$, and is closed under intersection; this forms a natural combinatorial generalization of convexity in euclidean space. Now let $G$ be a graph of order $n$. A subset $C$ of vertices of G is $g$-convex if for every pair $u,v\in C$ the vertices on every $u$--$v$ geodesic (i.e. shortest $u$--$v$ path) belong to $C$. The set of $g$-convex subsets of a graph are an interesting subfamily of alignments. In this talk we will discuss three aspects of $g$-convexity: the structure of $g$-minimal graphs (those that have the minimal number of g-convex sets), the complexity of counting $g$-convex sets in a graph, and when there exists $g$-convex sets of all cardinalities from $0$ to $n$. (This research is joint with O.Oellermann.)

Leizhen Cai, Chinese University of Hong Kong
Dually connected subgraphs and dual separators in edge bicoloured graphs

Let G be an edge-bicoloured graph where each edge is coloured either red or blue. We discuss problems of obtaining a subgraph H from G that simultaneously satisfies specified properties for H's red graph and blue graph. In particular, we consider Dually-Connected Induced Subgraph problem (find from G a k-vertex induced subgraph whose red and blue graphs are both connected) and Dual Separator problem (delete at most k vertices to simultaneously disconnect red and blue graphs of G).
Despite an extensive work on edge-coloured graphs in the literature, there is hardly any attention on this type of problems for edge-coloured graphs. We will discuss various algorithmic and complexity issues for Dually-Connected Induced Subgraph and Dual Separator problems: NP-hardness, polynomial-time algorithms, W[1]-hardness, and FPT algorithms. We will also give a complete characterization of the complexity, both traditional and parameterized, of the problem of obtaining a k-vertex induced subgraph H from G that simultaneously satisfies given hereditary properties for H's red and blue graphs.
Joint work with Junjie Ye.

Kathie Cameron, Wilfrid Laurier University
Finding an Easily Recognizable Strong Stable Set

A stable set in a graph G is a set of vertices, no two of which are joined by an edge. A stable set in G is called strong if it contains a vertex of every maximal clique of G. A Meyniel obstruction is an odd cycle with at least five vertices and with at most one chord. Given a graph G and a vertex v of G, we give a polytime algorithm to find either a strong stable set containing v, or a Meyniel obstruction in G. In fact, we find a special kind of strong stable set which is easily recognizable (that is, in NP). Our algorithm can be used to find in any graph, a clique and colouring of the same size or a Meyniel obstruction. This is joint work with Jack Edmonds.

Charles Colbourn, Arizona State University
Permutation covers (slides)

Let $n,t$ be positive integers with $n \geq t \geq 3$. A set ${\mathcal P}$ of permutations of $X=\{1,\dots,n\}$ is a {\sl permutation cover} of {\sl strength} $t$ if, for every $t$-subset $T$ of $X$ and for every ordering of the elements of $T$, at least one permutation in ${\mathcal P}$ contains the elements of $T$ in the specified order. The goal is to minimize the number of permutations given $n$ and $t$. After a brief outline of a motivation in event sequence testing and a summary of what is known, we outline a local optimization method for reducing the number of permutations in a permutation cover.

Bhaskar DasGupta, University of Illinois Chicago
On the Complexity of Modularity Clustering

An extremely popular model-based graph partitioning approach that is used for both biological and social networks is the so-called modularity optimization approach originally proposed by Newman and its variations. In this talk, I will review several combinatorial and algebraic methods that have been used in the literature to study the computational complexities of these optimization problems.

Andreas Feldmann, University of Waterloo
Steiner-Star-Free Graphs and Equivalence Between Steiner Tree Relaxations (slides)

The bottleneck of the currently best known approximation algorithms for the NP-hard Steiner tree problem is the solution of its large, so called hypergraphic, linear programming relaxation (HYP). Hypergraphic LPs are NP-hard to solve exactly, and it is a formidable computational task to even approximate them sufficiently well.
We focus on another well-studied but poorly understood LP relaxation of the problem: the bidirected cut relaxation (BCR). This LP is compact, and can therefore be solved efficiently. Its integrality gap is known to be greater than 1.161, and while this is widely conjectured to be close to the real answer, only a (trivial) upper bound of 2 is known.
We give an efficient constructive proof that BCR and HYP are polyhedrally equivalent in instances that do not have an (edge-induced) claw on Steiner vertices; i.e., instances that do not contain a Steiner vertex with 3 Steiner neighbours. This is a significant step forward from the previously known equivalence for (so called quasi-bipartite) instances in which Steiner vertices form an independent set. We complement our results by showing that even restricting to instances where Steiner vertices induce one single star, determining whether the two relaxations are equivalent is NP-hard.

Celina de Figueiredo, Federal University of Rio de Janeiro
The generalized split probe problem (slides)

A graph $G=(V,E)$ is $\mathcal{C}$ probe if $V$ can be partitioned into two sets, probes $P$ and non-probes $N$, such that $N$ is independent and new edges may be added between non-probes such that the resulting graph is in the graph class $\mathcal{C}$. In this case, we say that $(N,P)$ is a $\mathcal{C}$ probe partition for $G$. The $\mathcal{C}$ UNPARTITIONED PROBE problem consists of an input graph $G$ and the question: Is $G$ a $\mathcal{C}$ probe graph? The $\mathcal{C}$ PARTITIONED PROBE problem consists of an input with a graph $G$ and a vertex partition $(N,P)$, and the question: Is $(N,P)$ a $\mathcal{C}$ probe partition for $G$? Given a graph $G=(V,E)$, a $(k,\ell)$ partition for $G$ is a vertex set partition of $V$ into at most $k$ independent sets and $\ell$ cliques. The graph $G=(V,E)$ belongs to the $(k,\ell)$ class if $G$ admits a $(k,\ell)$ partition. We consider the complexity dichotomy into NP-complete and Polynomial for $(k,\ell)$ UNPARTITIONED PROBE problems.

Alexander 'Sasha' Gutfraind, University of Illinois Chicago
Multiscale approach for modeling graph topology (slides)

In the talk I will introduce a flexible strategy for modeling networks using ideas inspired by multigrid methods. The strategy, termed MUSKETEER, is to start from a known network dataset, perform a series of mappings that repeatedly coarsen and later repeatedly uncoarsen the network, while applying perturbations to create diversity. Using examples from several domains, I will show that MUSKETEER can generate diverse ensembles of networks, including their edge and node labels. Statistical analysis shows that MUSKETEER also achieves greater realism than most network modeling strategies.

Chinh Hoang, Wilfrid Laurier University
Colouring and Recognizing Claw-Free Graphs Without Even Holes

An even hole is an induced even cycle. Even-hole-free graphs generalize chordal graphs. We prove that claw-free even-hole-free graphs can be decomposed by clique cutsets into, essentially, proper circular-arc graphs. This provides the basis for our algorithms for recognizing and colouring these graphs. Our recognition algorithm is
more efficient than known algorithms for recognizing even-hole-free graphs. Minimum colouring of claw-free graphs is NP-hard and the complexity of colouring even-hole-free graphs is unknown, but our algorithm colours claw-free even-hole-free graphs in O(n^3) time. This is joint work with K. Cameron and S. Chaplick.

Mark Keil , University of Saskatchewan
A Polynomial time Algorithm for the Maximum Weight Independent Set Problem on Outerstring Graphs
(.pdf of abstract)

Anna Lubiw, University of Waterloo
Visibility Graphs, Dismatlability, and the Cops-and-Robbers Game (slides)

Visibility graphs of polygons are not known to be related to other graph classes, except for special cases, e.g. visibility graphs of spiral polygons are interval graphs (Everett and Corneil, 1990). We show that visibility graphs of polygons are dismantlable, a property that is defined in terms of a vertex ordering similar to perfect elimination ordering of chordal graphs. A consequence is that the cop can always win the cops and robbers game in a polygon. In this game one point (the cop) and one point (the robber) take turns moving in a straight line from one vertex to another inside a polygon, and the cop wins when it reaches the robber. We extend this to the cops and robbers game on all points inside a polygon, and discuss the relationship to pursuit-evasion in polygonal regions. Joint work with Hamideh Vosoughpour.

Jim Nastos, UBC Okanagan
Graph classes in social network analysis and algorithms

We present a collection of results which apply classical graph classes to social network analysis. In particular, we show that quasi-threshold graphs arise naturally when investigating the network structure of social community and organization. By also using cographs and $P_4$-sparse graphs, our line of research also lead to new algorithmic, complexity, and structural results for clustering-related problems.

Vivek Nittoor, University of Tokyo
New Results On the Cage Problem for Even Girth (.pdf of abstract)

Guillem Perarnau, McGill University
Spanning F-free subgraphs of regular graphs with large minimum degree
Authors: G. Perarnau and Bruce Reed (McGill University)

Let F be a family of fixed graphs and let d be large enough. For every d-regular graph G, we study the existence of a spanning F-free subgraph of G with large minimum degree. This problem is well-understood if F does not contain bipartite graphs. Here we provide asymptotically tight results for many families of bipartite graphs such as cycles or complete bipartite graphs.

Gara Pruesse, Vancouver Island University
Lexicographic Labellings achieve fast algorithms for bump number, cocomp hamiltonicity, and two-processor scheduling
(slides)

In 1972, Coffman and Graham introduced a clever technique for finding a makespan-optimal schedule of uniform jobs on two identical processors (the 2PS problem). Other, much more complicated methods were later developed to solve the 2PS problem, and it was these more ungainly solutions that were made to work in linear time through the application of a special case of the Union-Find algorithm, adding significantly to the elaborateness of the algorithm. The resulting methods were themselves used as inspiration for solving the bump number problem on posets, adding yet another layer of programming complexity while apparently maintaining the linear time computational complexity. The bump number of a linear extension of a poset is the number of occurrences of adjacent elements in the ordering that are comparable in the poset; the bump number of the poset is the least bump number of any linear extension.
Recent work in Min Path Cover for cocomparability graphs has led back to the poset equivalent, and insights from work on this important graph class have led the authors to a new bump number algorithm that is simple, efficient, and has an elegant proof of correctness; furthermore, it provides the natural "bump number" descendent of the 2PS algorithms of Coffman and Graham. These may be the "book" algorithm, and the "book" proof for the bump number problem, which have lain undiscovered for decades due to an asymptotically optimally efficient (yet very complicated) algorithm being known. The new proof and theorems offer insight into cocomparability graph algorithms, and may lead to optimally efficient algorithms for bump number that are simpler than known efficient algorithms.

(Joint work with Derek Corneil and Lalla Mouatadid, Computer Science, University of Toronto)

Jeremy Spinrad, Vanderbilt University
A New Generalization of Semi-orders

A semi-order is a type of graph used to model preference relations. Each element x is assigned a weight w(x), and there is a fixed threshold t; x is less than y if w(x)+t is less than w(y).
This talk discusses a natural generalization, in which there are two thresholds t1 and t2 rather than 1 threshold. If w(x) and w(y) differ by at most t1, there is no edge between x and y; if w(x) is less than w(y) by at least t2, then x is definitely less than y, while if w(x) is less than w(y) by a value between t1 and t2, x may be less than y or there may be no relationship between x and y.
The talk will discuss both applications and mathematical properties of this model, for various possible ratios of t2/t1.

Lorna Stewart, University of Alberta
List colouring and list homomorphism of permutation and interval graphs
Authors: Jessica Enright, Lorna Stewart, and Gabor Tardos

We give a polynomial-time algorithm for solving the list colouring problem on permutation graphs with a bounded total number of colours. More generally, we give a polynomial-time algorithm that solves the list homomorphism problem to any fixed target graph for a class of input graphs that contains all permutation and interval graphs.

Yaokun Wu, Shanghai Jiao Tong University
Hamiltonian thickness and fault-tolerant spanning rooted path systems of graphs

Li and Wu introduced the Hamiltonian thickness parameter of a graph in [1]. On the condition that the Hamiltonian thickness of a graph $G$ is not too small, Wu, Xiang and Zhu [2] propose a simple algorithm to generate various spanning path systems with given endpoint constraints in the graph obtained from $G$ by deleting an arbitrary subset of vertices and edges of small size. This talk aims to explain the concept of Hamiltonian thickness, illustrate the above-mentioned algorithm and its application in constructing sparse fault-tolerant graphs with various spanning rooted path systems and, if time permitted, also present some problems.
References:
[1] Peng Li, Yaokun Wu, Spanning connectedness and Hamiltonian thickness of graphs and interval graphs, available at http://math.sjtu.edu.cn/faculty/ykwu/data/Paper/DMTCS14.pdf
[2] Yaokun Wu, Ziqing Xiang, Yinfeng Zhu, Hamiltonian thickness and fault-tolerant spanning rooted path systems of graphs, in preparation.

Bing Zhou, Trent University
Adaptable coloring and color critical graphs (slides)

A graph G is adaptably k-colourable if for every k-edge colouring c', there is a k-vertex colouring c such that for every edge xy in G, not all of c(x), c(y), and c'(xy) are the same. The adaptable chromatic number of a graph G is the smallest integer k such that G is adaptably k-colourble. In this talk, we discuss the upper and lower bound of the adaptable chromatic number of a graph G in relation to its chromatic number. We also present a construction of colour critical graphs whose adaptable chromatic number is one less than its chromatic number. This answers a question raised by Molloy and Thron.

 

Top