notesum.ai

Published at December 5

cs.DS

Released Date: December 5, 2024

Authors: Tatsuya Gima¹, Yuni Iwamasa², Yasuaki Kobayashi¹, Kazuhiro Kurita³, Yota Otachi³, Rin Saito⁴

Aff.: ¹Hokkaido University; ²Kyoto University; ³Nagoya University; ⁴Tohoku University

Diverse Pair of Solutions

(

|\alpha_{1}{\mathbin{\triangle}}\alpha_{2}|\geq d

)

Dissimilar Pair of Solutions

(

|\alpha_{1}{\mathbin{\triangle}}\alpha_{2}|\geq|X|-s

)

2SAT

W[1]-hard (Thm. 3) and XP

FPT (Thm. 4)

Horn SAT

W[1]-hard (Thm. 3) and XP

NP-hard with

s=0

(Thm. 2)

Dual Horn SAT

W[1]-hard (Thm. 3) and XP

NP-hard with

s=0

(Thm. 2)

XOR SAT

FPT (Thm. 5)

W[1]-hard (Thm. 5) and XP