4 papers
Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs
Shinwoo An, Yeonsu Chang, Kyungjin Cho +4
Horiyama et al. (AAAI 2024) considered the problem of generating instances with a unique minimum vertex cover under certain conditions. The Minimum Pre-assignment for Uniquificatio…
An FPT algorithm for cycle rank on semi-complete digraphs
Seokbeom Kim, O-joung Kwon, Myounghwan Lee
Cycle rank is a depth parameter for digraphs introduced by Eggan in 1963. Gruber (DMTCS 2012) and Giannopoulou, Hunter, and Thilikos (DAM 2012) asked whether the problem of determi…
Moderately beyond clique-width: reduced component max-leaf and related parameters
Ãdouard Bonnet, Yeonsu Chang, Julien Duron +2
Reduced parameters [BKW, JCTB '26; BKRT, SODA '22] are defined via contraction sequences. Based on this framework, we introduce the reduced component max-leaf, denoted by $\operato…
Unavoidable butterfly minors in digraphs of large cycle rank
Meike Hatzel, O-joung Kwon, Myounghwan Lee +1
Cycle rank is one of the depth parameters for digraphs introduced by Eggan in 1963. We show that there exists a function such that every digraph of cyc…