Speaker:

Chao Xu (Assistant Professor in University of Electronic Science and Technology of China)

Time:

• 16:20-17:20 (Time in Beijing)
• 21:20-22:20 (Time in Auckland)
• March 4, 2022 (Friday)

Venue:

B1-518B, Research Building 4

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.