FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:     | 1 |   ...   | 10 | 11 || 13 | 14 |   ...   | 16 |

«Gefördert durch die Deutsche Forschungsgemeinschaft im Rahmen des Graduiertenkollegs ’Methods for Discrete Structures’ (GRK 1408) Präsident der ...»

-- [ Page 12 ] --

For (ii), we have to get rid of weights larger than 1. Let Ga be one query of the last reduction. Again we assume that a ≤ n and that weights = 1 are only allowed at loop edges. We replace every edge of weight a by the gadget that is drawn in Figure 5.2, and call this new unweighted graph G. It can be checked easily that the gadget indeed simulates a weight of a (parallel paths correspond to addition, serial edges to multiplication), i.e., per G = per Ga. Unfortunately, the reduction increases the number of edges by a superconstant factor: The number of edges of G is m(G ) ≤ (m+n log a) ≤ O(m+n log n).

5. Exponential Time Counting Complexity

–  –  –

But since m(G )/ log m(G ) ≤ O(m), the reduction implies that (ii).

For (iii), we assume that ETH holds. Theorem 5.1 gives that Unique 3-Sat cannot be computed in time exp(o(m)). Now we apply the first reduction of (i) to a formula ϕ which is promised to have at most one satisfying assignment. Then the number per G = (−2)i · #Sat(ϕ) is either 0 or (−2)i. In G, we replace each edge of weight −1 by a gadget of weight 2 ≡ −1 mod 3 and similarly get that (per G mod 3) is (0 mod 3) or (4i mod 3). Since (4i mod 3) = 0, we can distinguish the case in which ϕ is unsatisfiable from the case in which ϕ has exactly one satisfying assignment.

5.3. The Tutte Polynomial In this section, we prove Theorem 1.11, our hardness results for evaluating the Tutte polynomial. For quick reference, we state the propositions in which the individual results are proved and the techniques used in each case.

Theorem 1.11 (restated).

Let (x, y) ∈ Q2. Under #ETH, Tutte(x, y) requires time exp(Ω(n)) (i) if (x − 1)(y − 1) = 1 and y ∈ {0, ±1}, ( Proposition 5.3 in §5.3.2; stretching and thickening )

–  –  –

Tutte01 (x, y) requires time exp(Ω(m/ log3 m)) (iv) if (x − 1)(y − 1) ∈ {0, 1} and (x, y) ∈ {(−1, −1), (−1, 0), (0, −1)}.

( Proposition 5.4 in §5.3.3; inflation with Theta graphs )

–  –  –

see [Sok05, eq. (2.26)].

The Ising Hyperbola We begin with the case q = 2.

Proposition 5.1. Computing the coefficients of the polynomial w → Z(G; 2, w) for given simple graph G requires time exp(Ω(m)) under #ETH.

Proof. The reduction is from #MaxCut and well-known, see, e.g., [JS93, Theorem 15].

Name #MaxCut Input Simple undirected graph G.

Output The number of maximum cuts.

A maximum cut is a set C ⊆ V (G) that maximizes the number |E(C, C)| of edges of G that cross the cut. By the Fortuin–Kasteleyn identity [Sok05, Theorem 2.3], one can express Z(G; 2, w) for G = (V, E) as

–  –  –

Here the Iverson bracket [P ] is 1 if P is true and is 0 if P is false. The sets σ −1 (1) and σ −1 (−1) define a cut in G, so we can write the above expression as

–  –  –

Now, the coefficient of (1 + w)m−c in Z(G; 2, w) is the number of cuts in G of size c. In particular, after some interpolation, we can compute the number of maximum cuts in G from the coefficients of w → Z(G; 2, w). But as we observe in Appendix D, #MaxCut requires time exp(Ω(m)) under #ETH.

5. Exponential Time Counting Complexity

The Multivariate Tutte Polynomial For other q, in particular nonintegers, it is simpler to work with a multivariate formulation of the Tutte polynomial due to Fortuin and Kasteleyn [FK72]. We use Sokal’s definition [Sok05]: Let G = (V, E) be an undirected graph whose edge weights are given by a function w : E → Q. Then Z(G; q, w) = (5.2) q k(A) w(e).

