Speaker:
Ziliang Xiong(University of Electronic and Science Technology of China)
Time:
- 10:00-12:00 (Time in Beijing)
- 14:00-16:00 (Time in Auckland)
- April 9, 2021 (Friday)
VooVmeeting:
Link: https://meeting.tencent.com/s/4780kEVEoRgF
ID: 381 139 951
Venue:
B1-514, Main Building
Abstract:
Given a digraph, the minimum feedback arc set problem asks to find the smallest arc set whose removal makes the graph acyclic.
The problem is important in many application domains such as circuit design, graph visualization, and social networks. Theoretically,
the problem is computational challenging. In the paper, we turn to practical heuristic algorithms that solve the minimum feedback arc
set problem in reasonable time and with high accuracy. By exploiting graph structures, we propose a near-linear time reduction procedure
which reduces the scale of input graph without missing optimality. Importantly, the procedure finds optimal solutions for more than 80% of
the well-known ISCAS circuit graphs in less than one second. We also develop a O(m logn)-time divide-and-conquer heuristic for solving the
problem after reduction, where m and n are the number of vertices and arcs, respectively. Experiments on a wide range of large real-world graphs
demonstrate that the algorithm that combines the reduction and heuristic search achieves the state-of-the-art.