Publications
2025
Ziliang Xiong, Mingyu Xiao: A Simplified Parameterized Algorithm for Directed Feedback Vertex Set. SOSA 2025 (accepted) 2024
Yiding Feng, Mengfan Ma, Mingyu Xiao: Price of Non-discrimination in Public Combinatorial Contracts. WINE 2024 (accepted) Jingyang Zhao, Mingyu Xiao: Improved Approximation Algorithms for the Cumulative Vehicle Routing Problem. ICONIP 2024 (Accepted) 白天，肖鸣宇：反馈集问题与子集反馈集问题的计算复杂性研究进展. 计算机研究与发展 （2024）（Accepted） 白天，肖鸣宇：超图上最大独立集问题的精确算法. 中国科学 (2024)（Accepted） Tsuyoshi Hirayama, Yuhao Liu, Kazuhisa Mikino, Ke Shi, Chao Xu: A polynomial time algorithm for finding a minimum 4-partition of a submodular function. Math. Program. 207(1): 717-732 (2024) Jingyang Zhao, Mingyu Xiao. Approximation Algorithms for Cumulative Vehicle Routing with Stochastic Demands. ISAAC 2024 (accepted) Tian Bai, Mingyu Xiao. Breaking the Barrier 2^k for Subset Feedback Vertex Set in Chordal Graphs. MFCS 2024 : 15:1-15:18 Yuxi Liu and Mingyu Xiao. Solving Co-Path/Cycle Packing and Co-Path Packing Faster Than 3^k. IPEC 2024 (accepted) Chunyu Luo, Yi Zhou, Zhengren Wang and Mingyu Xiao. A Faster Branching Algorithm for the Maximum k-Defective Clique Problem. ECAI 2024 : 4132-4139 Fengjuan Jia, Mengxiao Zhang, Jiamou Liu, Bakh Khoussainov. Balancing Efficiency with Equality: Auction Design with Group Fairness Concerns. ECAI 2024: 3252-3259 Yuan Fang, Mengxiao Zhang, Jiamou Liu, Bakh Khoussainov. Meta-mechanisms for Combinatorial Auctions over Social Networks. ECAI 2024 : 3244-3251 Mingyu Xiao. Solving Directed Multiway Cut Faster Than 2^n. ESA 2024 : 104:1-104:13 盛子默, 肖鸣宇: Paw图-边删除问题的线性顶点核心化算法. 中国科学: 信息科学 2024 年 第 54 卷 第 7 期: 1604–1619 Ziliang Xiong, Yi Zhou, Mingyu Xiao, Bakhadyr Khoussainov: Finding small feedback arc sets on large graphs. Comput. Oper. Res. 169: 106724 (2024) Ming Sun, Xinyu Wu, Yi Zhou, Jin-Kao Hao, Zhang-Hua Fu. A Partition-and-Merge Algorithm for Solving the Steiner Tree Problem in Large Graphs. COCOON 2024 (accepted) Zihui Liang, Bakh Khoussainov, Haidong Yang. Topological network-control games played on graphs. COCOON 2024 (accepted) Mengfan Ma, Mingyu Xiao, Tian Bai, Xin Cheng. Facility Assignment with Fair Cost Sharing: Equilibrium and Mechanism Design. COCOON 2024 (accepted) Kangyi Tian, Mingyu Xiao, Haotian Pan. A Quadratic Vertex Kernel for Diamond-free Edge Deletion. COCOON 2024 (accepted) Rufan Bai, Chao Xu, Ruilong Zhang, Chenyang Xu. Resource-limited Network Security Games with General Contagious Attacks. COCOON 2024 (accepted) Ke Shi, Chao Xu. Almost optimum 𝑙 -covering of Zn. COCOON 2024 (accepted) Nadim Kasymov, Nadira Karimova, Bakh Khoussainov: Defining algorithmically presented structures in first order logic. LICS 2024 : 47:1-47:13 Toru Takisaka, Libo Zhang, Changjiang Wang, Jiamou Liu: Lexicographic Ranking Supermartingales with Lazy Lower Bounds. CAV (3) 2024 : 420-442 Junqiang Peng, Mingyu Xiao: A Fast Algorithm for MaxSAT Above Half Number of Clauses. IJCAI 2024 :1935-1943 Jingyang Zhao, Mingyu Xiao, Shunwang Wang: Improved Approximation Algorithms for Capacitated Location Routing. IJCAI 2024 : 6805-6813 Jingyang Zhao, Mingyu Xiao: A Better Approximation for Bipartite Traveling Tournament in Inter-League Sports Scheduling. IJCAI 2024 : 6814-6822 Ziliang Xiong, Mingyu Xiao: Exactly Solving Minimum Dominating Set and its Generalization. IJCAI 2024 : 7056-7064 Siyue Liu, Chao Xu: On the Congruency-Constrained Matroid Base. IPCO 2024: 280-293 Jingyang Zhao and Mingyu Xiao: Practical Algorithms with Guaranteed Approximation Ratio for TTP with Maximum Tour Length Two. Mathematics of Operations Research 2024 (accepted) Jingyang Zhao, Mingyu Xiao. A Deterministic Approximation Algorithm for Metric Triangle Packing. Theoretical Computer Science 1010: 114699 (2024) Yuxi Liu and Mingyu Xiao: An Improved Kernel and Parameterized Algorithm for Almost Induced Matching. TAMC 2024 ：86-98 Jingyang Zhao and Mingyu Xiao: An Improved Approximation Algorithm for Metric Triangle Packing. TAMC 2024 : 50-62 Zimo Sheng, Mingyu Xiao: Kernelization for edge triangle packing and covering via a discharging method. Theoretical Computer Science 1004: 114635 (2024) Yuhang Guo, Dong Hao, Mingyu Xiao and Bin Li: Networked Combinatorial Auction for Crowdsourcing and Crowdsensing . IEEE Internet of Things Journal 11(4): 5951-5966 (2024) Lu Liu, Mingyu Xiao, and Yi Zhou: A Fast Exact Solver with Theoretical Analysis for the Maximum Edge-Weighted Clique Problem . AAAI 2024 : 20768-20776 Jingyang Zhao and Mingyu Xiao: Improved Approximation Algorithms for Cycle and Path Packings . WALCOM 2024 : 179-193 Mingyu Xiao, Shen Huang, and Xiaoyu Chen: Maximum Weighted Independent Set: Effective Reductions and Fast Algorithms on Sparse Graphs. Algorithmica 86(5): 1293-1334 (2024) Tian Bai, Mingyu Xiao: Exact algorithms for restricted subset feedback vertex set in chordal and split graphs . Theor. Comput. Sci
2023
Toru Takisaka, Zhenya Zhang, Paolo Arcaini, Ichiro Hasuo: A Robustness-Based Confidence Measure for Hybrid System Falsification, IEEE Trans. Comput. Aided Des. Integr. Circuits Syst 42(5): 1718-1731 (2023) Tian Bai, Mingyu Xiao: A parameterized algorithm for subset feedback vertex set in tournaments . Theor. Comput. Sci. Junqiang Peng, Mingyu Xiao: Further improvements for SAT in terms of formula length . Inf. Comput. 294: 105085 (2023) Jianbo Wang, Chao Xu, Siyun Zhou: Solving systems of linear equations through zero forcing set . COCOON 2023 :353-365. Zihui Liang, Haidong Yang, Bakh Khoussainov: Topological network-control games . COCOON 2023 :144-156. Zimo Sheng, Mingyu Xiao: A Discharging Method: Improved Kernels for Edge Triangle Packing and Covering. COCOON 2023 :171-183. Jingyang Zhao, Mingyu Xiao: Improved Approximation Algorithms for Multidepot Capacitated Vehicle Routing . COCOON 2023 : 378-391. (Best Paper Award) Kangyi Tian, Mingyu Xiao, Boting Yang: An Improved Parameterized Algorithm for Cluster Vertex Deletion. COCOON 2023 :182-194. Zihui Liang, Bakh Khoussainov, Toru Takisaka, Mingyu Xiao: Connectivity in the presence of an opponent . ESA 2023 : 79:1-79:14. Fengjuan Jia, Mengxiao Zhang, Jiamou Liu, Bakh Khoussainov: Incentivising Diffusion while Preserving Differential Privacy . UAI 2023 : 963-972. Yuan Fang, Mengxiao Zhang, Jiamou Liu, Bakh Khoussainov, Mingyu Xiao: Multi-unit Auction over a Social Network . ECAI 2023 : 676-683. Weidong Li, Mengxiao Zhang, Libo Zhang, and Jiamou Liu. Integrated Private Data Trading Systems for Data Marketplaces . ECAI 2023 : 1422-1429. Mingyu Xiao, Guixin Lin, Bakh Khoussainov, Yuchao Song: Characterizations of Network Auctions and Generalizations of VCG . ECAI 2023 : 2736-2743. Zhengren Wang, Zhou Yi, Chunyu Luo, Mingyu Xiao: A Fast Maximum k-Plex Algorithm Parameterized by the Degeneracy Gap. IJCAI 2023 : 5648-5656. Junqiang Peng, Mingyu Xiao: Fast Algorithms for SAT with Bounded Occurrences of Variables . IJCAI 2023 : 2004-2012. Zeyu Zhang, Jiamou Liu, Kaiqi Zhao, Song Yang, Xianda Zheng, Yifei Wang: Contrastive Learning for Signed Bipartite Graphs . SIGIR 2023 : 1629–1638. Mingyu Xiao, Guoliang Qiu, Sen Huang: MMS Allocations of Chores with Connectivity Constraints: New Methods and New Results . AAMAS 2023 : 2886-2888. Fengjuan Jia, Mengxiao Zhang, Jiamou Liu, Bakh Khoussainov: Differentially Private Diffusion Auction: The Single-unit Case . AAMAS 2023 : 2724-2726. Libo Zhang, Yang Chen, Toru Takisaka, Bakh Khoussainov, Michael Witbrock, Jiamou Liu: Learning Density-Based Correlated Equilibria for Markov Games . AAMAS 2023 : 652-660. Mingyu Xiao, Shaowei Kou: A 5k -vertex kernel for 3-path vertex cover. Theor. Comput. Sci Mengfan Ma, Ziyang Men, André Rossi, Yi Zhou, Mingyu Xiao: A vertex-separator-based integer linear programming formulation for the partitioned Steiner tree problem . Comput. Oper. Res. 153: 106151 (2023) Yuhao Liu, Mingyu Xiao. The (3, 3)-colorability of planar graphs without 4-cycles and 5-cycles . Discrete Mathematics . 346(4), 113306 (2023) Jialing He, Zijian Zhang, Liran Ma, Zhouyu Zhang, Meng Li, Bakh Khoussainov, Jiamou Liu, and Liehuang Zhu. InFocus: Amplifying Critical Feature Influence on Non-Intrusive Load Monitoring through Self-Attention Mechanisms . IEEE Trans. Smart Grid. (2023) Mengfan Ma, Mingyu Xiao, Tian Bai, Bakh Khoussainov: Facility Location Games with Entrance Fees . AAAI 2023 : 37(5), 5797-5804. Jingyang Zhao, Mingyu Xiao. The Linear Distance Traveling Tournament Problem Allows an EPTAS . AAAI 2023 : 37(10), 12155-12162. Jialing He, Jiamou Liu, Zijian Zhang, Yang Chen, Yiwei Liu, Bakh Khoussainov, Liehuang Zhu. MSDC: Exploiting Multi-State Power Consumption in Non-Intrusive Load Monitoring Based on A Dual-CNN Model. AAAI 2023 : 37(4), 5078-5086. Dmitry Berdinsky, Sanjay Jain, Bakhadyr Khoussainov, Frank Stephan. String compression in FA–presentable structures. Theor. Comput. Sci. Qi Shi and Dong Hao. Social Sourcing: Incorporating Social Networks Into Crowdsourcing Contest Design . IEEE/ACM Trans. Netw. Early Access 10.1109/TNET.2022.3223367.(2023) Tsuyoshi Hirayama, Yuhao Liu, Kazuhisa Makino, Ke Shi, Chao Xu. A Polynomial Time Algorithm for Finding a Minimum 4-Partition of a Submodular Function . SODA 2023 : 1680-1691 Calvin Beideman, Karthekeyan Chandrasekaran, Chao Xu. Multicriteria cuts and size-constrained k-cuts in hypergraphs . Math. Program. 197(1): 27-69 (2023) Shan Hu, Yi Zhou, Mingyu Xiao, Zhang-Hua Fu, Zhipeng Lü. Listing maximal k-relaxed-vertex connected components from large graphs . Inf. Sci. 620:67-83(2023) Mingyu Xiao. Upper and lower bounds on approximating weighted mixed domination . Theor. Comput. Sci. 939: 292-302 (2023) Mengxiao Zhang, Jiamou Liu, Kaiyu Feng, Fernando Beltran, Zijian Zhang. SmartAuction: A blockchain-based secure implementation of private data queries . Future Gener. Comput. Syst. 138: 198-211 (2023) 2022
Peng Yu, Chao Xu, Albert Bifet, Jesse Read. Linear TreeShap . NeurIPS 2022 Calvin Beideman, Karthekeyan Chandrasekaran, Chandra Chekuri, Chao Xu. Approximate Representation of Symmetric Submodular Functions via Hypergraph Cut Functions . FSTTCS 2022 : 6:1-6:18 Yi Zhou, Shan Hu, Zimo Sheng. Extracting Densest Sub-hypergraph with Convex Edge-Weight Functions . TAMC 2022 : 305-321 Tian Bai, Mingyu Xiao. Exact and Parameterized Algorithms for Restricted Subset Feedback Vertex Set in Chordal Graphs . TAMC 2022 : 249-261 Bakh Khoussainov and Alexander Melnikov. Decomposability and computability . Algebra and Logic . 61(2):153–159 (2022) Jingyang Zhao, Mingyu Xiao, Chao Xu: Improved Approximation Algorithms for the Traveling Tournament Problem . MFCS 2022 : 83:1-83:15 Mingyu Xiao, Jianan Zhang, Weibo Lin. Parameterized algorithms and complexity for the traveling purchaser problem and its variants . J. Comb. Optim. 44(4): 2269-2285 (2022) Bakh Khoussainov, Toru Takisaka. Infinite Strings and their Large Scale Properties . J. Symb. Log. 87(2): 585-625 (2022) Haotian Cao, Hao Yin, Feng Gao, Zijian Zhang, Bakh Khoussainov, Shubin Xu, Liehuang Zhu. Chain-Based Covert Data Embedding Schemes in Blockchain. IEEE Internet Things J . 9(16): 14699-14707 (2022) Jialing He, Zijian Zhang, Jian Mao, Liran Ma, Bakh Khoussainov, Rui Jin, Liehuang Zhu. Video Aficionado. We Know What You Are Watching . IEEE Trans. Mob. Comput . 21(8): 3041-3052 (2022). Mingyu Xiao. An Exact MaxSAT Algorithm: Further Observations and Further Improvements . IJCAI 2022 : 1887-1893. Mingyu Xiao, Yuchao Song, Bakh Khoussainov. Multi-Unit Auction in Social Networks with Budgets . AAAI 2022 : 5228-5235. Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, Frank Stephan: Deciding Parity Games in Quasi-polynomial Time . SIAM J. Comput . 51(2): 17-152 (2022) Binglin Tao, Mingyu Xiao, Bakhadyr Khoussainov, Junqiang Peng. Optimal Shielding to Guarantee Region-Based Connectivity under Geographical Failures . INFOCOM 2022 : 1109-1118 Hao Yin, Zijian Zhang, Jialing He, Liran Ma, Liehuang Zhu, Meng Li, Bakh Khoussainov. Proof of Continuous Work for Reliable Data Storage Over Permissionless Blockchain . IEEE Internet Things J. 9(10): 7866-7875 (2022) Zimo Sheng, Mingyu Xiao. An improved kernel for planar vertex-disjoint triangle packing . Theor. Comput. Sci. 922: 122-130 (2022) Ton Kloks, Mingyu Xiao. A Guide to Graph Algorithms . Springer 2022 , ISBN 978-981-16-6349-9, pp. 1-340. Yan Jin, Bowen Xiong, Kun He, Yangming Zhou, Yi Zhou. On fast enumeration of maximal cliques in large graphs . Expert Syst. Appl. 187: 115915 (2022) Mingyu Xiao, Shaowei Kou. A simple and improved parameterized algorithm for bicluster editing . Inf. Process. Lett. 174: 106193 (2022) Zhengren Wang, Yi Zhou, Mingyu Xiao, Bakhadyr Khoussainov. Listing Maximal k-Plexes in Large Real-World Graphs . WWW 2022 : 1517-1527 Yi ZhouAn effective branch-and-bound algorithm for the maximum s-bundle problem . Eur. J. Oper. Res. 297(1):27-39 (2022) 2021
Sen Huang, Mingyu Xiao and Xiaoyu Chen. Exact algorithms for maximum weighted independent set on sparse graphs . COCOON 2021 : 617-628 Jingyang Zhao and Mingyu Xiao. A Further Improvement on Approximating TTP-2 . COCOON 2021 : 137-149 Huairui Chu, Mingyu Xiao, and Zhe Zhang. An improved upper bound for SAT . Theor. Comput. Sci. 887: 51-62 (2021) Yiwei Liu, Jiamou Liu, Kaibin Wan, Zhan Qin, Zijian Zhang, Bakh Khoussainov, Liehuang Zhu. From Local to Global Norm Emergence: Dissolving Self-reinforcing Substructures with Incremental Social Instruments . ICML 2021 : 6871-6881 Jingyang Zhao, Mingyu Xiao. The Traveling Tournament Problem with Maximum Tour Length Two: A Practical Algorithm with An Improved Approximation Bound . IJCAI 2021 : 4206-4212 Amir Hossein Gharehgozli, Chao Xu, Wenda Zhang. High multiplicity asymmetric traveling salesman problem with feedback vertex set and its application to storage/retrieval system . Eur. J. Oper. Res. 289(2): 495-507 (2021) Karthekeyan Chandrasekaran, Chao Xu, Xilin Yu. Hypergraph k-cut in randomized polynomial time . Math. Program. 186(1): 85-113 (2021) Junqiang Peng, Mingyu Xiao. A Fast Algorithm for SAT in Terms of Formula Length . SAT 2021 : 436-452 Mingyu Xiao, Sen Huang, Yi Zhou, Bolin Ding. Efficient Reductions and a Fast Algorithm of Maximum Weighted Independent Set . WWW 2021 : 3930-3940 Yi Zhou, Shan Hu, Mingyu Xiao, Zhang-Hua Fu. Improving Maximum k-plex Solver via Second-Order Reduction and Graph Color Bounding . AAAI 2021 : 12453-12460 Zhenyu Guo, Mingyu Xiao, Yi Zhou, Dongxiang Zhang, Kian-Lee Tan. Enhancing Balanced Graph Edge Partition with Effective Local Search . AAAI 2021 : 12336-12343 Huairui Chu, Mingyu Xiao, Zhe Zhang. An Improved Upper Bound for SAT . AAAI 2021 : 3707-3714 Xiaoyu Chen, Yi Zhou, Jin-Kao Hao. Mingyu Xiao. Computing maximum k-defective cliques in massive graphs . Comput. Oper. Res. 127: 105131 (2021) 2020
Zijian Zhang, Nurilla Avazov, Jiamou Liu, Bakh Khoussainov, Xin Li, Keke Gai, Liehuang Zhu. WiPOS: A POS Terminal Password Inference System Based on Wireless Signals . IEEE Internet Things J. 7(8): 7506-7516 (2020) Shaoyuan Liu, Zhi Fang, Feng Gao, Bakh Khoussainov, Zijian Zhang, Jiamou Liu, Liehuang Zhu. Whispers on Ethereum: Blockchain -based Covert Data Embedding Schemes . BSCI 2020 : 171-179 Moses Ganardi, Bakhadyr Khoussainov. Automatic Equivalence Structures of Polynomial Growth . CSL 2020 : 21:1-21:16 Binglin Tao, Mingyu Xiao, Jingyang Zhao. Finding Minimum-Weight Link-Disjoint Paths with a Few Common Nodes . AAAI 2020 : 938-945 Yi Zhou, Jingwei Xu, Zhenyu Guo, Mingyu Xiao, Yan Jin. Enumerating Maximal k-Plexes with Worst-Case Time Guarantee . AAAI 2020 : 2442-2449 Sen Huang, Mingyu Xiao. Object reachability via swaps under strict and weak preferences . Auton. Agents Multi Agent Syst. 34(2): 51 (2020) Mingyu Xiao, Hiroshi Nagamochi. Characterizing Star-PCGs . Algorithmica 82(10): 3066-3090 (2020) Mingyu Xiao, Hiroshi Nagamochi. Some reduction operations to pairwise compatibility graphs . Inf. Process. Lett. 153 (2020) Qiuxia Lai, Yongwei Nie, Hanqiu Sun, Qiang Xu, Zhensong Zhang, Mingyu Xiao. Video super-resolution via pre-frame constrained and deep-feature enhanced sparse reconstruction . Pattern Recognit. 100: 107139 (2020) Mingyu Xiao, Zimo Sheng. Improved parameterized algorithms and kernels for mixed domination . Theor. Comput. Sci. 815: 109-120 (2020) Mingyu Xiao, Shaowei Kou. Parameterized algorithms and kernels for almost induced matching . Theor. Comput. Sci. 846: 103-113 (2020) Zhensong Zhang, Yongwei Nie, Hanqiu Sun, Qing Zhang, Qiuxia Lai, Guiqing Li, Mingyu Xiao. Multi-View Video Synopsis via Simultaneous Object-Shifting and View-Switching Optimization . IEEE Trans. Image Process. 29: 971-985 (2020) Mingyu Xiao, Jiaxing Ling. Algorithms for Manipulating Sequential Allocation . AAAI 2020 : 2302-2309 Zhenyu Guo, Mingyu Xiao, Yi Zhou. The Complexity of the Partition Coloring Problem . TAMC 2020 : 390-401