Author name cluster

Pu Wu

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

TCS Journal 2026 Journal Article

A space improved algorithm for chromatic number

Pu Wu
Huanyu Gu
Huiqin Jiang
Zehui Shao
Jin Xu

We investigate the chromatic number problem, a classic NP-complete problem identified by Karp among his 21 seminal problems. The chromatic number of a graph G is the smallest integer k such that each vertex of G can be assigned one of k colors, with no two adjacent vertices assigned the same color. The chromatic number problem requires determining this minimum k for a given graph G with n vertices. The questions of whether an algorithm for the chromatic number problem with time complexity O * ( a n ), where a < 2, exists, and whether an algorithm for the chromatic number problem with time complexity O * ( 2 n ) and polynomial space exists, both remain unresolved. The fastest known algorithm for the chromatic number problem was proposed by Björklund, Husfeldt, and Koivisto (FOCS 2006), with the time and space complexity of O * ( 2 n ). Subsequently, in their follow-up work (ICALP 2010), the space complexity is reduced to O ( 1. 2916 n ). In this work, we present an improved algorithm for the chromatic number problem. Building on prior research, our approach leverages algebraic methods, specifically the generating functions and the discrete Fourier transform. Our main contribution demonstrates that by utilizing these algebraic techniques, certain structural properties of graphs can be exploited to reduce space complexity, while preserving the best-known time complexity of O * ( 2 n ). Specifically, our algorithm achieves a time complexity of O * ( 2 n ) and a space complexity of O * ( 2 9 n 25 ) = O ( 1. 2835 n ).

Details DOI

AAAI Conference 2026 Conference Paper

Exact Optimization for Minimum Dominating Sets

Enqiang Zhu
Qiqi Bao
Yu Zhang
Chanjuan Liu
Pu Wu

The Minimum Dominating Set (MDS) problem is a well-established combinatorial optimization problem with numerous real-world applications. Its NP-hard nature makes it increasingly difficult to obtain exact solutions as the graph size grows. This paper introduces ParDS, an exact algorithm developed to address the MDS problem within the branch-and-bound framework. ParDS features two key innovations: an advanced linear programming technique that yields tighter lower bounds and a set of novel reduction rules that dynamically simplify instances throughout the solving process. Compared to the leading exact algorithms presented at IJCAI 2023 and 2024, ParDS demonstrates theoretically superior lower-bound quality. Experimental results on standard benchmark datasets highlight several significant advantages of ParDS: it achieves fastest solving times in 70% of graph categories, especially on large, sparse graphs, delivers a speed-up of up to 3,411 times on the fastest individual instance, and successfully solves 16 out of 43 instances that other algorithms were unable to resolve within the 5-hour time limit. These findings establish ParDS as a state-of-the-art solution for exactly solving the MDS problem

PDF Details DOI

NeurIPS Conference 2025 Conference Paper

Photography Perspective Composition: Towards Aesthetic Perspective Recommendation

Lujian Yao
Siming Zheng
Xinbin Yuan
Zhuoxuan Cai
Pu Wu
Jinwei Chen
Bo Li
Peng-tao Jiang

Traditional photography composition approaches are dominated by 2D cropping-based methods. However, these methods fall short when scenes contain poorly arranged subjects. Professional photographers often employ perspective adjustment as a form of 3D recomposition, modifying the projected 2D relationships between subjects while maintaining their actual spatial positions to achieve better compositional balance. Inspired by this artistic practice, we propose photography perspective composition (PPC), extending beyond traditional cropping-based methods. However, implementing the PPC faces significant challenges: the scarcity of perspective transformation datasets and undefined assessment criteria for perspective quality. To address these challenges, we present three key contributions: (1) An automated framework for building PPC datasets through expert photographs. (2) A video generation approach that demonstrates the transformation process from less favorable to aesthetically enhanced perspectives. (3) A perspective quality assessment (PQA) model constructed based on human performance. Our approach is concise and requires no additional prompt instructions or camera trajectories, helping and guiding ordinary users to enhance their composition skills.

PDF Details