PACE Solver Description: Hust-Solver – A Heuristic Algorithm of Directed Feedback Vertex Set Problem

YuMing Du; QingYun Zhang; JunZhou Xu; ShunGen Zhang; Chao Liao; ZhiHuai Chen; ZhiBo Sun; ZhouXing Su; JunWen Ding; Chen Wu; PinYan Lu; ZhiPeng Lv

doi:10.4230/LIPIcs.IPEC.2022.29

PACE Solver Description: Hust-Solver – A Heuristic Algorithm of Directed Feedback Vertex Set Problem

YuMing Du
, QingYun Zhang
, JunZhou Xu
, ShunGen Zhang
, Chao Liao
, ZhiHuai Chen
, ZhiBo Sun
, ZhouXing Su
, JunWen Ding
, Chen Wu
, PinYan Lu
, ZhiPeng Lv

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

1 Citation (Scopus)

1 Downloads (CityUHK Scholars)

Abstract

A directed graph is formed by vertices and arcs from one vertex to another. The feedback vertex set problem (FVSP) consists in making a given directed graph acyclic by removing as few vertices as possible. In this write-up, we outline the core techniques used in the heuristic feedback vertex set algorithm, submitted to the heuristic track of the 2022 PACE challenge. © YuMing Du, QingYun Zhang, JunZhou Xu, ShunGen Zhang, Chao Liao, ZhiHuai Chen, ZhiBo Sun, ZhouXing Su, JunWen Ding, Chen Wu, PinYan Lu, and ZhiPeng Lv.

Original language	English
Title of host publication	17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Editors	Holger Dell, Jesper Nederlof
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Number of pages	3
ISBN (Print)	978-3-95977-260-0
DOIs	https://doi.org/10.4230/LIPIcs.IPEC.2022.29
Publication status	Published - 2022
Externally published	Yes
Event	17th International Symposium on Parameterized and Exact Computation (IPEC 2022) - Potsdam, Germany Duration: 7 Sept 2022 → 9 Sept 2022 https://www.dagstuhl.de/dagpub/978-3-95977-260-0

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	249
ISSN (Print)	1868-8969

Conference

Conference	17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Place	Germany
City	Potsdam
Period	7/09/22 → 9/09/22
Internet address	https://www.dagstuhl.de/dagpub/978-3-95977-260-0

Research Keywords

directed feedback vertex set
local search
set covering
simulated annealing

Publisher's Copyright Statement

This full text is made available under CC-BY 4.0. https://creativecommons.org/licenses/by/4.0/

Access Output

10.4230/LIPIcs.IPEC.2022.29

485983867.pdfFinal Published version, 395 KBLicence: CC BY

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Du, Y., Zhang, Q., Xu, J., Zhang, S., Liao, C., Chen, Z., Sun, Z., Su, Z., Ding, J., Wu, C., Lu, P., & Lv, Z. (2022). PACE Solver Description: Hust-Solver – A Heuristic Algorithm of Directed Feedback Vertex Set Problem. In H. Dell, & J. Nederlof (Eds.), 17th International Symposium on Parameterized and Exact Computation (IPEC 2022) Article 29 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 249). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.IPEC.2022.29