A⊆E e∈A If w is single-valued, in the sense that w(e) = w for all e ∈ E, we recover Z(G; q, w).

The conceptual strength of the multivariate perspective is that it turns the Tutte polynomial’s second variable y, suitably transformed, into an edge weight of the graph.

In particular, the multivariate formulation allows the graph to have different weights on different edges, which turns out to be a dramatic technical simplification even when, as in the present work, we are ultimately interested in the single-valued case.

Sokal’s polynomial vanishes at q = 0, so we sometimes use the polynomial

–  –  –

For fixed G and q, this is a polynomial in w of degree at most m.

Lemma 5.1.

Let q be a rational number with q ∈ {1, 2}. Computing the coefficients of the polynomial w → Z0 (G; q, w), with w as in (5.4), for a given simple graph G requires time exp(Ω(m)) under #ETH. Moreover, this is true even if |T | = 3.

–  –  –

Proof. In Appendix D, we argue that a standard reduction from #MaxCut already implies that the problem #3-Terminal MinCut requires time exp(Ω(m)) under #ETH.

Name #3-Terminal MinCut Input Simple undirected graph G = (V, E) with three distinguished vertices (“terminals”) t1, t2, t3 ∈ V.

Output The number of edge subsets A ⊆ E of minimal size that separate t1 from t2, t2 from t3, and t3 from t1.

–  –  –

We first show that the second term of (5.6) vanishes. Consider an edge subset A ∈ A and assume without loss of generality that it connects the terminals t1 and t2. Consider B ⊆ T, and let B = B ⊕ {t1 t2 }, so that B is the same as B except for t1 t2. Then the contributions of A ∪ B and A ∪ B cancel: First, k(A ∪ B) equals k(A ∪ B ) because t1 and t2 are connected through A already, so the presence or absence of the edge t1 t2 makes no difference. Second, (−1)|B| equals −(−1)|B |.

We proceed to simplify the first term of (5.6). The edges in B only ever connect vertices in T, and for A ∈ A, each of these lies in a separate component of (V, A), so

–  –  –

The edge subsets A ∈ A are exactly the complements of the 3-terminal cuts in G.

Now consider the family C of minimal 3-terminal cuts, all of size c. The sets E − A in C are exactly the sets A of size m − c in A, and by minimality, k(A) = 3. Thus,

–  –  –

Thus, if we could compute the coefficients d0,..., dm of w → Q−1 Z0 (G; q, w), then we could determine the smallest c so that dm−c = 0 and return dm−c = |C |/Q, the number of 3-terminal mincuts.

General Hyperbolas We want to use Lemma 5.1 to show that computing the coefficients of the univariate Tutte polynomial at any fixed q ∈ {1, 2} is hard. For this, we need to get rid of negative weights and reduce to a single-valued weight function. In [GJ08], this is done by thickenings and stretches, which we have to avoid. Since the number of edges with a negative weight is small (in fact, 3), we can use another tool: deletion–contraction.

A deletion–contraction identity expresses a function of the graph G in terms of two graphs G − e and G/e, where G − e arises from G by deleting the edge e ( → ) and G/e arises from G by contracting the edge e ( → ) that is, deleting it and identifying its endpoints (so any remaining edges between these two endpoints become loops).

It is known [Sok05, eq. (4.6)] that

–  –  –

An edge e is a bridge of G if deleting e from G increases the number of connected

components. The above gives a deletion–contraction identity for Z0 as well:

–  –  –

Proposition 5.2. Let q be a rational number with q ∈ {1, 2}. Computing the coefficients / of the polynomial v → Z0 (G; q, v) for a given simple graph G requires time exp(Ω(m)) under #ETH.

By (5.3), this proposition also holds for Z instead of Z0 when q ∈ {0, 1, 2}.

Proof. Let G = (V, E) be a graph as in the previous lemma, with three edges T = {e1, e2, e3 } of weight −1. The given reduction actually uses the restriction that G =

–  –  –

(V, E \T ) is connected, so we can assume that this is the case. Thus, none of the T -edges is a bridge, so three applications of (5.8) to delete and contract these edges, gives

–  –  –

