10 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.…
Linear Kernels for -Exact Component Order Connectivity
Yuxi Liu, Mingyu Xiao
The \textsc{-Exact Component Order Connectivity} problem asks whether, given an input graph and an integer , there exists a vertex subset of size at mos…
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…
The Role of Degrees and Acyclic Neighborhoods in the Complexity of Tournament Fixing
Yuxi Liu, Junqiang Peng, Mingyu Xiao +1
The \textsc{Tournament Fixing} problem asks whether a knockout tournament can be scheduled to make a favorite player win when all pairwise match outcomes are given. Such tournament…
Aggregation Queries over Unstructured Text: Benchmark and Agentic Method
Haojia Zhu, Qinyuan Xu, Haoyu Li +4
Aggregation query over free text is a long-standing yet underexplored problem. Unlike ordinary question answering, aggregate queries require exhaustive evidence collection and syst…
How Hard Is It to Rig a Tournament When Few Players Can Beat or Be Beaten by the Favorite?
Zhonghao Wang, Junqiang Peng, Yuxi Liu +1
In knockout tournaments, players compete in successive rounds, with losers eliminated and winners advancing until a single champion remains. Given a tournament digraph , which e…
A Refined Kernel for -Hitting Set
Yuxi Liu, Mingyu Xiao
The -Hitting Set problem is a fundamental problem in parameterized complexity, which asks whether a given hypergraph contains a vertex subset of size at most that inters…
Weighted Envy-Freeness Revisited: Indivisible Resource and House Allocations
Yuxi Liu, Mingyu Xiao
Envy-Freeness is one of the most fundamental and important concepts in fair allocation. Some recent studies have focused on the concept of weighted envy-freeness. Under this concep…
The Cost of Representation by Subset Repairs
Yuxi Liu, Fangzhu Shen, Kushagra Ghosh +3
Datasets may include errors, and specifically violations of integrity constraints, for various reasons. Standard techniques for ``minimal-cost'' database repairing resolve these vi…
Solving Co-Path/Cycle Packing and Co-Path Packing Faster Than
Yuxi Liu, Mingyu Xiao
The \textsc{Co-Path/Cycle Packing} problem (resp. The \textsc{Co-Path Packing} problem) asks whether we can delete at most vertices from the input graph such that the remaining…