{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T04:19:18Z","timestamp":1772252358735,"version":"3.50.1"},"reference-count":14,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2020,12,3]],"date-time":"2020-12-03T00:00:00Z","timestamp":1606953600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100015269","name":"Magyarorsz\u00e1g Korm\u00e1nya","doi-asserted-by":"publisher","award":["GINOP-2.1.2-8-1-4-16-2017-00176"],"award-info":[{"award-number":["GINOP-2.1.2-8-1-4-16-2017-00176"]}],"id":[{"id":"10.13039\/501100015269","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In a previous paper we defined the black and white SAT problem which has exactly two solutions, where each variable is either true or false. We showed that black and white 2-SAT problems represent strongly connected directed graphs. We presented also the strong model of communication graphs. In this work we introduce two new models, the weak model, and the Balatonbogl\u00e1r model of communication graphs. A communication graph is a directed graph, where no self loops are allowed. In this work we show that the weak model of a strongly connected communication graph is a black and white SAT problem. We prove a powerful theorem, the so called transitions theorem. This theorem states that for any model which is between the strong and the weak model, we have that this model represents strongly connected communication graphs as black and white SAT problems. We show that the Balatonbogl\u00e1r model is between the strong and the weak model, and it generates 3-SAT problems, so the Balatonbogl\u00e1r model represents strongly connected communication graphs as black and white 3-SAT problems. Our motivation to study these models is the following: The strong model generates a 2-SAT problem from the input directed graph, so it does not give us a deep insight how to convert a general SAT problem into a directed graph. The weak model generates huge models, because it represents all cycles, even non-simple cycles, of the input directed graph. We need something between them to gain more experience. From the Balatonbogl\u00e1r model we learned that it is enough to have a subset of a clause, which represents a cycle in the weak model, to make the Balatonbogl\u00e1r model more compact. We still do not know how to represent a SAT problem as a directed graph, but this work gives a strong link between two prominent fields of formal methods: the SAT problem and directed graphs.<\/jats:p>","DOI":"10.3390\/a13120321","type":"journal-article","created":{"date-parts":[[2020,12,3]],"date-time":"2020-12-03T11:15:43Z","timestamp":1606994143000},"page":"321","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Convert a Strongly Connected Directed Graph to a Black-and-White 3-SAT Problem by the Balatonbogl\u00e1r Model"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6969-1629","authenticated-orcid":false,"given":"G\u00e1bor","family":"Kusper","sequence":"first","affiliation":[{"name":"Faculty of Informatics, Eszterh\u00e1zy K\u00e1roly University, 3300 Eger, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8561-9141","authenticated-orcid":false,"given":"Csaba","family":"Bir\u00f3","sequence":"additional","affiliation":[{"name":"Faculty of Informatics, Eszterh\u00e1zy K\u00e1roly University, 3300 Eger, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,12,3]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"755","DOI":"10.18514\/MMN.2018.2140","article-title":"Equivalence of Strongly Connected Graphs and Black-and-White 2-SAT Problems","volume":"19","author":"Kusper","year":"2018","journal-title":"Miskolc Math. Notes"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","article-title":"A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean Formulas","volume":"8","author":"Aspvall","year":"1979","journal-title":"Inf. Process. Lett."},{"key":"ref_3","unstructured":"Balla, T., Bir\u00f3, C., and Kusper, G. (2020, January 11\u201317). The BWConverter Toolchain: An Incomplete Way to Convert SAT Problems into Directed Graphs. Proceedings of the ICAI 2020, Yokohama, Japan."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Langlands, R.P. (1970). Problems in the theory of automorphic forms to Salomon Bochner in gratitude. Lectures in Modern Analysis and Applications III, Springer.","DOI":"10.1007\/BFb0079065"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1007\/BF01361551","article-title":"Uber die Bestimmung Dirichletscher Reihen durch Funktionalgleichungen","volume":"168","author":"Weil","year":"1967","journal-title":"Math. Ann."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"443","DOI":"10.2307\/2118559","article-title":"Modular elliptic curves and Fermat\u2019s Last Theorem","volume":"141","author":"Wiles","year":"1995","journal-title":"Ann. Math"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Hellerman, L. (1963). A Catalog of Three-Variable Or-Invert and And-Invert Logical Circuits. IEEE Trans. Electron. Comput., 198\u2013223.","DOI":"10.1109\/PGEC.1963.263531"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1109\/TC.1986.1676819","article-title":"Graph-Based Algorithms for Boolean Function Manipulation","volume":"100","author":"Bryant","year":"1986","journal-title":"IEEE Trans. Comput."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Minato, S. (1993, January 14\u201318). Zero-suppressed BDDs for Set Manipulation in Combinatorial Problems. Proceedings of the 30th International Design Automation Conference, Dallas, TX, USA.","DOI":"10.1145\/157485.164890"},{"key":"ref_10","unstructured":"Hearn, R.A. (2006). Games, Puzzles, and Computation. [Ph.D. Thesis, Massachusetts Institute of Technology]."},{"key":"ref_11","first-page":"57","article-title":"Truth-teller-liar puzzles and their graphs","volume":"11","author":"Nagy","year":"2003","journal-title":"Cent. Eur. J. Oper. Res."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Kusper, G., Balla, T., Bir\u00f3, C., Tajti, T., Yang, Z.G., and Baj\u00e1k, I. (2020, January 1\u20134). Generating Minimal Unsatisfiable SAT Instances from Strong Digraphs. Proceedings of the 2020 22nd International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, Timisoara, Romania.","DOI":"10.1109\/SYNASC51798.2020.00024"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Bir\u00f3, C., and Kusper, G. (2018, January 21\u201322). BaW 1.0-A Problem Specific SAT Solver for Effective Strong Connectivity Testing in Sparse Directed Graphs. Proceedings of the IEEE 18th International Symposium on Computational Intelligence and Informatics (CINTI 2018), Budapest, Hungary.","DOI":"10.1109\/CINTI.2018.8928191"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Kusper, G., Bir\u00f3, C., and Balla, T. (2020, January 21\u201323). Investigation of the Efficiency of Conversion of Directed Graphs to 3-SAT Problems. Proceedings of the 2020 IEEE 14th International Symposium on Applied Computational Intelligence and Informatics (SACI), Timisoara, Romania.","DOI":"10.1109\/SACI49304.2020.9118786"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/12\/321\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:40:59Z","timestamp":1760179259000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/12\/321"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,3]]},"references-count":14,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2020,12]]}},"alternative-id":["a13120321"],"URL":"https:\/\/doi.org\/10.3390\/a13120321","relation":{"has-preprint":[{"id-type":"doi","id":"10.20944\/preprints202011.0214.v1","asserted-by":"object"}]},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,3]]}}}