2026-09-18T18:53:26Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/110504 2023-07-11 col_2142_5131 col_2142_16340 com_2142_5130 com_2142_16339 com_2142_8903

Hirani, Anil N Dunfield, Nathan M Baryshnikov, Yuliy Tserunyan, Anush Karve, Vaibhav 2021-09-17T01:11:03Z 2021-09-17T01:11:03Z 2021-04-21 2021-05 The presented research is an introduction and analysis of a novel graph decision problem called GraphSAT. Using the tools of topology and graph theory, this new variant builds upon the classical logic and computer science problem of boolean satisfiability k-SAT. k-SAT asks if there exists a truth assignment that satisfies a given boolean formula. Our variant deals with multi-hypergraphs instead of boolean formulae and uses truth assignments on vertices instead of variables. This graph-theoretic picture helps us explore and exploit patterns in unsatisfiable instances of k-SAT, which in turn helps us identify minimal obstruction sets to graph satisfiability. Historically, k-SAT (for k≥3) was the first problem that was proven to be NP-complete, independently by Cook and Levin, making it central to the study of algorithms and computational complexity. We shed new light on k-SAT by analyzing GraphSAT. We demonstrate that 2-GraphSAT is in complexity class P and has a finite obstruction set containing four simple graphs. Further, our exploration of 3-GraphSAT gives rise to the local graph rewriting theorem, which leverages the fact that taking a union over all possible vertex-assignments preserves the satisfiability status of a graph. Using this theorem, we generate a list of graph reduction rules and an incomplete list of obstructions to satisfiability of looped-multi-hypergraphs. A part of this research, especially the search for unsatisfiable instances of GraphSAT, was carried out using computational tools. Hence, some results are aided by a Python package specifically written to carry out computations on multi-hypergraph instances and implement the local rewriting algorithm. These computational steps are included in the thesis in the form of code blocks to give a glimpse of the back-end. Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2021-09-16 without embargo terms The student, Vaibhav Karve, accepted the attached license on 2021-04-19 at 12:29. The student, Vaibhav Karve, submitted this Dissertation for approval on 2021-04-19 at 13:01. This Dissertation was approved for publication on 2021-04-21 at 10:21. DSpace SAF Submission Ingestion Package generated from Vireo submission #16409 on 2021-09-16 at 16:43:08 Made available in DSpace on 2021-09-17T01:11:03Z (GMT). No. of bitstreams: 4 KARVE-DISSERTATION-2021.pdf: 9548194 bytes, checksum: be505880f31211583e873c0772b17d49 (MD5) source_files_20210421.zip: 18063704 bytes, checksum: b930551d4c9551dadc4b0133be2b18fa (MD5) LICENSE.txt: 4210 bytes, checksum: fe2a663fa37ec3596b25bead87928c42 (MD5) PROQUEST_LICENSE.txt: 4556 bytes, checksum: 7713e547ad45e88896976607b80a7732 (MD5) Previous issue date: 2021-04-21 application/pdf http://hdl.handle.net/2142/110504 en Copyright 2021 Vaibhav Karve boolean satisfiability satisfiability graph theory logic graphs hypergraphs python graphsat kSAT 3SAT NP-complete Graphical structure of unsatisfiable boolean formulae text Thesis Mathematics Mathematics University of Illinois at Urbana-Champaign Dissertation Ph.D.