A Contraction Tree SAT Encoding for Computing Twin-Width

被引：0

作者：

Horev, Yinon ^{[1
]}

Shay, Shiraz ^{[1
]}

Cohen, Sarel ^{[1
]}

Friedrich, Tobias ^{[2
]}

Issac, Davis ^{[2
]}

Kamma, Lior ^{[1
]}

Niklanovits, Aikaterini ^{[2
]}

Simonov, Kirill ^{[2
]}

机构：

[1] Acad Coll Tel Aviv Yaffo, Tel Aviv, Israel

[2] Univ Potsdam, Hasso Plattner Inst, Potsdam, Germany

来源：

ADVANCES IN KNOWLEDGE DISCOVERY AND DATA MINING, PT II, PAKDD 2024 | 2024年 / 14646卷

关键词：

Twin-width; SAT encoding;

D O I：

10.1007/978-981-97-2253-2_35

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Twin-width is a structural width parameter and matrix invariant introduced by Bonnet et al. [FOCS 2020], that has been gaining attention due to its various fields of applications. In this paper, inspired by the SAT approach of Schidler and Szeider [ALENEX 2022], we provide a new SAT encoding for computing twin-width. The encoding aims to encode the contraction sequence as a binary tree. The asymptotic size of the formula under our encoding is smaller than in the state-of-the-art relative encoding of Schidler and Szeider. We also conduct an experimental study, comparing the performance of the new encoding and the relative encoding.

引用

页码：444 / 456

页数：13

共 14 条

[1] Balaban J., LEIBNIZ INT P INFORM, V214
[2] Berge P., 2022, LIPICS, V229
[3] Bonnet E., LEIBNIZ INT P INFORM, V214
[4] Twin-width can be exponential in treewidth
Bonnet, Edouard
Depres, Hugues
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2023, 161 : 1 - 14
[5] Twin-width I: Tractable FO Model Checking
Bonnet, Edouard
Kim, Eun Jung
Thomasse, Stephan
Watrigant, Remi
[J]. JOURNAL OF THE ACM, 2022, 69 (01)
[6] Bonnet E, 2021, Disc Algorithms, P1977
[7] Bonnet Edouard, 2021, LIPICS, V198, P35, DOI DOI 10.4230/LIPICS.ICALP.2021.35
[8] Guillemot S., 2014, P 25 ANN ACM SIAM S, P82, DOI [10.1137/1.9781611973402.7, DOI 10.1137/1.9781611973402.7]
[9] Bounding Twin-Width for Bounded-Treewidth Graphs, Planar Graphs, and Bipartite Graphs
Jacob, Hugo
Pilipczuk, Marcin
[J]. GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE (WG 2022), 2022, 13453 : 287 - 299
[10] Planar graph with twin-width seven
Kral, Daniel
Lamaison, Ander
[J]. EUROPEAN JOURNAL OF COMBINATORICS, 2025, 123

← 1 2 →