where for each C ⊆ {1, 2, 3}, the graph GC is constructed from G by removing e1, e2, e3 as follows: If i ∈ C then ei is contracted, otherwise it is deleted. In any case, the edges of T have disappeared and remaining edges of GC are in one-to-one correspondence with the edges in E; especially, they all have the same weight w, so Z0 (GC ; q, w) = Z0 (GC ; q, w).

The resulting GC are not necessarily simple, because the contracted edges from T may have been part of a triangle and may have produced a loop. (In fact, investigating the details of the previous lemma, we can see that this is indeed the case.) Thus we construct the simple graph GC from GC by subdividing every edge into a 3-path. This operation, known as a 3-stretch, is known to largely preserve the value of Z and Z0 (see [Sok04] for the former and [GJ08] for the latter). In particular,

–  –  –

5.3.2. Individual Points for Multigraphs If we allow graphs to have multiple edges, we can use thickening and interpolation, one of the original strategies of [JVW90], for relocating the hardness result for hyperbolas from Proposition 5.1 and Proposition 5.2 to individual points in the Tutte plane. For most points, this gives us tight bounds in terms of n, the number of vertices, but not for points with y ∈ {0, ±1}, where thickening fails completely.

We recall the thickening identities for the Tutte polynomial. The k-thickening of G is the graph Gk in which all edges have been replaced by k parallel edges. One can show [Sok05, (4.21)] that, with wk = (1 + w)k − 1,

–  –  –

It is easy to transfer this result to the Tutte polynomial T using (5.1), yielding special cases of Brylawski’s well-known graph transformation rules.

5. Exponential Time Counting Complexity We use interpolation and obtain Theorem 1.11 (i) for y = 0 from the following.

Proposition 5.3. Let (q, w) ∈ Q2 with w ∈ {0, −1, −2} and q = 1. Computing Z(G; q, w) for a given graph G (not necessarily simple) requires time exp(Ω(n)) under #ETH.

Proof. We observe that the values wk = (1 + w)k − 1 are all distinct for k = 0, 1,..., m.

Thus, the k-thickenings Gk of G give rise to m + 1 different weight shifts, the evaluations of which, Z(G; q, wk ), can be obtained from Z(Gk ; q, w) using (5.10). Thus, with oracle access to G → Z(G ; q, w), we can compute the coefficients of the polynomial v → Z(G; q, v) in polynomial time for any given G. By Proposition 5.1 and Proposition 5.2, doing so requires time exp(Ω(n)) under #ETH. Since the number of vertices is n in each Gk, computing G → Z(G ; q, w) requires time exp(Ω(n)) under #ETH.

The proof of Theorem 1.11 (ii) uses Linial’s well-known reduction for the chromatic polynomial [Lin86], and is deferred to Proposition D.1 in Appendix D.

5.3.3. Individual Points for Simple Graphs In this section we show that most points (x, y) of the Tutte plane are as hard as the entire hyperbola on which they lie, even for sparse, simple graphs. The drawback of our method is that we lose a polylogarithmic factor in the exponent of the lower bound.

The results are particularly interesting for the points on the line y = −1, for which we know no other good exponential lower bounds under #ETH, even in more general graph classes. We remark that the points (−1, −1), (0, −1), and ( 1, −1) on this line are known to admit a polynomial-time algorithm, and indeed our hardness result does not apply here.

Graph inflations We use the graph theoretic version of Brylawski’s tensor product for matroids [Bry82].

We found the following terminology more intuitive in our setting.

Definition 5.1 (Graph inflation). Let H be a 2-terminal undirected graph. For any undirected graph G = (V, E), an H-inflation of G, denoted G ⊗ H, is obtained by replacing every edge xy ∈ E by (a fresh copy of) H, identifying x with one of the terminals of H and y with the other.

If H is not symmetric with respect to its two terminals, then the graph G ⊗ H need not be unique since there are in general two non-isomorphic ways two replace an edge xy by H. For us this difference does not matter since the resulting Tutte polynomials turn out to be the same; in fact, in any graph one can remove a maximal biconnected component and reinsert it in the other direction without changing the Tutte polynomial, an operation that is called the Whitney twist. Thus we choose G ⊗ H arbitrarily among the graphs that satisfy the condition in the definition above. Graph inflation is not commutative and Sokal uses the notation GH.

