On November 12, Tony Huynh from Monash University gave a talk on the maximum weight stable set problem on graphs with bounded odd cycle packing number. The title of his talk was “Stable sets in graphs with bounded odd cycle packing number“.

## Tony Huynh, Stable sets in graphs with bounded odd cycle packing number

It is a classic result that the maximum weight stable set problem is efficiently solvable for bipartite graphs. The recent bimodular algorithm of Artmann, Weismantel and Zenklusen shows that it is also efficiently solvable for graphs without two disjoint odd cycles. The complexity of the stable set problem for graphs without $k$ disjoint odd cycles is a long-standing open problem for all other values of $k$. We prove that under the additional assumption that the input graph is embedded in a surface of bounded genus, there is a polynomial-time algorithm for each fixed $k$. Moreover, we obtain polynomial-size extended formulations for the respective stable set polytopes.

To this end, we show that 2-sided odd cycles satisfy the Erdős-Pósa property in graphs embedded in a fixed surface. This result may be of independent interest and extends a theorem of Kawarabayashi and Nakamoto asserting that odd cycles satisfy the Erdős-Pósa property in graphs embedded in a fixed orientable surface.

Eventually, our findings allow us to reduce the original problem to the problem of finding a minimum-cost non-negative integer circulation of a certain homology class, which we prove to be efficiently solvable in our case.

This is joint work with Michele Conforti, Samuel Fiorini, Gwenaël Joret, and Stefan Weltge.

## Combinatorial and Discrete Optimization (2019 KSIAM Annual Meeting)

# Special Session @ 2019 KSIAM Annual Meeting

A special session on “Combinatorial and Discrete Optimization” at the 2019 KSIAM Annual Meeting is organized by Dabeen Lee. URL: https://www.ksiam.org/conference/84840fb6-87b0-4566-acc1-4802bde58fbd/welcome

## Date

**Nov 8, 2019** – **Nov 9, 2019** Address: 61-13 Odongdo-ro, Sujeong-dong, Yeosu-si, Jeollanam-do (전남 여수시 오동도로 61-13)

## Venue

Venezia Hotel & Resort Yeosu, Yeosu, Korea (여수 베네치아 호텔) Address: 61-13 Odongdo-ro, Sujeong-dong, Yeosu-si, Jeollanam-do (전남 여수시 오동도로 61-13)

## Speakers

**Hyung-Chan An (안형찬)**,*Yonsei University***Tony Huynh**,*Monash University***Dong Yeap Kang (강동엽)**,*KAIST / IBS Discrete Mathematics Group***Dabeen Lee (이다빈)**,*IBS Discrete Mathematics Group***Kangbok Lee (이강복)**,*POSTECH***Sang-il Oum (엄상일)**,*IBS Discrete Mathematics Group / KAIST***Kedong Yan**,*Nanjing University of Science and Technology***Se-Young Yun (윤세영)**,*KAIST*

## Schedules

- Combinatorial and Discrete Optimization I: November 8, 2019 Friday, 14:20 – 15:40.
- Kangbok Lee
- Kedong Yan
- Dabeen Lee
- Se-young Yun

- Combinatorial and Discrete Optimization II: November 9, 2019 Saturday, 10:00 – 11:20.
- Hyung Chan An
- Dong Yeap Kang
- Tony Huynh
- Sang-il Oum

## Abstracts

#### Kangbok Lee (이강복), Bi-criteria scheduling

#### Kedong Yan, Cliques for multi-term linearization of 0-1 multilinear program for boolean logical pattern generation

#### Dabeen Lee (이다빈), **Joint Chance-constrained programs and the intersection of mixing sets through a submodularity lens**

