FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 16 |

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

-- [ Page 4 ] --

The literature for computing the Tutte polynomial is very rich, and we make no attempt to survey it here. A recent paper of [GJ08], which shows that the Tutte polynomial is hard to even approximate for large parts of the Tutte plane, contains an overview. A list of graph classes for which subexponential time algorithms are known can be found in [BHKK08].

Results Our hardness results are based on two versions of the exponential time hypothesis. The (randomized) exponential time hypothesis (ETH) as defined in [IPZ01] is that satisfiThe Feynman quote and many other quotes describing the frustration and puzzlement of physicists around that time can be found in the copious footnotes of [Ist00].

1. Introduction ability of 3-CNF formulas cannot be computed substantially faster than by trying all

possible assignments, i.e., it requires time exp(Ω(n)). Formally, this reads as follows:

(ETH) There is a constant c 0 such that no randomized algorithm can decide 3-Sat in time exp(c · n) with error probability at most 3.

The second hypothesis we are using is the (deterministic) counting exponential time hypothesis, based on the counting variant of 3-Sat.

Name #3-Sat Input 3-CNF formula ϕ with n variables and m clauses.

Output The number of satisfying assignments to ϕ.

The best known algorithm for this problem runs in time O(1.6423n ) [Kut07].

(#ETH) There is a constant c 0 such that no deterministic algorithm can compute #3-Sat in time exp(c · n).

ETH trivially implies #ETH whereas the other direction is not known. By introducing the sparsification lemma, [IPZ01] show that ETH is a robust notion in the sense that the clause width 3 and the parameter n in its definition can be replaced by d ≥ 3 and m, respectively, to get an equivalent hypothesis. The constant c may change in doing so.

We transfer the sparsification lemma to #d-Sat and get a similar kind of robustness for #ETH, the proof of which is spelled out in §C.

Theorem 1.8.

Let d ≥ 3 be an integer. Then #ETH holds if and only if there is a constant c 0 such that no deterministic algorithm can solve #d-Sat time exp(c · m).

For convenience, we say that #d-Sat requires time exp(Ω(m)).

Counting Independent Sets In light of Theorem 1.8, it is natural to consider the exponential time complexity of #2-Sat. Restricted to antimonotone 2-CNF formulas, this corresponds to counting all independent sets in a given graph, which Hoffmann [Hof10] shows to require time exp(Ω(n/ log3 n)) under #ETH. The loss of the poly log-factor in the exponent is due to the interpolation inherent in the hardness reduction. We avoid interpolation using the isolation lemma for d-CNF formulas [CIKP03] and get an asymptotically tight lower bound, with the drawback that our lower bound only holds under the (randomized) exponential time hypothesis ETH instead of #ETH.

Theorem 1.9.

Counting independent sets and #2-Sat require time exp(Ω(m)) under ETH, where m is the number of edges and clauses, respectively.

We discuss the isolation technique and prove this theorem in §5.1.

–  –  –

The Permanent

For a set S of rationals we define the following problems:

Name PermS Input Square matrix A with entries from S.

Output The value of per A.

We write Perm for PermN. If B is a bipartite graph with Aij edges from the ith vertex in the left half to the jth vertex in the right half (1 ≤ i, j ≤ n), then per(A) equals the number of perfect matchings of B. Thus Perm and Perm0,1 can be viewed as counting the perfect matchings in bipartite multigraphs and bipartite simple graphs, respectively.

We express our lower bounds in terms of m, the number of non-zero entries of A.

Without loss of generality, n ≤ m, so the same bounds hold for the parameter n as well.

Note that these bounds imply that the hardest instances have roughly linear density.

Theorem 1.10.

(i) Perm−1,0,1 and Perm require time exp(Ω(m)) under #ETH.

(ii) Perm01 requires time exp(Ω(m/ log n)) under #ETH.

(iii) Perm01 requires time exp(Ω(m)) under ETH.

The proof of this theorem is in §5.2. For (i), we follow a standard reduction by Valiant [Val79, Pap94] but use a simple equality gadget derived from [BD07] instead of Valiant’s XOR-gadget, and we use interpolation to get rid of the negative weights. To establish (ii) we simulate edge weights w 1 by gadgets of size logarithmic in w, which increases the number of vertices and edges by a logarithmic factor. For (iii) we use the isolation lemma and the reduction from part (i), and we simulate the edge weights −1 without interpolation by replacing them with 2 and doing computation modulo 3.

The Tutte Polynomial The computational problem Tutte(x, y) is defined for each pair (x, y) of rationals.

Name Tutte(x, y).

Input Undirected multigraph G with n vertices.

Output The value of T (G; x, y).

In general, parallel edges and loops are allowed; we write Tutte01 (x, y) for the special case where the input graph is simple.

Our main result is that under #ETH, Tutte(x, y) requires time exp(Ω(n)) for specific points (x, y), but the size of the bound, and the graph classes for which it holds, varies.

We summarise our results in the theorem below, see also Figure 1.1. Our reductions often give edge-exponential lower bounds, i.e., bounds in terms of the parameter m, which implies the same bounds in terms of n because m ≥ n in connected graphs.

1. Introduction

–  –  –

Figure 1.1.

: Exponential time complexity under #ETH of the Tutte plane for multigraphs (left) and simple graphs (right) in terms of n, the number of vertices. The white line y = 1 on the map is uncharted territory. The black hyperbola (x − 1)(y − 1) = 1 and the four points close to the origin are in P. Everywhere else, in the shaded regions, we prove a lower bound exponential in n, or within a polylogarithmic factor of it.

Moreover, a lower bound of exp(Ω(m/ poly log m)) together with the algorithm in time exp(O(n)) from [BHKK08] implies that worst-case instances are sparse, in the sense that m = O(n · poly log n).

–  –  –

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)}.

