Abstract
XSAT is defined as the following: Given a propositional formula in conjunctive normal form, can one find an assignment to variables such that there is exactly only 1 literal that is true in every clause, while the other literals are false. The decision problem XSAT is known to be NPcomplete. Crescenzi and Rossi [Pierluigi Crescenzi and Gianluca Rossi, 2002] introduced the variant where one searches for a pair of two solutions of an X3SAT instance with maximal Hamming Distance among them, that is, one wants to identify the largest number k such that there are two solutions of the instance with Hamming Distance k. Dahllöf [Vilhelm Dahllöf, 2005; Vilhelm Dahllöf, 2006] provided an algorithm using branch and bound method for Max Hamming Distance XSAT in O(1.8348^n); Fu, Zhou and Yin [Linlu Fu and Minghao Yin, 2012] worked on a more specific problem, the Max Hamming Distance X3SAT, and found for this problem an algorithm with runtime O(1.6760^n). In this paper, we propose an exact exponential algorithm to solve the Max Hamming Distance XSAT problem in O(1.4983^n) time. Like all of them, we will use the branch and bound technique alongside a newly defined measure to improve the analysis of the algorithm.
BibTeX  Entry
@InProceedings{hoi_et_al:LIPIcs:2019:11511,
author = {Gordon Hoi and Frank Stephan},
title = {{Measure and Conquer for Max Hamming Distance XSAT}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {15:115:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771306},
ISSN = {18688969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11511},
URN = {urn:nbn:de:0030drops115119},
doi = {10.4230/LIPIcs.ISAAC.2019.15},
annote = {Keywords: XSAT, Measure and Conquer, DPLL, Exponential Time Algorithms}
}
Keywords: 

XSAT, Measure and Conquer, DPLL, Exponential Time Algorithms 
Collection: 

30th International Symposium on Algorithms and Computation (ISAAC 2019) 
Issue Date: 

2019 
Date of publication: 

28.11.2019 