Yuxi Liu

activity

20242026

collaborators

Showing cs.DSShow all

5 papers · 1 filter

cs.DS2026

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 $k$ vertices (resp.…

cs.DS2026

Linear Kernels for $l$ -Exact Component Order Connectivity

Yuxi Liu, Mingyu Xiao

The \textsc{ $l$ -Exact Component Order Connectivity} problem asks whether, given an input graph $G$ and an integer $k$ , there exists a vertex subset $S \subseteq V (G)$ of size at mos…

cs.DS2026

Faster Parameterized Vertex Multicut

Huairui Chu, Yuxi Liu, Daniel Lokshtanov +3

In the {\sc Vertex Multicut} problem the input consists of a graph $G$ , integer $k$ , and a set $T = {(s_{1}, t_{1}), \dots, (s_{p}, t_{p})}$ of pairs of vertices of $G$ . The ta…

cs.DS2025

A Refined Kernel for $d$ -Hitting Set

Yuxi Liu, Mingyu Xiao

The $d$ -Hitting Set problem is a fundamental problem in parameterized complexity, which asks whether a given hypergraph contains a vertex subset $S$ of size at most $k$ that inters…

cs.DS2024

Solving Co-Path/Cycle Packing and Co-Path Packing Faster Than $3^{k}$

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 $k$ vertices from the input graph such that the remaining…

Deterministic Single Exponential Time Algorithms for Co-Path Packing and Co-Path Set Parameterized by Treewidth

Linear Kernels for l-Exact Component Order Connectivity

Faster Parameterized Vertex Multicut

A Refined Kernel for d-Hitting Set

Solving Co-Path/Cycle Packing and Co-Path Packing Faster Than 3k

Linear Kernels for $l$ -Exact Component Order Connectivity

A Refined Kernel for $d$ -Hitting Set

Solving Co-Path/Cycle Packing and Co-Path Packing Faster Than $3^{k}$