Yixin Cao

YNIMG Journal 2026 Journal Article

Hippocampal subfields volumes as biomarkers for early diagnosis of asymptomatic manganese overexposure

• Jiayu Wu
• Yuli Gao
• Xuying Ru
• Sijia Fan
• Ming Gao
• Mengxue Sun
• Yixin Cao
• Mingyue Ma

Chronic occupational manganese (Mn) overexposure is associated with motor and cognitive deficits, but its effects on hippocampal subfields remain underexplored. Although neurodegeneration is known to involve the hippocampus, subfield-specific structural abnormalities have received limited attention. This study aimed to assess the diagnostic power of hippocampal subfield volumes in discriminating asymptomatic Mn-exposed welders from healthy controls (HCs). Mn-exposed welders and age-matched HCs were recruited and underwent high-resolution T1-weighted MRI scans. Volumes across 19 hippocampal subfields of each subject were estimated from automated tissue segmentations and surface-based reconstruction using FreeSurfer. The laterality value was defined as: (Right-Left)/(Right+Left)*100. Between-group differences in subfield volumes and laterality were assessed using cross-sectional analysis. Three machine learning classifiers, including logistic regression, K-nearest neighbors and support vector machine (SVM), were applied to differentiate welders from HCs. Compared to HCs, Mn-exposed welders had reduced volumes mainly in the fimbria, subiculum, and presubiculum, while showing higher volumes in the cornu ammonis area 3 (CA3). The welders group demonstrated significant rightward laterality in CA1 and CA4, and leftward laterality in the presubiculum. Among the three classifiers, the SVM classifier achieved the best performance (AUC = 0.96) in distinguishing welders from HCs using subfield volumes. Additionally, the exposure duration was non-linearly associated with left fimbria volume. These results revealed distinct volumetric and asymmetric patterns in hippocampal subfields among Mn-exposed welders, indicating regional vulnerability and potential compensatory responses. Notably, our findings underscored that hippocampal subfield volumes might serve as imaging biomarkers for early diagnosis in individuals with asymptomatic Mn overexposure.

TCS Journal 2026 Journal Article

Partial interval multicover: Approximation and complexity

• Peng Li
• Xiangzhi Tu
• Zhao Zhang
• Yixin Cao

We study a variant of set cover on the real line, where elements are points, sets are intervals, and each point has an integer demand; a point is fully covered when it is contained in at least its demand many chosen intervals. The objective is to select the fewest intervals that fully cover at least a specified number of points. We present the first polynomial-time approximation scheme (PTAS) for the unweighted version of this problem and show that a natural weighted generalization is NP-complete.

NeurIPS Conference 2025 Conference Paper

ForgerySleuth: Empowering Multimodal Large Language Models for Image Manipulation Detection

• Zhihao Sun
• Haoran Jiang
• Haoran Chen
• Yixin Cao
• Xipeng Qiu
• Zuxuan Wu
• Yu-Gang Jiang

Multimodal large language models have unlocked new possibilities for various multimodal tasks. However, their potential in image manipulation detection remains unexplored. When directly applied to the IMD task, M-LLMs often produce reasoning texts that suffer from hallucinations and overthinking. To address this, we propose ForgerySleuth, which leverages M-LLMs to perform comprehensive clue fusion and generate segmentation outputs indicating specific regions that are tampered with. Moreover, we construct the ForgeryAnalysis dataset through the Chain-of-Clues prompt, which includes analysis and reasoning text to upgrade the image manipulation detection task. A data engine is also introduced to build a larger-scale dataset for the pre-training phase. Our extensive experiments demonstrate the effectiveness of ForgeryAnalysis and show that ForgerySleuth significantly outperforms existing methods in generalization, robustness, and explainability.

NeurIPS Conference 2025 Conference Paper

Learning 3D Anisotropic Noise Distributions Improves Molecular Force Fields

• Xixian Liu
• Rui Jiao
• Zhiyuan Liu
• Yurou Liu
• Yang Liu
• Ziheng Lu
• Wenbing Huang
• Yang Zhang

