Seminars in November 2016

  • Paul Wollan, Solving the half-integral disjoint paths problem in highly connected digraphs
    Solving the half-integral disjoint paths problem in highly connected digraphs
    Paul Wollan
    Department of Computer Science, University of Rome, Rome, Italy
    2016/11/30 Wed 4PM-5PM
    The k disjoint paths problem, which was shown to be efficiently solvable for fixed k in undirected graphs in a breakthrough result by Robertson and Seymour, is notoriously difficult in directed graphs. In directed graphs, he problem is NP-complete even in the case when k=2. In an attempt to make the problem more tractable, Thomassen conjectured that if a digraph G were sufficiently strongly connected, then every k disjoint paths problem in G would be feasible. He later answered his conjecture in the negative, showing that the problem remains NP-complete when k=2, even when we assume that the graph is arbitrarily highly connected. </p>

    We consider the following further relaxation of the problem: a half-integral solution to a k disjoint paths problem is a set of paths linking the desired vertices such that each vertex of the graph is in at most two of the paths. We will present the new result that the half-integral k disjoint paths problem can be efficiently solved (even when the parameter k is included as part of the input!) if we assume the graph is highly connected.

    This is joint work with Irene Muzi and Katherine Edwards.

    Tags:

  • O-joung Kwon (권오정), Generalized feedback vertex set problems on bounded-treewidth graphs
    Generalized feedback vertex set problems on bounded-treewidth graphs
    O-joung Kwon (권오정)
    Technische Universitat Berlin, Berin, Germany
    2016/11/25 Fri 4PM-5PM
    It has long been known that Feedback Vertex Set can be solved in time 2O(w log w)nO(1) on graphs of treewidth w, but it was only recently that this running time was improved to 2O(w)nO(1), that is, to single-exponential parameterized by treewidth. We consider a natural generalization of this problem, which asks given a graph G on n vertices and positive integers k and d, whether there is a set S of at most k vertices of G such that each block of G-S has at most d vertices. The central question of this talk is: “Can we obtain an algorithm that runs in single-exponential time parameterized by treewidth, for every fixed d?” The answer is negative. But then, one may be curious which properties of Feedback Vertex Set that make it allow to have a single-exponential algorithm. To answer this question, we add an additional condition in the general problem, and provide a dichotomy result.
    Formally, for a class ? of graphs, the Bounded ?-Block Vertex Deletion problem asks, given a graph G on n vertices and positive integers k and d, whether there is a set S of at most k vertices of G such that each block of G-S has at most d vertices and is in ?. Assuming that ? is recognizable in polynomial time and satisfies a certain natural hereditary condition, we give a sharp characterization of when single-exponential parameterized algorithms are possible for fixed values of d:</p>
    • if ? consists only of chordal graphs, then the problem can be solved in time 2O(wd^2)nO(1),
    • if ? contains a graph with an induced cycle of length ℓ≥4, then the problem is not solvable in time 2o(w log w) nO(1) even for fixed d=ℓ, unless the ETH fails.

    We further show that it is W[1]-hard parameterized by only treewidth, when ? consists of all graphs. This is joint work with Édouard Bonnet, Nick Brettell, and Daniel Marx.

    Tags:

  • [Colloquium] Chris Godsil, Quantum walks on graphs

    FYI: Colloquium of Dept. of Mathematical Sciences.

    Quantum walks on graphs.
    Chris Godsil
    Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON, Canada
    2016/11/17 Thu 4:15PM-5:15PM
    A quantum walk is a (rather imperfect analog) of a random walk on a graph. They can be viewed as gadgets that might play a role in quantum computers, and have been used to produce algorithms that outperform corresponding classical procedures. Physical questions about these walks lead to problems in spectral graph theory, and they also provide interesting new graph invariants. In my talk I will present some of the background, and some of the many open problems that they have given rise to.
    Tags:

  • David Roberson, Homomorphisms of Strongly Regular Graphs
    Homomorphisms of Strongly Regular Graphs
    David Roberson
    Department of Computer Science, University College London, London, UK
    2016/11/16 Wed 4PM-5PM
    A homomorphism is an adjacency preserving map between the vertex sets of two graphs. A n-vertex, k-regular graph is strongly regular, with parameters (n,k,λ, μ), if there exist numbers λ and μ such that every pair of adjacent vertices share λ common neighbors and every pair of non-adjacent vertices share μ common neighbors. A strongly regular graph is primitive if neither it nor its complement is a disjoint union of complete graphs. We prove that if G and H are primitive strongly regular graphs with the same parameters and φ is a homomorphism from G to H, then φ is either an isomorphism or a coloring (homomorphism to a complete subgraph). Moreover, any such coloring is optimal for G and its image is a maximum clique of H. Therefore, the only endomorphisms of a primitive strongly regular graph are automorphisms or colorings. This confirms and strengthens a conjecture of Peter Cameron and Priscila Kazanidis that all strongly regular graphs are cores or have complete cores. The proof of the result is elementary, mainly relying on linear algebraic techniques.
    Tags:

  • [Soc Colloquium] Hee-Kap Ahn (안희갑), Locating the geodesic center of a simple polygon
    FYI: Colloquium, School of Computing
    Locating the geodesic center of a simple polygon
    Hee-Kap Ahn (안희갑)
    Department of Computer Science and Engineering, POSTECH
    2016/11/14 4PM-6PM (E3-1, Room #1501)
    Computational geometry deals with basic geometric objects such as points, line segments, polygons, and polyhedra, and aims to develop efficient algorithms and data structures for solving problems by figuring out the geometric, combinatorial, and topological properties of the objects. It has provided numerous methods and algorithms to solve geometric problems in application areas efficiently, such as computer graphics, robotics, geographic information systems, computer vision, and computational biology.
    The traditional geometric algorithms, however, are not adequate for real-world data because they are not designed to handle imprecise and uncertain data and therefore they may return a wrong answer due to the imprecision or uncertainty of data.
    This talk will provide an introduction to recent results of computational geometry on real-world data and open questions.
    Tags:

  • [Lecture series]Xavier Goaoc, Topological methods for discrete geometry

    MFRS Lecture Series

    Topological methods for discrete geometry
    Xavier Goaoc
    Université Paris-Est Marne-la-Vallée, France
    2016/11/04 Fri 5PM-6PM (Lecture 1)
    2016/11/07 Mon 4PM-5PM (Lecture 2)
    Helly’s theorem, a classical result in discrete geometry, asserts that if n>d convex subsets of R^d have empty intersection, some d+1 of them must already have empty intersection. I will discuss some topological generalizations of Helly’s theorem, where convexity is replaced by connectivity assumptions on the nonempty intersections, that lead to non-embeddability results of Borsuk-Ulam type and to variations on Leray’s acyclic cover theorem (or the Nerve theorem).
    Tags:

  • Xavier Goaoc, Embedding complete graphs in surfaces: what about higher dimensions?
    Embedding complete graphs in surfaces: what about higher dimensions?
    Xavier Goaoc
    Université Paris-Est Marne-la-Vallée, France
    2016/11/02 Wed 4PM-5PM
    The fact that the complete graph K5 does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood problem for graphs on surfaces established that Kn embeds in a closed surface M if and only if (n − 3)(n − 4) ≤ 6b1(M), where b1(M) is the first Betti number of M. On the other hand, van Kampen and Flores proved that the k-skeleton of the n-dimensional simplex (the higher-dimensional analogue of Kn+1 embeds in R2k if and only if n ≤ 2k + 1.
    I will discuss a conjecture of Kuhnel that generalizes both the Heawood inequality and the van Kampen-Flores theorem, and present some partial results toward this conjecture.
    Tags:

Monthly Archives