5.3. The Tutte Polynomial

If H is a simple path of k edges, G ⊗ H gives the usual k-stretch of G, and a bundle of k parallel edges results in a k-thickening. What makes graph inflations so useful in the study of Tutte polynomials is that the Tutte polynomial of G ⊗ H can be expressed in terms of the Tutte polynomials of G and H, so that Z(G ⊗ H; q, w) ∼ Z(G; q, w ) for some ‘shifted’ weight w.

For fixed rational points (q, w), we want to use interpolation to prove the hardness of computing Z(G; q, w) for a given graph G. The basic idea is to find a suitable class of graphs {Hi }, such that we can compute the coefficients of the monovariate polynomial v → Z(G; q, v) for given G and q by interpolation from sufficiently many evaluations of Z(G; q, wi ) ∼ Z(G ⊗ Hi ; q, w). For this, we need that the number of different weight shifts {wi } provided by the graph class {Hi } is at least |E(G)| + 1, one more than the degree of the polynomial.

–  –  –

This lemma can be derived from Sokal’s series and parallel reduction rules for Z using a straightforward calculation. Since all edge weights are the same, the result can also be established from the classical Tutte polynomial via the series and parallel reduction rules in [JVW90], but the calculation would be slightly more laborious.

We now show that the class of Theta graphs provides a rich enough spectrum of weight shifts to allow for interpolation.

Lemma 5.3.

Pages:     | 1 |   ...   | 10 | 11 || 13 | 14 |   ...   | 16 |

Similar works:

«Web: www.igwbs.ch IG WBS Interessengruppe der Wissenschaftlichen Mail: info@igwbs.ch Bibliothekarinnen und Bibliothekare der Schweiz GI BSS Groupe d’intérêt des bibliothécaires scientifiques suisses Post: IG WBS, 3000 Bern Rundbrief an die Mitglieder Nr. 59 – Urheberrecht August 2012 Liebe Mitglieder der IG WBS, liebe Kolleginnen und Kollegen Das Thema Urheberrecht im Umfeld der Bibliotheken ist mit der Klage, welche die grossen Wissenschaftsverlage Elsevier, Thieme und Springer beim...»

«The granular connection (Xenakis, Vaggione, Di Scipio.) Makis Solomos To cite this version: Makis Solomos. The granular connection (Xenakis, Vaggione, Di Scipio.). Symposium The Creative and Scientific Legacies of Iannis Xenakis International Symposium, 2006, Canada. hal-00770088 HAL Id: hal-00770088 https://hal.archives-ouvertes.fr/hal-00770088 Submitted on 7 Jan 2013 HAL is a multi-disciplinary open access L’archive ouverte pluridisciplinaire HAL, est archive for the deposit and...»

«Deutscher Bundestag Drucksache 18/3270 18. Wahlperiode 20.11.2014 Unterrichtung durch die Bundesregierung Fortschrittsbericht zur Lage in Afghanistan 2014 einschließlich einer Zwischenbilanz des Afghanistan-Engagements Inhaltsverz eich nis Seite Einleitung Zusammenfassung des Fortschrittsberichts 2014 1. Staatswesen und Regierungsführung 1.1 Wahlen und Regierungswechsel 1.2 Regierungsführung und Institutionen 1.3 Internationale Beziehungen 1.4 Zivilgesellschaft und Menschenrechte 1.5...»

«Enduring Love? Couple Relationships in the 21st Century Survey Findings Report Authors Jacqui Gabb, Martina Klett-Davies, Janet Fink and Manuela Thomae © The Open University November 2013 ISBN 978-1-78007-951-6 Contents page Contents page.. 2 Executive summary.. 3 1. Introduction.. 8 2. Research Methodology.. 10 3. Sample Information (UK).. 11 4. Relationship Quality, Relationship with Partner, Relationship Maintenance 4.1 Survey design and measures.. 13 4.2 A guide to results.. 16...»

