4 papers
Deterministic Single Exponential Time Algorithms for Co-Path Packing and Co-Path Set Parameterized by Treewidth
Yuxi Liu, Kangyi Tian, Mingyu Xiao
The \textsc{Co-Path Packing} (resp., \textsc{Co-Path Set}) problem asks whether a given graph can be edited to a collection of induced paths by deleting at most vertices (resp.…
A Faster Deterministic Algorithm for Kidney Exchange via Representative Set
Kangyi Tian, Mingyu Xiao
The Kidney Exchange Problem is a prominent challenge in healthcare and economics, arising in the context of organ transplantation. It has been extensively studied in artificial int…
A Note on Interdiction of Linear Minimization Problems
Yu Cong, Kangyi Tian
Motivated by the FPTAS for connectivity interdiction of Huang et al. (IPCO'24), we isolate the part of the argument that does not use cuts. The setting is a minimization problem ov…
Faster Parameterized Vertex Multicut
Huairui Chu, Yuxi Liu, Daniel Lokshtanov +3
In the {\sc Vertex Multicut} problem the input consists of a graph , integer , and a set of pairs of vertices of . The ta…