Coordinate denoising has emerged as a promising method for 3D molecular pretraining due to its theoretical connection to learning molecular force field. However, existing denoising methods rely on oversimplied molecular dynamics that assume atomic motions to be isotropic and homoscedastic. To address these limitations, we propose a novel denoising framework AniDS: Anisotropic Variational Autoencoder for 3D Molecular Denoising. AniDS introduces a structure-aware anisotropic noise generator that can produce atom-specific, full covariance matrices for Gaussian noise distributions to better reflect directional and structural variability in molecular systems. These covariances are derived from pairwise atomic interactions as anisotropic corrections to an isotropic base. Our design ensures that the resulting covariance matrices are symmetric, positive semi-definite, and SO(3)-equivariant, while providing greater capacity to model complex molecular dynamics. Extensive experiments show that AniDS outperforms prior isotropic and homoscedastic denoising models and other leading methods on the MD17 and OC22 benchmarks, achieving average relative improvements of 8. 9% and 6. 2% in force prediction accuracy. Our case study on a crystal and molecule structure shows that AniDS adaptively suppresses noise along the bonding direction, consistent with physicochemical principles. Our code is available at https: //github. com/ZeroKnighting/AniDS.

TCS Journal 2025 Journal Article

Minimum sum vertex cover: Difficulty of ordering

• Jingyi Liu
• Yixin Cao
• Ling Gai
• Jianxin Wang

A minimum sum vertex cover of a graph is a vertex cover associated with a permutation of its vertices that minimizes the total cost of covering all edges. The cost of an edge is defined by the smaller index of its two endpoints in the permutation. While this vertex cover is not necessarily the smallest possible, we show that its size, denoted as k, is polynomially bounded by the size of the minimum vertex covers. We note that finding an optimal ordering is NP-hard even when the vertex set of an optimal solution is given. We propose an O ( m + 2 k k! k 3 ) -time algorithm for finding a minimum sum vertex cover, where m is the size of the input graph, toward which we also show a ( k 2 + 2 k ) -vertex kernel.

AAAI Conference 2025 Conference Paper

S^3cMath: Spontaneous Step-Level Self-Correction Makes Large Language Models Better Mathematical Reasoners

• Yuchen Yan
• Jin Jiang
• Yang Liu
• Yixin Cao
• Xin Xu
• Mengdi Zhang
• Xunliang Cai
• Jian Shao

Self-correction is a novel method that can stimulate the potential reasoning abilities of large language models (LLMs). It involves detecting and correcting errors during the inference process when LLMs solve reasoning problems. However, recent works do not regard self-correction as a spontaneous and intrinsic capability of LLMs. Instead, such correction is achieved through post-hoc generation, external knowledge introduction, multi-model collaboration, and similar techniques. In this paper, we propose a series of mathematical LLMs called S^3cMath, which are able to perform Spontaneous Step-level Self-correction for Mathematical reasoning. This capability helps LLMs to recognize whether their ongoing inference tends to contain errors and simultaneously correct these errors to produce a more reliable response. We proposed a method, which employs a step-level sampling approach to construct step-wise self-correction data for achieving such ability. Additionally, we implement a training strategy that uses above constructed data to equip LLMs with spontaneous step-level self-correction capacities. Our data and methods have been demonstrated to be effective across various foundation LLMs, consistently showing significant progress in evaluations on GSM8K, MATH, and other mathematical benchmarks. To the best of our knowledge, we are the first to introduce the spontaneous step-level self-correction ability of LLMs in mathematical reasoning.

AAAI Conference 2025 Conference Paper

Simulation-Free Hierarchical Latent Policy Planning for Proactive Dialogues

• Tao He
• Lizi Liao
• Yixin Cao
• Yuanxing Liu
• Yiheng Sun
• Zerui Chen
• Ming Liu
• Bing Qin

