4 papers · 1 filter
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 Lagrangian Approach to Interdiction of Linear Minimization Problems
Yu Cong, Kangyi Tian
We study budgeted interdiction of linear minimization problems. Given a family of feasible sets, element weights, and deletion costs, the objective is to delete elements within a p…
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…
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…