Du, YuMing ; Zhang, QingYun ; Xu, JunZhou et al. / PACE Solver Description : Hust-Solver – A Heuristic Algorithm of Directed Feedback Vertex Set Problem. 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). editor / Holger Dell ; Jesper Nederlof. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2022. (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{8cf2d647bc674138a1649089b9a989c1,

title = "PACE Solver Description: Hust-Solver – A Heuristic Algorithm of Directed Feedback Vertex Set Problem",

abstract = "A directed graph is formed by vertices and arcs from one vertex to another. The feedback vertex set problem (FVSP) consists in making a given directed graph acyclic by removing as few vertices as possible. In this write-up, we outline the core techniques used in the heuristic feedback vertex set algorithm, submitted to the heuristic track of the 2022 PACE challenge. {\textcopyright} YuMing Du, QingYun Zhang, JunZhou Xu, ShunGen Zhang, Chao Liao, ZhiHuai Chen, ZhiBo Sun, ZhouXing Su, JunWen Ding, Chen Wu, PinYan Lu, and ZhiPeng Lv.",

keywords = "directed feedback vertex set, local search, set covering, simulated annealing",

author = "YuMing Du and QingYun Zhang and JunZhou Xu and ShunGen Zhang and Chao Liao and ZhiHuai Chen and ZhiBo Sun and ZhouXing Su and JunWen Ding and Chen Wu and PinYan Lu and ZhiPeng Lv",

year = "2022",

doi = "10.4230/LIPIcs.IPEC.2022.29",

language = "English",

isbn = "978-3-95977-260-0",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "Dell, \{Holger \} and Jesper Nederlof",

booktitle = "17th International Symposium on Parameterized and Exact Computation (IPEC 2022)",

address = "Germany",

note = "17th International Symposium on Parameterized and Exact Computation (IPEC 2022) ; Conference date: 07-09-2022 Through 09-09-2022",

url = "https://www.dagstuhl.de/dagpub/978-3-95977-260-0",

}

Du, Y, Zhang, Q, Xu, J, Zhang, S, Liao, C, Chen, Z, Sun, Z, Su, Z, Ding, J, Wu, C, Lu, P & Lv, Z 2022, PACE Solver Description: Hust-Solver – A Heuristic Algorithm of Directed Feedback Vertex Set Problem. in H Dell & J Nederlof (eds), 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)., 29, Leibniz International Proceedings in Informatics, LIPIcs, vol. 249, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022), Potsdam, Germany, 7/09/22. https://doi.org/10.4230/LIPIcs.IPEC.2022.29

PACE Solver Description: Hust-Solver – A Heuristic Algorithm of Directed Feedback Vertex Set Problem. / Du, YuMing; Zhang, QingYun; Xu, JunZhou et al.
17th International Symposium on Parameterized and Exact Computation (IPEC 2022). ed. / Holger Dell; Jesper Nederlof. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2022. 29 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 249).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - PACE Solver Description

T2 - 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

AU - Du, YuMing

AU - Zhang, QingYun

AU - Xu, JunZhou

AU - Zhang, ShunGen

AU - Liao, Chao

AU - Chen, ZhiHuai

AU - Sun, ZhiBo

AU - Su, ZhouXing

AU - Ding, JunWen

AU - Wu, Chen

AU - Lu, PinYan

AU - Lv, ZhiPeng

PY - 2022

Y1 - 2022

N2 - A directed graph is formed by vertices and arcs from one vertex to another. The feedback vertex set problem (FVSP) consists in making a given directed graph acyclic by removing as few vertices as possible. In this write-up, we outline the core techniques used in the heuristic feedback vertex set algorithm, submitted to the heuristic track of the 2022 PACE challenge. © YuMing Du, QingYun Zhang, JunZhou Xu, ShunGen Zhang, Chao Liao, ZhiHuai Chen, ZhiBo Sun, ZhouXing Su, JunWen Ding, Chen Wu, PinYan Lu, and ZhiPeng Lv.

AB - A directed graph is formed by vertices and arcs from one vertex to another. The feedback vertex set problem (FVSP) consists in making a given directed graph acyclic by removing as few vertices as possible. In this write-up, we outline the core techniques used in the heuristic feedback vertex set algorithm, submitted to the heuristic track of the 2022 PACE challenge. © YuMing Du, QingYun Zhang, JunZhou Xu, ShunGen Zhang, Chao Liao, ZhiHuai Chen, ZhiBo Sun, ZhouXing Su, JunWen Ding, Chen Wu, PinYan Lu, and ZhiPeng Lv.

KW - directed feedback vertex set

KW - local search

KW - set covering

KW - simulated annealing

UR - http://www.scopus.com/inward/record.url?scp=85144177658&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85144177658&origin=recordpage

U2 - 10.4230/LIPIcs.IPEC.2022.29

DO - 10.4230/LIPIcs.IPEC.2022.29

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 978-3-95977-260-0

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

A2 - Dell, Holger

A2 - Nederlof, Jesper

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

Y2 - 7 September 2022 through 9 September 2022

ER -

Du Y, Zhang Q, Xu J, Zhang S, Liao C, Chen Z et al. PACE Solver Description: Hust-Solver – A Heuristic Algorithm of Directed Feedback Vertex Set Problem. In Dell H, Nederlof J, editors, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2022. 29. (Leibniz International Proceedings in Informatics, LIPIcs). Epub 2022 Dec 14. doi: 10.4230/LIPIcs.IPEC.2022.29

PACE Solver Description: Hust-Solver – A Heuristic Algorithm of Directed Feedback Vertex Set Problem

Abstract

Publication series

Conference

Research Keywords

Publisher's Copyright Statement

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this