Recent advancements in proactive dialogues have garnered significant attention, particularly for more complex objectives (e.g. emotion support and persuasion). Unlike traditional task-oriented dialogues, proactive dialogues demand advanced policy planning and adaptability, requiring rich scenarios and comprehensive policy repositories to develop such systems. However, existing approaches tend to rely on Large Language Models (LLMs) for user simulation and online learning, leading to biases that diverge from realistic scenarios and result in suboptimal efficiency. Moreover, these methods depend on manually defined, context-independent, coarse-grained policies, which not only incur high expert costs but also raise concerns regarding their completeness. In our work, we highlight the potential for automatically discovering policies directly from raw, real-world dialogue records. To this end, we introduce a novel dialogue policy planning framework, LDPP. It fully automates the process from mining policies in dialogue records to learning policy planning. Specifically, we employ a variant of the Variational Autoencoder to discover fine-grained policies represented as latent vectors. After automatically annotating the data with these latent policy labels, we propose an Offline Hierarchical Reinforcement Learning (RL) algorithm in the latent space to develop effective policy planning capabilities. Our experiments demonstrate that LDPP outperforms existing methods on two proactive scenarios, even surpassing ChatGPT with only a 1.8-billion-parameter LLM.

NeurIPS Conference 2024 Conference Paper

Automating Dataset Updates Towards Reliable and Timely Evaluation of Large Language Models

• Jiahao Ying
• Yixin Cao
• Yushi Bai
• Qianru Sun
• Bo Wang
• Wei Tang
• Zhaojun Ding
• Yizhe Yang

Large language models (LLMs) have achieved impressive performance across various natural language benchmarks, prompting a continual need to curate more difficult datasets for larger LLMs, which is costly and time-consuming. In this paper, we propose to automate dataset updating and provide systematical analysis regarding its effectiveness in dealing with benchmark leakage issue, difficulty control, and stability. Thus, once current benchmark has been mastered or leaked, we can update it for timely and reliable evaluation. There are two updating strategies: 1) mimicking strategy to generate similar samples based on original data, preserving stylistic and contextual essence, and 2) extending strategy that further expands existing samples at varying cognitive levels by adapting Bloom’s taxonomy of educational objectives. Extensive experiments on updated MMLU and BIG-Bench demonstrate the stability of the proposed strategies and find that the mimicking strategy can effectively alleviate issues of overestimation from benchmark leakage. In cases where the efficient mimicking strategy fails, our extending strategy still shows promising results. Additionally, by controlling the difficulty, we can better discern the models’ performance and enable fine-grained analysis — neither too difficult nor too easy an exam can fairly judge students’ learning status. To the best of our knowledge, we are the first to automate updating benchmarks for reliable and timely evaluation. Our demo leaderboard can be found at https: //yingjiahao14. github. io/Automating-DatasetUpdates/.

NeurIPS Conference 2024 Conference Paper

Knowledge Graph Completion by Intermediate Variables Regularization

• Changyi Xiao
• Yixin Cao

Knowledge graph completion (KGC) can be framed as a 3-order binary tensor completion task. Tensor decomposition-based (TDB) models have demonstrated strong performance in KGC. In this paper, we provide a summary of existing TDB models and derive a general form for them, serving as a foundation for further exploration of TDB models. Despite the expressiveness of TDB models, they are prone to overfitting. Existing regularization methods merely minimize the norms of embeddings to regularize the model, leading to suboptimal performance. Therefore, we propose a novel regularization method for TDB models that addresses this limitation. The regularization is applicable to most TDB models and ensures tractable computation. Our method minimizes the norms of intermediate variables involved in the different ways of computing the predicted tensor. To support our regularization method, we provide a theoretical analysis that proves its effect in promoting low trace norm of the predicted tensor to reduce overfitting. Finally, we conduct experiments to verify the effectiveness of our regularization technique as well as the reliability of our theoretical analysis. The code is available at https: //github. com/changyi7231/IVR.

NeurIPS Conference 2024 Conference Paper

Meaningful Learning: Enhancing Abstract Reasoning in Large Language Models via Generic Fact Guidance

