|
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
|
