Show simple item record

AuthorScharpfenecker, Patrickdc.contributor.author
Date of accession2017-06-20T13:03:20Zdc.date.accessioned
Available in OPARU since2017-06-20T13:03:20Zdc.date.available
Year of creation2017dc.date.created
Date of first publication2017-06-20dc.date.issued
AbstractSuccinct encodings are short descriptions of relations such that the relation itself may be of size exponential in the size of its description. We can encode graphs, which are binary relations over a set of vertices, by circuits, formulas, OBDDs and other models of computation which store a truth-table. This dissertation studies two common types of succinct encodings on graphs: 1. The set of edges and vertices are given by a succinct description. We call such encodings the standard succinct encoding. 2. The set of vertices is given by a succinct description and the edge-set is defined by a fixed host-graph. If the host graph is the n-dimensional hypercube, such encodings are called solution graphs. For many years, all studied computational problems under the standard succinct encoding were shown to be exponentially harder than their explicit counterparts. These complexity blow-ups have been proved using so called upward-translation theorems, which show that specific low-level reductions between computational problems can be adapted to polynomial-time reductions between their succinct counterparts. We extend this work by studying succinct graph problems under more restricted encodings such as bounded-depth circuits and identify the hidden structure of these graphs as the alternating union and intersection of complete bipartite graphs. This structure can be used to show that CNF- and DNF-formulas are succinct encodings for which not all computational problems have an exponential complexity blow-up. We give the first known examples of decision problems under restricted types of standard succinct encodings that are not computationally harder than their explicit versions (STCONN on DNF-encoded graphs) or which get an intermediate blow-up (DS on DNF-encoded graphs). Using these exceptions, there cannot exist upward-translation theorems for CNF- and DNF-succinct encodings unless the used low-level reduction separates Clique and CNFSAT, proving there are no upward-translation theorems for logarithmic-space reductions and CNF-/DNF-encodings. By contrast, we prove such upward-translation theorems for circuits of depth 3, yielding a threshold for the existence of such theorems. We further show how to adapt these results to explicitly given graphs and define a hierarchy of graph classes for which the second level is strong enough for all NP-complete graph problems to stay NP-complete on graphs in this class. Furthermore, for graphs in the first level, DS has a sub-exponential time algorithm and the graph isomorphism problem is already GI-complete on these graphs. For solution graphs, we refine the known classification of the complexity of USTCONN and extend the known structural results on such graphs. We show that for a class of formulas called CPSS, all connected components of encoded graphs are partial cubes, while outside of this class this property does not hold. Still, even for the larger class of so called safely tight formulas, USTCONN can be reduced to the satisfiability problem on related formulas. Our results imply that USTCONN on 2CNF solution graphs is NL-complete. We apply our structural results to GI on 2CNF solution graphs and show that this problem is C_=P-complete, using the intermediate result that deciding if two given 2CNF formulas have the same number of satisfying solutions is C_=P-complete. Therefore isomorphism of such succinctly encoded solution graphs is not harder than deciding if two such graphs have the same number of vertices.dc.description.abstract
AbstractSuccincte Kodierungen sind kurze Beschreibungen von Relationen, sodass die beschriebenen Relationen exponentiell größer sein können als ihre Beschreibungen. Wir können Graphen als binäre Relationen über ihrer Knotenmenge mit Schaltkreisen, Formeln, OBDDs und anderen Modellen kodieren, welche eine Wahrheitstabelle speichern. Diese Dissertation behandelt zwei typische Arten von succincten Kodierungen von Graphen: 1. Wenn eine Knoten- und Kantenmenge durch eine succincte Beschreibung gegeben ist sprechen wir von einer standard-succincten Kodierung. 2. Oder es wird die Menge der Knoten succinct beschrieben und die Kanten werden anhand eines festen Host-Graphen definiert. Ist dieser Host-Graph der n-dimensionale Hyperwürfel, so spricht man von Lösungsgraphen. Bisher konnte für alle untersuchten standard-succinct-kodierten Entscheidungsprobleme gezeigt werden, dass sie exponentiell schwerer werden als ihre explizit gegebenen Varianten. Dieses Verhalten wird mit sogenannten Upward-Translation Theoremen gezeigt, welche stark eingeschränkte Reduktionen zwischen zwei Entscheidungsproblemen zu Reduktionen in polynomieller Zeit zwischen ihren succincten Varianten übersetzen. Wir erweitern diese Ergebnisse, indem wir Entscheidungsprobleme auf succinct-kodierten Graphen betrachten, für die die succincte Kodierung Schaltkreise beschränkter Tiefe sind. Wir zeigen, dass solche Graphen aus alternierenden Vereinigungen und Schnitten von vollständigen bipartiten Graphen konstruiert werden können. Diese Struktur erlaubt es uns für manche CNF- und DNF-kodierten Probleme effizientere Algorithmen anzugeben. Wir geben dadurch die ersten standard-succinct-kodierten Entscheidungsprobleme an, welche nicht schwerer als ihre expliziten Varianten sind (z.B. STCONN auf DNF-kodierte Graphen) oder welche nur etwas schwerer als ihre expliziten Varianten werden (z.B. DS auf DNF-kodierte Graphen). Anhand dieser Ausnahmen lässt sich beweisen, dass es keine Upward-Translation Theoreme für CNF- und DNF-kodierte Entscheidungsprobleme gibt, solange unter der verwendeten Reduktion Clique und CNFSAT äquivalent sind. Dies impliziert, dass es keine Upward-Translation Theoreme für logarithmisch-platz-beschränkte Reduktionen und CNF- und DNF-kodierte Entscheidungsprobleme gibt. Wir zeigen zudem, dass es für Schaltkreise der Tiefe 3 solche Theoreme gibt. Des weiteren transferieren wir diese Ergebnisse auf explizite Graphen, indem wir eine Hierarchie von Graph-Klassen definieren, in der die zweite Ebene bereits Graphen enthält, für welche alle NP-vollständigen Probleme NP-vollständig bleiben. Ähnlich wie bereits bei den succinct-kodierten Problemen zeigen wir, dass dies für die erste Ebene wohl nicht gilt: wir geben einen Algorithmus für DS auf Graphen in der ersten Ebene an, welcher nur sub-exponentielle Zeit benötigt. Für GI ist jedoch bereits die erste Ebene GI-vollständig. Für Lösungsgraphen verbessern wir die bekannten Ergebnisse bezüglich der Komplexität von USTCONN und erweitern die bekannten strukturellen Ergebnisse dieser Graphen. Wir zeigen, dass Zusammenhangskomponenten in Graphen, die durch CPSS Formeln kodiert werden, sogenannte Partial-Cubes sind. Wenn diese Formeln nicht mehr CPSS sein müssen, gilt diese Eigenschaft nicht mehr unbedingt. Wir zeigen zudem, dass für sogenannte safely-tight Formeln das USTCONN-Problem auf das Erfüllbarkeitsproblem von verwandten Formeln reduziert werden kann. Dies impliziert unter anderem, dass USTCONN auf 2CNF-kodierten Lösungsgraphen NL-vollständig ist. Zusätzlich verwenden wir unsere strukturellen Ergebnisse für 2CNF-kodierte Lösungsgraphen, um zu zeigen, dass GI auf solche Graphen C_=P-vollständig ist. Für die untere Schranke beweisen wir zuerst, dass zu prüfen, ob zwei 2CNF Formeln gleich viele erfüllende Belegungen haben, ebenfalls C_=P-vollständig ist. Somit ist GI auf solchen Lösungsgraphen genauso schwer wie zu entscheiden, ob zwei solcher Graphen gleich viele Knoten besitzen.dc.description.abstract
Languageendc.language.iso
PublisherUniversität Ulmdc.publisher
LicenseStandarddc.rights
Link to license texthttps://oparu.uni-ulm.de/xmlui/license_v3dc.rights.uri
KeywordSuccinct encodingsdc.subject
Dewey Decimal GroupDDC 004 / Data processing & computer sciencedc.subject.ddc
LCSHComputational complexitydc.subject.lcsh
LCSHGraphsdc.subject.lcsh
TitleProblems on succinctly encoded graphsdc.title
Resource typeDissertationdc.type
Date of acceptance2017-04-28dcterms.dateAccepted
RefereeTorán, Jacobodc.contributor.referee
RefereeArvind, Vikramandc.contributor.referee
RefereeThierauf, Thomasdc.contributor.referee
DOIhttp://dx.doi.org/10.18725/OPARU-4390dc.identifier.doi
PPN892869321dc.identifier.ppn
URNhttp://nbn-resolving.de/urn:nbn:de:bsz:289-oparu-4429-0dc.identifier.urn
GNDCodierungdc.subject.gnd
GNDGraphendc.subject.gnd
FacultyFakultät für Ingenieurwissenschaften, Informatik und Psychologieuulm.affiliationGeneral
InstitutionInstitut für Theoretische Informatikuulm.affiliationSpecific
Shelfmark print versionW: W-H 15.172uulm.shelfmark
Grantor of degreeFakultät für Ingenieurwissenschaften, Informatik und Psychologieuulm.thesisGrantor
DCMI TypeTextuulm.typeDCMI
TypeErstveröffentlichunguulm.veroeffentlichung
CategoryPublikationenuulm.category
University Bibliographyjauulm.unibibliographie


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record