• Kai Xiong
• Xiao Ding
• Ting Liu
• Bing Qin
• Dongliang Xu
• Qing Yang
• Hongtao Liu
• Yixin Cao

Large language models (LLMs) have developed impressive performance and strong explainability across various reasoning scenarios, marking a significant stride towards mimicking human-like intelligence. Despite this, when tasked with several simple questions supported by a generic fact, LLMs often struggle to abstract and apply the generic fact to provide consistent and precise answers, revealing a deficiency in abstract reasoning abilities. This has sparked a vigorous debate about whether LLMs are genuinely reasoning or merely memorizing. In light of this, we design a preliminary study to quantify and delve into the abstract reasoning abilities of existing LLMs. Our findings reveal a substantial discrepancy between their general reasoning and abstract reasoning performances. To relieve this problem, we tailor an abstract reasoning dataset (AbsR) together with a meaningful learning paradigm to teach LLMs how to leverage generic facts for reasoning purposes. The results show that our approach not only boosts the general reasoning performance of LLMs but also makes considerable strides towards their capacity for abstract reasoning, moving beyond simple memorization or imitation to a more nuanced understanding and application of generic facts. The code is available at https: //github. com/Waste-Wood/MeanLearn.

NeurIPS Conference 2024 Conference Paper

MMLONGBENCH-DOC: Benchmarking Long-context Document Understanding with Visualizations

• Yubo Ma
• Yuhang Zang
• Liangyu Chen
• Meiqi Chen
• Yizhu Jiao
• Xinze Li
• Xinyuan Lu
• Ziyu Liu

Understanding documents with rich layouts and multi-modal components is a long-standing and practical task. Recent Large Vision-Language Models (LVLMs) have made remarkable strides in various tasks, particularly in single-page document understanding (DU). However, their abilities on long-context DU remain an open problem. This work presents MMLONGBENCH-DOC, a long-context, multi- modal benchmark comprising 1, 082 expert-annotated questions. Distinct from previous datasets, it is constructed upon 135 lengthy PDF-formatted documents with an average of 47. 5 pages and 21, 214 textual tokens. Towards comprehensive evaluation, answers to these questions rely on pieces of evidence from (1) different sources (text, image, chart, table, and layout structure) and (2) various locations (i. e. , page number). Moreover, 33. 7\% of the questions are cross-page questions requiring evidence across multiple pages. 20. 6\% of the questions are designed to be unanswerable for detecting potential hallucinations. Experiments on 14 LVLMs demonstrate that long-context DU greatly challenges current models. Notably, the best-performing model, GPT-4o, achieves an F1 score of only 44. 9\%, while the second-best, GPT-4V, scores 30. 5\%. Furthermore, 12 LVLMs (all except GPT-4o and GPT-4V) even present worse performance than their LLM counterparts which are fed with lossy-parsed OCR documents. These results validate the necessity of future research toward more capable long-context LVLMs.

I&C Journal 2024 Journal Article

Modification problems toward proper (Helly) circular-arc graphs

• Yixin Cao
• Hanchun Yuan
• Jianxin Wang

We present a 9 k ⋅ n O ( 1 ) -time algorithm for the proper circular-arc vertex deletion problem, resolving an open problem of van 't Hof and Villanger [Algorithmica 2013] and Crespelle et al. [Computer Science Review 2023]. Our structural study also implies parameterized algorithms for modification problems toward proper Helly circular-arc graphs.

NeurIPS Conference 2023 Conference Paper

Benchmarking Foundation Models with Language-Model-as-an-Examiner

• Yushi Bai
• Jiahao Ying
• Yixin Cao
• Xin Lv
• Yuze He
• Xiaozhi Wang
• Jifan Yu
• Kaisheng Zeng

