31 citations · 126 across the 26 of their papers we have counts for
31 papers
Cluster Deletion is as Hard to Approximate as Vertex Cover
Yixin Cao, Ying Xu
Recent breakthroughs in Cluster Editing have motivated attempts to adapt these approaches to obtain better-than- approximations for Cluster Deletion. We rule out this possibilit…
Minimum Sum Set Cover: Structures and Algorithm
Zhongyi Zhang, Yixin Cao
A set cover of a hypergraph is a set of vertices intersecting every hyperedge. In the minimum sum set cover problem, vertices are selected one by one; each edge pays the positi…
Cluster Vertex Deletion on Chordal Graphs
Yixin Cao, Peng Li
We present a polynomial-time algorithm for the cluster vertex deletion problem on chordal graphs, resolving an open question posed in different contexts by Cao et al. [Theoretical…
On Fork-free T-perfect Graphs
Yixin Cao, Shenghua Wang
In an attempt to understanding the complexity of the independent set problem, Chv{á}tal defined t-perfect graphs. While a full characterization of this class is still at large, pro…
Modification Problems toward Proper (Helly) Circular-arc Graphs
Yixin Cao, Jianxin Wang, Hanchun Yuan
We present a -time algorithm for the proper circular-arc vertex deletion problem, resolving an open problem of van 't Hof and Villanger [Algorithmica 2013] and C…
(Sub)linear kernels for edge modification problems towards structured graph classes
Gabriel Bathie, Nicolas Bousquet, Théo Pierron
In a (parameterized) graph edge modification problem, we are given a graph , an integer and a (usually well-structured) class of graphs , and ask whether it is…
Complementation in t-perfect graphs
Yixin Cao, Shenghua Wang
Inspired by applications of perfect graphs in combinatorial optimization, Chvátal defined t-perfect graphs in 1970s. The long efforts of characterizing t-perfect graphs started imm…
Improved Kernels for Edge Modification Problems
Yixin Cao, Yuping Ke
In an edge modification problem, we are asked to modify at most edges to a given graph to make the graph satisfy a certain property. Depending on the operations allowed, we hav…
Recognizing (Unit) Interval Graphs by Zigzag Graph Searches
Yixin Cao
Corneil, Olariu, and Stewart [SODA 1998; SIAM Journal on Discrete Mathematics 2009] presented a recognition algorithm for interval graphs by six graph searches. Li and Wu [Discrete…
Enumerating Maximal Induced Subgraphs
Yixin Cao
Given a graph , the maximal induced subgraphs problem asks to enumerate all maximal induced subgraphs of that belong to a certain hereditary graph class. While its optimizat…
Polynomial Kernels for Paw-free Edge Modification Problems
Yixin Cao, Yuping Ke, Hanchun Yuan
Let be a fixed graph. Given a graph and an integer , the -free edge modification problem asks whether it is possible to modify at most edges in to make it …
Characterization and Linear-time Recognition of Paired Threshold Graphs
Guozhen Rong, Yixin Cao, Jianxin Wang
In a paired threshold graph, each vertex has a weight, and two vertices are adjacent if their weight sum is large enough and their weight difference is small enough. It generalizes…
Graph Searches and Their End Vertices
Yixin Cao, Guozhen Rong, Jianxin Wang +1
Graph search, the process of visiting vertices in a graph in a specific order, has demonstrated magical powers in many important algorithms. But a systematic study was only initiat…
Local Coloring and its Complexity
Jie You, Yixin Cao, Jianxin Wang
A -coloring of a graph is an assignment of integers between and to vertices in the graph such that the endpoints of each edge receive different numbers. We study a local…
A -vertex Kernel for -packing
Wenjun Li, Junjie Ye, Yixin Cao
The -packing problem asks for whether a graph contains vertex-disjoint paths each of length two. We continue the study of its kernelization algorithms, and develop a -…
A Polynomial Kernel for Diamond-Free Editing
Yixin Cao, Ashutosh Rai, R. B. Sandeep +1
An -free editing problem asks whether we can edit at most edges to make a graph contain no induced copy of the fixed graph . We obtain a polynomial kernel for this proble…
An Parameterized Algorithm for the Multiterminal Cut Problem
Yixin Cao, Jianer Chen, Jia-Hao Fan
We study the \emph{multiterminal cut} problem, which, given an -vertex graph whose edges are integer-weighted and a set of terminals, asks for a partition of the vertex set such…
Vertex Deletion Problems on Chordal Graphs
Yixin Cao, Yuping Ke, Yota Otachi +1
Containing many classic optimization problems, the family of vertex deletion problems has an important position in algorithm and complexity study. The celebrated result of Lewis an…
A Naive Algorithm for Feedback Vertex Set
Yixin Cao
Given a graph on vertices and an integer , the feedback vertex set problem asks for the deletion of at most vertices to make the graph acyclic. We show that a greedy bra…
Unit Interval Vertex Deletion: Fewer Vertices are Relevant
Yuping Ke, Yixin Cao, Xiating Ouyang +1
The unit interval vertex deletion problem asks for a set of at most vertices whose deletion from an -vertex graph makes it a unit interval graph. We develop an -vert…
Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds
Yixin Cao, R. B. Sandeep
Given an sparse symmetric matrix with nonzero entries, performing Gaussian elimination may turn some zeroes into nonzero values. To maintain the matrix sparse, we would l…
Approximate Association via Dissociation
Jie You, Jianxin Wang, Yixin Cao
A vertex set of a graph is an association set if each component of is a clique, or a dissociation set if each component of is a single vertex or a single ed…
Unit Interval Editing is Fixed-Parameter Tractable
Yixin Cao
Given a graph~ and integers , , and~, the unit interval editing problem asks whether can be transformed into a unit interval graph by at most vertex del…
A -Vertex Kernel for Maximum Internal Spanning Tree
Wenjun Li, Jianxin Wang, Jianer Chen +1
We consider the parameterized version of the maximum internal spanning tree problem, which, given an -vertex graph and a parameter , asks for a spanning tree with at least $k…