In an attempt to prove these results, we may first turn to the literature, which contains a cornucopia of constructions for proving hardness of the Tutte polynomial in various models. In these arguments, a central role is played by graph transformations called thickenings and stretches. A k-thickening replaces every edge by a bundle of k edges, and a k-stretch replaces every edge by a path of k edges. This is used to ‘move’ an evaluation from one point to another. For example, if H is the 2-stretch of G then T (H; 2, 2) ∼ T (G; 4, 3 ). Thus, every algorithm for (2, 2) works also at (4, 4 ), connecting the complexity of the two points. These reductions are very well-developed in the literature, and are used in models that are immune to polynomial-size changes in the input parameters, such as #P-hardness and approximation complexity. However, we cannot always afford such constructions in our setting, otherwise our bounds would

1.2. Sparse Instances of Counting Problems

be of the form exp(Ω(n1/r )) for some constant r depending on the blowup in the proof.

In particular, the parameter n is destroyed already by a 2-stretch in a nonsparse graph.

The proofs are in §5.3. Where we can, we sample from established methods, carefully avoiding or modifying those that are not parameter-preserving. At other times we require more subtle techniques, e.g., the constructions in §5.3.3, which use graph products with graphs of polylogarithmic size instead of thickenings and stretches. Like many recent papers, we use Sokal’s multivariate version of the Tutte polynomial, which vastly simplifies many of the technical details.

Consequences The permanent and Tutte polynomial are equivalent to, or generalisations of, various other graph problems, so our lower bounds under ETH and #ETH hold for these problems as well. In particular, it takes time exp(Ω(m)) to compute the following graph polynomials (for example, as a list of their coefficients) for a given simple graph: the Ising partition function, the q-state Potts partition function (q = 0, 1, 2), the reliability polynomial, the chromatic polynomial, and the flow polynomial. Moreover, we have exp(Ω(n)) lower bounds for the following counting problems on multigraphs: # perfect matchings, # cycle covers in digraphs, # connected spanning subgraphs, all-terminal graph reliability with given edge failure probability p 0, # nowhere-zero k-flows (k = 0, ±1), and # acyclic orientations.

The lower bound for counting the number of perfect matchings holds even in bipartite graphs, where an O(1.414n ) algorithm is given by Ryser’s formula. Such algorithms are also known for general graphs [BH08a], the current best bound is O(1.619n ) [Koi09].

For simple graphs, we have exp(Ω(m)) lower bounds for # perfect matchings and # cycle covers in digraphs.

2. Preliminaries Most of our notation is standard (see [AB09, Gol08] for general and [DF99, FG06, Nie06] for parameterized complexity). We suffice with a review of some particular notions and notation we use.

Problems By a problem we usually mean a decision problem, i.e., deciding membership to a language L ⊆ {0, 1}∗. Apart from their bitlength |x|, instances x ∈ {0, 1}∗ often have another natural complexity parameter k(x), such as the number of vertices in the case of graph problems, or the witness length in the case of NP-problems. The function k : {0, 1}∗ → N is called parameterization and a parameterized problem is a pair (L, k).

We often write L for both the parameterized and unparameterized problem, e.g., when saying that a parameterized problem is NP-complete.

We denote the complement of L by L. The OR of a language L is the language OR(L) that consists of all tuples (x1,..., xt ) with t 0 for which there is an i ∈ [t] with xi ∈ L.

An OR-problem with arity t : N → N \ {0} is a problem OR(L) restricted to instances that satisfy the additional properties s = |x1 | = · · · = |xt | and t = t(s) for some s ∈ N.

We denote this problem by ORt (L).