Numerous benchmarks have been established to assess the performance of foundation models on open-ended question answering, which serves as a comprehensive test of a model's ability to understand and generate language in a manner similar to humans. Most of these works focus on proposing new datasets, however, we see two main issues within previous benchmarking pipelines, namely testing leakage and evaluation automation. In this paper, we propose a novel benchmarking framework, Language-Model-as-an-Examiner, where the LM serves as a knowledgeable examiner that formulates questions based on its knowledge and evaluates responses in a reference-free manner. Our framework allows for effortless extensibility as various LMs can be adopted as the examiner, and the questions can be constantly updated given more diverse trigger topics. For a more comprehensive and equitable evaluation, we devise three strategies: (1) We instruct the LM examiner to generate questions across a multitude of domains to probe for a broad acquisition, and raise follow-up questions to engage in a more in-depth assessment. (2) Upon evaluation, the examiner combines both scoring and ranking measurements, providing a reliable result as it aligns closely with human annotations. (3) We additionally propose a decentralized Peer-examination method to address the biases in a single examiner. Our data and benchmarking results are available at: http: //lmexam. xlore. cn.

AAAI Conference 2023 Conference Paper

Knowledge Graph Embedding by Normalizing Flows

• Changyi Xiao
• Xiangnan He
• Yixin Cao

A key to knowledge graph embedding (KGE) is to choose a proper representation space, e.g., point-wise Euclidean space and complex vector space. In this paper, we propose a unified perspective of embedding and introduce uncertainty into KGE from the view of group theory. Our model can incorporate existing models (i.e., generality), ensure the computation is tractable (i.e., efficiency) and enjoy the expressive power of complex random variables (i.e., expressiveness). The core idea is that we embed entities/relations as elements of a symmetric group, i.e., permutations of a set. Permutations of different sets can reflect different properties of embedding. And the group operation of symmetric groups is easy to compute. In specific, we show that the embedding of many existing models, point vectors, can be seen as elements of a symmetric group. To reflect uncertainty, we first embed entities/relations as permutations of a set of random variables. A permutation can transform a simple random variable into a complex random variable for greater expressiveness, called a normalizing flow. We then define scoring functions by measuring the similarity of two normalizing flows, namely NFE. We construct several instantiating models and prove that they are able to learn logical rules. Experimental results demonstrate the effectiveness of introducing uncertainty and our model. The code is available at https://github.com/changyi7231/NFE.

TCS Journal 2022 Journal Article

A 5k-vertex kernel for P2-packing

• Wenjun Li
• Junjie Ye
• Yixin Cao

The P 2 -packing problem asks whether a graph contains k vertex-disjoint (not necessarily induced) paths each of length two. We continue the study of its kernelization algorithms, and develop a 5k-vertex kernel.

AAAI Conference 2022 Conference Paper

Debiasing NLU Models via Causal Intervention and Counterfactual Reasoning

• Bing Tian
• Yixin Cao
• Yong Zhang
• Chunxiao Xing

Recent studies have shown that strong Natural Language Understanding (NLU) models are prone to relying on annotation biases of the datasets as a shortcut, which goes against the underlying mechanisms of the task of interest. To reduce such biases, several recent works introduce debiasing methods to regularize the training process of targeted NLU models. In this paper, we provide a new perspective with causal inference to find out the bias. On the one hand, we show that there is an unobserved confounder for the natural language utterances and their respective classes, leading to spurious correlations from training data. To remove such confounder, the backdoor adjustment with causal intervention is utilized to find the true causal effect, which makes the training process fundamentally different from the traditional likelihood estimation. On the other hand, in inference process, we formulate the bias as the direct causal effect and remove it by pursuing the indirect causal effect with counterfactual reasoning. We conduct experiments on large-scale natural language inference and fact verification benchmarks, evaluating on bias sensitive datasets that are specifically designed to assess the robustness of models against known biases in the training data. Experimental results show that our proposed debiasing framework outperforms previous stateof-the-art debiasing methods while maintaining the original in-distribution performance.

TCS Journal 2021 Journal Article

Polynomial kernels for paw-free edge modification problems

• Hanchun Yuan
• Yuping Ke
• Yixin Cao