The intersection of mixing sets with common binary variables arise when modeling joint linear chance-constrained programs with random right-hand sides and finite sample space. In this talk, we first establish a strong and previously unrecognized connection of mixing sets to submodularity. This viewpoint enables us to unify and extend existing results on polyhedral structures of mixing sets. Then we study the intersection of mixing sets with common binary variables and also linking constraint lower bounding a linear function of the continuous variables. We propose a new class of valid inequalities and characterize when this new class along with the mixing inequalities are sufficient to describe the convex hull.

#### Se-Young Yun (윤세영), Optimal sampling and clustering algorithms in the stochastic block model

#### Hyung-Chan An (안형찬), Constant-factor approximation algorithms for parity-constrained facility location problems

*Facility location*is a prominent optimization problem that has inspired a large quantity of both theoretical and practical studies in combinatorial optimization. Although the problem has been investigated under various settings reflecting typical structures within the optimization problems of practical interest, little is known on how the problem behaves in conjunction with parity constraints. This shortfall of understanding was rather disturbing when we consider the central role of

*parity*in the field of combinatorics. In this paper, we present the first constant-factor approximation algorithm for the facility location problem with parity constraints. We are given as the input a metric on a set of

*facilities*and

*clients*, the opening cost of each facility, and the

*parity requirement*—$\mathsf{odd}$, $\mathsf{even}$, or $\mathsf{unconstrained}$—of every facility in this problem. The objective is to open a subset of facilities and assign every client to an open facility so as to minimize the sum of the total opening costs and the assignment distances, but subject to the condition that the number of clients assigned to each open facility must have the same parity as its requirement. Although the unconstrained facility location problem as a relaxation for this parity-constrained generalization has unbounded gap, we demonstrate that it yields a structured solution whose parity violation can be corrected at small cost. This correction is prescribed by a $T$-join on an auxiliary graph constructed by the algorithm. This graph does not satisfy the triangle inequality, but we show that a carefully chosen set of shortcutting operations leads to a cheap and

*sparse*$T$-join. Finally, we bound the correction cost by exhibiting a combinatorial multi-step construction of an upper bound. At the end of this paper, we also present the first constant-factor approximation algorithm for the parity-constrained $k$-center problem, the bottleneck optimization variant.

#### Dong Yeap Kang (강동엽), On minimal highly connected spanning subgraphs in dense digraphs

In 1985, Mader showed that every $n(\geq4k+3)$-vertex strongly $k$-connected digraph contains a spanning strongly $k$-connected subgraph with at most $2kn-2k^2$ edges, and the only extremal digraph is a complete bipartite digraph $DK_{k,n−k}$. Nevertheless, since the extremal graph is sparse, Bang-Jensen asked whether there exists g(k) such that every strongly $k$-connected $n$-vertex tournament contains a spanning strongly $k$-connected subgraph with $kn + g(k)$ edges, which is an “almost $k$-regular” subgraph.

#### Tony Huynh, Stable sets in graphs with bounded odd cycle packing number

#### Sang-il Oum, Rank-width: Algorithmic and structural results

## The first seminar talk at DIMAG was given by Tony Huynh on December 10

Tony Huynh from Université libre de Bruxelles became the first person to give a talk at discrete math seminar at DIMAG on December 10, 2018. He talked about his recent work “A tight Erdős-Pósa function for planar minors” (SODA’19).

## Tony Huynh, A tight Erdős-Pósa function for planar minors

Let H be a planar graph. By a classical result of Robertson and Seymour, there is a function f(k) such that for all k and all graphs G, either G contains k vertex-disjoint subgraphs each containing H as a minor, or there is a subset X of at most f(k) vertices such that G−X has no H-minor. We prove that this remains true with f(k)=ck log k for some constant c depending on H. This bound is best possible, up to the value of c, and improves upon a recent bound of Chekuri and Chuzhoy. The proof is constructive and yields the first polynomial-time O(log 𝖮𝖯𝖳)-approximation algorithm for packing subgraphs containing an H-minor.

This is joint work with Wouter Cames van Batenburg, Gwenaël Joret, and Jean-Florent Raymond.