«Überblick und Vergleich der Forschungsförderung in Österreich F. Fahringer Berichte aus Energieund Umweltforschung 10/2012 Die vorliegende Abschlussarbeit von Fahringer Fritz mit dem Thema Überblick und Vergleich der Forschungsförderung in Österreich liefert einen guten Überblick über die Förderlandschaft in Österreich, sowie die Rolle Österreichs im europäischen Kontext. Ein Teil der Arbeit analysiert nationale Energieforschungsprogramme des Bundesministeriums für Verkehr,...»

«Alarms and Responses: A Comparative Study of Contemporary International Efforts to Anticipate and Prevent Violent Conflicts. The Case of El Salvador ˝ ˝ Terry KarlF ˝ Stanford University ˝ ˝ The recent experience of El Salvador that is, the causes of its civil war and the war's subsequent resolution through a United Nations-sponsored peace agreement is instructive for policymakers seeking to prevent similar conflicts for several reasons. First, El Salvador's authoritarian regime...»

«Nokoko Institute of African Studies Carleton University (Ottawa, Canada) 2014 (4) Kupururudzira muroora songs in Muzvezve Bride welcoming ceremony or relegation of women to the subaltern? by Wonder Maguraushe and Treda Mukuhlani The institution of marriage is a place where Shona women have often suffered oppression instead of fulfilment. Women have lamented Shona cultural practices that are not cognisant of human rights despite Zimbabwe being a signatory to the SADC Declaration on Gender and...»

«South East Queensland Regional Plan 2005–2026 Implementation Guideline No. 8 Identifying and protecting scenic amenity values September 2007 Acknowledgements These guidelines draw from previous scenic amenity studies by SEQ local governments, including the Brisbane City Council, Caboolture Shire Council, Esk Shire Council, Gatton Shire Council, Ipswich City Council and Laidley Shire Council. Other information in these guidelines has been drawn from studies conducted during stage 1 of the SEQ...»

«IYARE! Splendor & Tension in Benin’s Palace Theatre November 8, 2008 – March 1, 2009 University of Pennsylvania Museum of Archaeology and Anthropology Print Resources The resources below are divided by subheadings. This list is not meant to be exhaustive, but these selected works are available through many major libraries. Their bibliographies will yield many additional references. Ẹdo Traditional Culture and Art Aisien, Ekhaguosa. Iwu, the body markings of the Edo people. Benin City:...»

«weiterbildungsinstitut.at Weiterbildungsinstitut Wien Service GmbH Rechte Wienzeile 85, 1050 Wien (U4, 13A, 14A, 12A Station: Pilgramgasse) Tel: 01/94 33 699 Fax: 01/94 33 699 30 E-mail: info@weiterbildungsinstitut.at ALLGEMEINE GESCHÄFTSBEDINGUNGEN für Sprachkurse der Weiterbildungsinstitut Wien Service GmbH Stand 10.07.2015 Deutsch Seite 2-3 English Page 4-5 ALLGEMEINE GESCHÄFTSBEDINGUNGEN für Sprachkurse der Weiterbildungsinstitut Wien Service GmbH (Soweit in diesen AGB personenbezogene...»

«Commemorating the 70th Anniversary of the Liberation of Bergen-Belsen Concentration Camp by British Forces: Guidance Notes and Suggested Readings Introduction 15th April 2015 marks the 70th anniversary of the liberation of Bergen-Belsen concentration camp in Germany by the 11th Armoured Division of the British Army, an event which shaped British awareness and understanding of the Holocaust. The anniversary will be marked by a series of public commemorations culminating in an international...»

«Die inoffizielle Betriebsanleitung für den Elecraft K2 zusammengestellt von Daniel, DM3DA Es kommt gar nicht so sehr darauf an, welches Funkgerät Du hast. Viel wichtiger ist, dass Du den Umgang mit dem Gerät lernst. Learn to drive it. — Brian, G8OSN Version: 2014-02-18 Kontakt: Daniel Schlieper, DM3DA, Wissmannstr. 21, 40219 Düsseldorf Email: dm3da@tuxomania.net Satz: LuaLTEX mit KOMA-Script aus der Latin Modern A Einbandgestaltung unter Verwendung einer Zeichnung von Elecraft Quelltext:...»

<<  HOME   |    CONTACTS
2016 www.abstract.xlibx.info - Free e-library - Abstract, dissertation, book

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.