Given a graph G and an integer k, the paw-free completion problem asks whether it is possible to add at most k edges to G to make it paw-free. The paw-free edge deletion problem is defined analogously. Sandeep and Sivadasan (IPEC 2015) asked whether these problems admit polynomial kernels. We answer both questions affirmatively by presenting, respectively, O ( k ) -vertex and O ( k 4 ) -vertex kernels for them. This is part of an ongoing program that aims at understanding the compressibility of H-free edge modification problems for general H.

AAAI Conference 2020 Conference Paper

Image Enhanced Event Detection in News Articles

• Meihan Tong
• Shuai Wang
• Yixin Cao
• Bin Xu
• Juanzi Li
• Lei Hou
• Tat-Seng Chua

Event detection is a crucial and challenging sub-task of event extraction, which suffers from a severe ambiguity issue of trigger words. Existing works mainly focus on using textual context information, while there naturally exist many images accompanied by news articles that are yet to be explored. We believe that images not only reflect the core events of the text, but are also helpful for the disambiguation of trigger words. In this paper, we first contribute an image dataset supplement to ED benchmarks (i. e. , ACE2005) for training and evaluation. We then propose a novel Dual Recurrent Multimodal Model, DRMM, to conduct deep interactions between images and sentences for modality features aggregation. DRMM utilizes pre-trained BERT and ResNet to encode sentences and images, and employs an alternating dual attention to select informative features for mutual enhancements. Our superior performance compared to six state-of-art baselines as well as further ablation studies demonstrate the significance of image modality and effectiveness of the proposed architecture. The code and image dataset are avaliable at https: //github. com/ shuaiwa16/image-enhanced-event-extraction.

I&C Journal 2020 Journal Article

Minimum fill-in: Inapproximability and almost tight lower bounds

• Yixin Cao
• R.B. Sandeep

Given an n × n sparse symmetric matrix with m nonzero entries, performing Gaussian elimination may turn some zeroes into nonzero values, so called fill-ins. The minimum fill-in problem asks whether it is possible to perform the elimination with at most k fill-ins. We exclude the existence of polynomial time approximation schemes for this problem, assuming P≠NP, and the existence of 2 O ( n 1 − δ ) -time approximation schemes for any positive δ, assuming the Exponential Time Hypothesis. We also give a 2 O ( k 1 / 2 − δ ) ⋅ n O ( 1 ) parameterized lower bound. All these results come as corollaries of a new reduction from vertex cover to the minimum fill-in problem, which might be of its own interest: All previous reductions for similar problems start from some kind of graph layout problems, and hence have limited use in understanding their fine-grained complexity.

TCS Journal 2020 Journal Article

Preface to the special issue on Computing and Combinatorics

• Yixin Cao

AAAI Conference 2019 Conference Paper

Explainable Reasoning over Knowledge Graphs for Recommendation

• Xiang Wang
• Dingxian Wang
• Canran Xu
• Xiangnan He
• Yixin Cao
• Tat-Seng Chua

Incorporating knowledge graph into recommender systems has attracted increasing attention in recent years. By exploring the interlinks within a knowledge graph, the connectivity between users and items can be discovered as paths, which provide rich and complementary information to user-item interactions. Such connectivity not only reveals the semantics of entities and relations, but also helps to comprehend a user’s interest. However, existing efforts have not fully explored this connectivity to infer user preferences, especially in terms of modeling the sequential dependencies within and holistic semantics of a path. In this paper, we contribute a new model named Knowledgeaware Path Recurrent Network (KPRN) to exploit knowledge graph for recommendation. KPRN can generate path representations by composing the semantics of both entities and relations. By leveraging the sequential dependencies within a path, we allow effective reasoning on paths to infer the underlying rationale of a user-item interaction. Furthermore, we design a new weighted pooling operation to discriminate the strengths of different paths in connecting a user with an item, endowing our model with a certain level of explainability. We conduct extensive experiments on two datasets about movie and music, demonstrating significant improvements over state-of-the-art solutions Collaborative Knowledge Base Embedding and Neural Factorization Machine.

