Speaker:

Chao Xu (University of Electronic Science and Technology of China)

Time:

• 15:00-16:00 (Time in Beijing)
• August 19, 2022 (Friday)

Venue:

Online, Tencent Meeting：662-155-517

Abstract:

The minimum violation problem asks for a vertex map from a digraph to a pattern digraph that minimizes violation, the total weight of the edges not mapped to an edge. We are interested in surjective mappings. We characterize all patterns where a minimum violation map that fixes some vertices can be computed in polynomial time. We also make progress in the case where we do not fix any vertex in the mapping, including when the digraph is disconnected, when the graph is in the variety of finite paths. Moreover, we obtain a dichotomy result for trees. We apply the result to some cut problems including k-cut with size lower bounds and length bounded k-cuts. This is a joint work with Ken-ichi Kawarabayashi.

Speaker Bio:

Chao Xu is currently an Assistant Professor at Algorithms and Logic Group in UESTC. He obtained a Ph.D. degree of Computer Science at UIUC in May 2018. He works in the field of combinatorial optimization and has published a series of papers in SODA, RANDOM, SIAM J.Computing, SIAM J. Disc Math., Math. Program.