Satisfiability A d-CNF formula on the variables x1,..., xn is a conjunction of clauses where a clause is a disjunction of exactly d literals, i.e., the variables xi and their negations xi. We denote by d-Sat the problem of deciding whether a given d-CNF formula has at least one satisfying assignment, i.e., a truth assignment to its variables that makes the formula evaluate to true.

Hypergraph Problems A hypergraph G = (V (G), E(G)) consists of a finite set V (G) of vertices and a set E(G) of subsets of V (G), the (hyper)edges. A hypergraph is d-uniform if every edge has size exactly d. A vertex cover of G is a set S ⊆ V (G) that contains at least one vertex from every edge of G, and d-Vertex Cover is the problem of deciding whether, for a given d-uniform hypergraph G and integer k, there exists a vertex cover of G of size at most k. Similarly, a clique of G is a set S ⊆ V (G) all of whose subsets of size d are edges of G, and d-Clique is the problem of deciding whether, for given (G, k), there exists a clique of G of size at least k. The two problems are dual to each other, in the sense that G, the d-uniform hypergraph obtained from G by flipping the presence of all edges of size d, has a clique of size k if and only if G has a vertex cover of size n − k.

Note that this transformation preserves the number of vertices.

Reductions Unless stated otherwise the reductions we consider are computable in time polynomial in the bitlength of the input. We indicate this by a superscript p in the

2. Preliminaries notation ≤p for reducibility. We consider both general reductions (also known as Turing reductions) as well as mapping reductions (also known as many-one reductions). A mapping reduction, or ≤p -reduction, from L to L is a mapping R from {0, 1}∗ to {0, 1}∗ m such that R(x) ∈ L if and only if x ∈ L.

A compression of (L, k) is a ≤p -reduction from L to some language L that maps m instances with parameter k to instances of bitlength at most g(k) for some computable function g independent of the input size. A kernelization is a compression with L = L. Note that any decidable parameterized problem that has a kernelization is fixedparameter tractable, that is, it can be solved in deterministic time f (k) · poly(n) for some computable function f : The reduced instance has size at most g(k) and can be solved using any algorithm for L.

Complexity Classes The polynomial-time hierarchy PH is the union ∪i≥0 Σp, where i Σp = P, and Σp = NPΣi for i ≥ 0. We say that the polynomial-time hierarchy p 0 i+1 collapses to its ith level if PH = Σp. It is widely conjectured that the polynomial-time i hierarchy does not collapse to any level.

Given a class C of languages, we denote by coC the class {L | L ∈ C}. Apart from the first few levels of the polynomial-time hierarchy and their co-classes, we make use of complexity classes with advice. Given a class C of languages and a function : N → N, we denote by C/ (n) the class of languages L for which there exists a language L ∈ C and a sequence a0, a1, a2,... of strings with |an | ≤ (n) such that for any input x, we have that x ∈ L if and only if x, a|x| ∈ L, where ·, · denotes a standard pairing function. We call an the advice at length n. C/ poly is a shorthand for ∪c0 C/nc. P/ poly consists exactly of the languages that can be decided by Boolean circuits of polynomial size. Similarly, NP/ poly consists exactly of the languages that can be decided by nondeterministic Boolean circuits of polynomial size. A nondeterministic circuit has two types of inputs – the actual input x and auxiliary input y. It accepts an actual input x if and only if there exists a setting of the auxiliary input y such that the circuit outputs 1 on the combined input x and y.

Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 16 |

Similar works:

«SANDIA REPORT SAND2013-5472 Unlimited Release Printed July 2013 Microgrid Cyber Security Reference Architecture Version 1.0 Cynthia K. Veitch, Jordan M. Henry, Bryan T. Richardson, Derek H. Hart Prepared by Sandia National Laboratories Albuquerque, New Mexico 87185 and Livermore, California 94550 Sandia National Laboratories is a multi-program laboratory managed and operated by Sandia Corporation, a wholly owned subsidiary of Lockheed Martin Corporation, for the U.S. Department of Energy’s...»

«See discussions, stats, and author profiles for this publication at: https://www.researchgate.net/publication/271530391 Тематика организационно-психологических публикаций в российской периодической печати за 2000–2009 гг. Article · January 2011 READS 1 author: Andrey Lovakov National Research University Higher Schoo. 7 PUBLICATIONS 0 CITATIONS SEE PROFILE Available from: Andrey Lovakov...»

«Himalayan Polyandry STR U CTU R E, F U N C T IO N IN G AND CU LTU RE CH ANGE A F IE L D -S T U D Y OF J A U N S A R -B A W A R by D. N. M A JU M D A R ASIA P U B L IS H IN G H O U SE B O M BA Y • C A L C U T T A • NEW D ELH I • M A D R A S L O N D O N • NEW Y O R K ALSO B Y D. N. M AJU M D AR Caste and Communication in an Indian Village Races and Cultures o f India Bharatiya SansKriti ke Upadan ChlioT ka ek Gaon An Introduction to Social Anthropology (w ith t. n. m adan) A Tribe in...»