TCS Journal 2018 Journal Article

Vertex deletion problems on chordal graphs

• Yixin Cao
• Yuping Ke
• Yota Otachi
• Jie You

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 and Yannakakis gives a complete dichotomy of their complexity. It however has nothing to say about the case when the input graph is also special. This paper initiates a systematic study of vertex deletion problems from one subclass of chordal graphs to another. We give polynomial-time algorithms or proofs of NP-completeness for most of the problems. In particular, we show that the vertex deletion problem from chordal graphs to interval graphs is NP-complete.

I&C Journal 2017 Journal Article

Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree

• Wenjun Li
• Yixin Cao
• Jianer Chen
• Jianxin Wang

The maximum internal spanning tree problem asks for a spanning tree of a given graph that has the maximum number of internal vertices among all spanning trees of this graph. In its parameterized version, we are interested in whether the graph has a spanning tree with at least k internal vertices. Fomin et al. (2013) [4] crafted a very ingenious reduction rule, and showed that a simple application of this rule is sufficient to yield a 3k-vertex kernel, implying an O ⁎ ( 8 k ) -time parameterized algorithm. Using depth-2 local search, Knauer and Spoerhase (2015) [9] developed a (5/3)-approximation algorithm for the optimization version. We try deeper local search: We conduct a thorough combinatorial analysis on the obtained spanning trees and explore their algorithmic consequences. We first observe that from the spanning tree obtained by depth-3 local search, one can easily find a reducible structure and apply the reduction rule of Fomin et al. This gives an improved kernel of 2k vertices, and as a by-product, a deterministic algorithm running in time O ⁎ ( 4 k ). We then go even deeper by considering the spanning tree obtained by depth-5 local search. It is shown that the number of internal vertices of this spanning tree is at least 2/3 of the maximum number a spanning tree can have, thereby delivering an improved approximation algorithm with ratio 1. 5 for the problem.

I&C Journal 2017 Journal Article

Unit interval editing is fixed-parameter tractable

• Yixin Cao

Given a graph G and integers k 1, k 2, and k 3, the unit interval editing problem asks whether G can be transformed into a unit interval graph by at most k 1 vertex deletions, k 2 edge deletions, and k 3 edge additions. We give an algorithm solving this problem in time 2 O ( k log ⁡ k ) ⋅ ( n + m ), where k: = k 1 + k 2 + k 3, and n, m denote respectively the numbers of vertices and edges of G. Therefore, it is fixed-parameter tractable parameterized by the total number of allowed operations. Our algorithm implies the fixed-parameter tractability of the unit interval edge deletion problem, for which we also present a more efficient algorithm running in time O ( 4 k ⋅ ( n + m ) ). Another result is an O ( 6 k ⋅ ( n + m ) ) -time algorithm for the unit interval vertex deletion problem, significantly improving the algorithm of van 't Hof and Villanger, which runs in time O ( 6 k ⋅ n 6 ).

TCS Journal 2015 Journal Article

Edge deletion problems: Branching facilitated by modular decomposition

• Yunlong Liu
• Jianxin Wang
• Jie You
• Jianer Chen
• Yixin Cao

Edge deletion problems ask for a minimum set of edges whose deletion makes a graph have a certain property. When this property can be characterized by a finite set of forbidden induced subgraphs, the problem can be solved in fixed-parameter time by a naive bounded search tree algorithm. Sometimes deleting an edge to break an erstwhile forbidden induced subgraph might introduce new ones, which may involve the neighbors of the original forbidden induced subgraph. Therefore, in considering possible ways to break a forbidden induced subgraph one naturally takes its neighborhood into consideration. This observation easily yields more efficient branching rules, but a naive implementation will require too many tedious case analyses. Here we take advantage of modular decomposition, which allows us to focus on far simpler quotient graphs instead of the original graphs. They together yield simple improved algorithms for the edge deletion problems to chain graphs and trivially perfect graphs.