Seminars in July 2019

  • 2019 IBS Summer Research Program on Algorithms and Complexity in Discrete Structures

    2019 IBS Summer Research Program on Algorithms and Complexity in Discrete Structures

    Website: https://dimag.ibs.re.kr/event/2019-ibs-summer-research-program/

    July 21 Sunday – August 10 Saturday

    Room B232, IBS (기초과학연구원)

    Schedule

    July 22 Monday

    10:00-11:00 Introduction

    11:00-12:00 Open Problems

    July 23 Tuesday

    11:00-10:30 Stefan Kratsch, Humboldt-Universität zu Berlin, Germany
    Elimination Distances, Blocking Sets, and Kernels for Vertex Cover

    10:45-11:15 Benjamin Bergougnoux, University Clermont Auvergne, France
    More applications of the d-neighbor equivalence

    11:30-12:00 Yixin Cao, Hong Kong Polytechnic University, China
    Enumerating Maximal Induced Subgraphs

    July 24 Wednesday

    (We will go to KAIST for June Huh‘s two talks 15:00-16:00, 16:30-17:30.)

    July 25 Thursday

    10:00-11:00 Nick Brettell, Eindhoven University of Technology, Netherlands
    Recent work on characterising matroids representable over finite fields

    11:30-12:00 Mamadou M. Kanté, University Clermont Auvergne, France
    On recognising k-letter graphs

    July 26 Friday

    10:00-11:00 O-joung Kwon (권오정), Incheon National University, Korea
    The grid theorem for vertex-minors

    11:00-12:00 Progress Report

    July 27 Saturday

    8:30 Excursion to Damyang (departure from the accommodation)

    July 29 Monday

    10:00-11:00 Archontia Giannopoulou, National and Kapodistrian University of Athens, Greece
    The directed flat wall theorem

    11:30-12:00 Eunjung Kim (김은정), LAMSADE-CNRS, France
    Subcubic even-hole-free graphs have a constant treewidth

    July 30 Tuesday

    10:00-11:00 Pierre Aboulker, ENS Ulm, France
    Generalizations of the geometric de Bruijn Erdős Theorem

    11:30-12:00 Michael Dobbins, Binghamton University, USA
    Barycenters of points in polytope skeleta

    July 31 Wednesday

    10:00-11:00 Magnus Wahlström, Royal Holloway, University of London, UK
    T.B.A.

    11:30-12:00 Édouard Bonnet, ENS Lyon, France
    The FPT/W[1]-hard dichotomy of Max Independent Set in H-free graphs

    August 1 Thursday

    10:00-11:00 Euiwoong Lee (이의웅), NYU, USA
     Losing treewidth by separating subsets

    11:30-12:00 Sang-il Oum (엄상일), IBS Discrete Mathematics Group and KAIST, Korea
    Branch-depth: Generalizing tree-depth of graphs

    August 2 Friday

    10:00-11:00 Dabeen Lee (이다빈), IBS Discrete Mathematics Group, Korea
    t-perfect graphs and the stable set problem

    11:00-12:00 Progress Report

    August 5-9: Free Discussions / Research Collaborations / Progress Report
    Tea time: Every weekday 3:30pm

  • Dabeen Lee, Integrality of set covering polyhedra and clutter minors

    IBS/KAIST Joint Discrete Math Seminar

    Integrality of set covering polyhedra and clutter minors
    Dabeen Lee (이다빈)
    IBS Discrete Mathematics Group
    2019/07/16 Tue 4:30PM-5:30PM
    Given a finite set of elements $V$ and a family $\mathcal{C}$ of subsets of $V$, the set covering problem is to find a minimum cardinality subset of $V$ intersecting every subset in the family $\mathcal{C}$. The set covering problem, also known as the hitting set problem, admits a simple integer linear programming formulation. The constraint system of the integer linear programming formulation defines a polyhedron, and we call it the set covering polyhedron of $\mathcal{C}$. We say that a set covering polyhedron is integral if every extreme point is an integer lattice point. Although the set covering problem is NP-hard in general, conditions under which the problem becomes polynomially solvable have been studied. If the set covering polyhedron is integral, then it is straightforward that the problem can be solved using a polynomial-time algorithm for linear programming.</p>

    In this talk, we will focus on the question of when the set covering polyhedron is integral. We say that the family $\mathcal{C}$ is a clutter if every subset in $\mathcal{C}$ is inclusion-wise minimal. As taking out non-minimal subsets preserves integrality, we may assume that $\mathcal{C}$ is a clutter. We call $\mathcal{C}$ ideal if the set covering polyhedron of it is integral. To understand when a clutter is ideal, the notion of clutter minors is important in that $\mathcal{C}$ is ideal if and only if so is every minor of it. We will study two fundamental classes of non-ideal clutters, namely, deltas and the blockers of extended odd holes. We will characterize when a clutter contains either a delta or the blocker of an extended odd hole as a minor.

    This talk is based on joint works with Ahmad Abdi and G\’erard Cornu\’ejols.

    Tags:

Monthly Archives