«Bull. Murithienne 106 (1988): 37-50 CHRONIQUE ORNITHOLOGIQUE VALAISANNE POUR LES ANNÉES 1985 et 1986 par Antoine Sierra ' ZUSAMMENFASSUNG Ornithologische Ergebnisse aus dem Wallis für die Jahre 1985 und 1986 Der Autor sammelt die wichtigsten ornithologischen beobachtungen aus dem Wallis während der jähre 1985 und 1986. Neben den Originaldaten von 11 Beobachtern werden auch Ergebnisse, die im «Informationdienst» der Vogelwarte Sempach oder in der Zeitschrift «Nos Oiseaux» publiziert...»

«Minerals and Waste Forum Implementation Planning Advisory Group Guidance on Non-Material Amendments and Minor Material Amendments April 2012 Non-Material Amendments and Minor Material Amendments 1) Non-material Amendments Legislative provisions Non-material Amendments (NMAs) are given legislative effect by S.96A Town and Country Planning Act 1990 (brought into force on 1 October 2009) via the commencement of s.190 of the Planning Act 2008. This stipulates: (1) A local planning authority in...»

«Universidade Nova de Lisboa Faculdade de Ciências e Tecnologia Departamento de Informática MSC Dissertation in Computer Engineering 1st Semester, 2008/2009 Spatial Operators for Collaborative Map Handling ollaborative Renato Rodrigues No. 26146 Supervisor Prof.ª Doutora Maria Armanda Simenta Rodrigues Grueau February the 20th, 2009 ii No. Of the student: 26146 Name: Renato de Lemos Mendes Severino Rodrigues Title of the Dissertation: Spatial Operators for Collaborative Map Handling Keywords:...»

«Kurzanalyse Juni 2011 Die Umwälzungen in der arabischen Welt und der Palästinakonflikt Dr. John Bunzl Die Veränderungen in der arabischen Welt, besonders in Ägypten, haben eine neue Situation geschaffen und alte Gewissheiten erschüttert. Der Palästinakonflikt konnte davon nicht unberührt bleiben. Er hatte immer eine lokale, regionale und globale Dimension, deren Interaktion und Gewichtung verschieden waren und sind. Wegen der Spiegelbildlichkeit des Konflikts sind beide Parteien zwar...»

«Recreational Sports Journal, 2007, 31, 3-13  © 2007 NIRSA Foundation Campus Recreational Sports Internships: A Comparison of Student and Employer Perspectives Craig M. Ross and Brent A. Beggs The purpose of this study was to examine differences between senior-level students and campus recreational sport directors in their perceptions of recreational sport management internships. Using a web-based survey of 48 items, the study explored how students and practitioners differed in...»

«Intercultural Communication Studies XXIII: 3 (2014) Yu Understanding the Impact of Culture on Interpretation: A Relevance Theoretic Perspective Qiufen Yu University of Chester, UK Abstract: This article proposes a relevance theoretic approach to understanding the impact of culture on interpretation. Theorizing about cultural differences in communication has been dominated to date by the ‘trait’ approach (e.g. Hong and Mallorie, 2004, p.60), and yet the dependence on this approach has been...»

«Elektromobilität 11 ‐ 2013    ELEKTROMOBILITÄT   EMO  TecScan Journal Editorial   Liebe Leserinnen und Leser, als Abonnent der TecScan-Journale werden Sie nicht nur mit dem aktuellen Stand der Technik versorgt, sondern Sie erkennen Trends und Entwicklungen schon früh und können diese Informationen für Innovationen nutzen. Wir bieten die TecScan-Journale in zwei verschiedenen Lieferformen an, als gedruckte und als PDF-Ausgabe, um den unterschiedlichen Vorlieben und...»

«Aus dem Max-Planck-Institut für Physiologische und Klinische Forschung, W.G. Kerckhoff-Institut, Abteilung für Experimentelle Kardiologie, Bad Nauheim Eingereicht über das Institut für Veterinär-Anatomie, Histologie und Embryologie der Justus-Liebig-Universität Gießen Die protektive Wirkung von Cyclosporin A während der Ischämie und der Reperfusion Untersuchungen am global ischämischen Hundeherzen Inaugural-Dissertation zur Erlangung des Doktorgrades beim Fachbereich Veterinärmedizin...»

«Distribution Agreement In presenting this thesis or dissertation as a partial fulfillment of the requirements for an advanced degree from Emory University, I hereby grant to Emory University and its agents the non-exclusive license to archive, make accessible, and display my thesis or dissertation in whole or in part in all forms of media, now or hereafter known, including display on the world wide web. I understand that I may select some access restrictions as part of the online submission of...»

<<  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.