advertisement

Paths and Polynomials

67 %
33 %
advertisement
Information about Paths and Polynomials
Technology

Published on March 5, 2014

Author: ASPAK2014

Source: slideshare.net

advertisement

Paths & Polynomials

Hamiltonian Path has an algorithm that spends O(2n) time and consumes O(2n) space.

Walks to the rescue…

Walks to the rescue…

Walks to the rescue…

Adjacency Matrix A[i,j] = 1 iff (i,j) is an edge in G.

Adjacency Matrix A[i,j] = 1 iff (i,j) is an edge in G.

Adjacency Matrix A[i,j] = 1 iff (i,j) is an edge in G.

Adjacency Matrix A[i,j] = 1 iff (i,j) is an edge in G.

Adjacency Matrix A[i,j] = 1 iff (i,j) is an edge in G. What is A2[i,j]?

Adjacency Matrix A[i,j] = 1 iff (i,j) is an edge in G. What is A2[i,j]?

i j Adjacency Matrix A[i,j] = 1 iff (i,j) is an edge in G. What is A2[i,j]?

i j Adjacency Matrix A[i,j] = 1 iff (i,j) is an edge in G. What is A2[i,j]?

i j Adjacency Matrix A[i,j] = 1 iff (i,j) is an edge in G. What is A2[i,j]?

i j Adjacency Matrix A[i,j] = 1 iff (i,j) is an edge in G. What is A2[i,j]?

i j Adjacency Matrix A[i,j] = 1 iff (i,j) is an edge in G. What is A2[i,j]?

i j Adjacency Matrix A[i,j] = 1 iff (i,j) is an edge in G. What is A2[i,j]?

What is A2[i,j] counts the number of common neighbors of i and j.

What is A2[i,j] counts the number of common neighbors of i and j. What is Ak[i,j]?

What is A2[i,j] counts the number of common neighbors of i and j. What is Ak[i,j]? What is Ak[i,j] counts the number of walks of length k between i and j.

We know how to count walks!

We know how to count walks! Suppose we now want to count paths.

We know how to count walks! Suppose we now want to count paths. Let U be the collection of all Hamiltonian Walks.

We know how to count walks! Suppose we now want to count paths. Let U be the collection of all Hamiltonian Walks. Let Ai be the set of walks of length n passing through i.

Consider… n X= Ai i=1 Let U be the collection of all Hamiltonian Walks. Let Ai be the set of walks of length n passing through i.

Consider… n X=U Ai i=1 Let U be the collection of all Hamiltonian Walks. Let Ai be the set of walks of length n passing through i.

Consider… n X=U Ai i=1 Let U be the collection of all Hamiltonian Walks. Let Ai be the set of walks of length n passing through i.

Consider… n X=U Ai i=1 Let U be the collection of all Hamiltonian Walks. Let Ai be the set of walks of length n passing through i. The set of walks that avoid i.

Consider… n X=U Ai i=1 |Z| |X| = |U| ( 1) Z [n] Ai i Z Let U be the collection of all Hamiltonian Walks. Let Ai be the set of walks of length n passing through i. The set of walks that avoid i.

Consider… n X=U Ai i=1 |Z| |X| = |U| ( 1) Z [n] Ai i Z Let U be the collection of all Hamiltonian Walks. Let Ai be the set of walks of length n passing through i. The set of walks that avoid i.

Consider… n X=U Ai i=1 |Z| |X| = |U| ( 1) Z [n] Ai i Z Let U be the collection of all Hamiltonian Walks. Let Ai be the set of walks of length n passing through i. The set of walks that avoid i. The set of walks that avoid X.

Consider… n X=U Ai i=1 |Z| |X| = |U| ( 1) Z [n] Ai i Z Let U be the collection of all Hamiltonian Walks. Let Ai be the set of walks of length n passing through i. The set of walks that avoid i. The set of walks that avoid X.

Polynomial Identity Testing Input: A polynomial p(x). Question: Is p(x) identically zero? (x1 + 3x2 x3 )(3x1 + x4 1) · · · (x7 x2 ) 0?

Polynomial Identity Testing Input: A polynomial p(x). Question: Is p(x) identically zero? (x1 + 3x2 x3 )(3x1 + x4 1) · · · (x7 x2 ) 0? Captures several problems, like checking if two polynomials are equal, finding a perfect matching, primality testing, and so on.

Basic Idea (x1 + 3x2 x3 )(3x1 + x4 1) · · · (x7 x2 ) Simplifying is expensive, but evaluating is cheap. 0?

Basic Idea (x1 + 3x2 x3 )(3x1 + x4 1) · · · (x7 x2 ) Simplifying is expensive, but evaluating is cheap. The probability that a random assignment corresponds to a root is low. 0?

Given a (directed) graph G and a number k… ! ! ! Let’s try to construct a polynomial that is zero ! if and only if ! G has a path of length k.

x[v1,2 ]x[v2,3 ] · ·2,3 ] · k· x[vk 1,k]y[v2 ] · · · 2 ] · · ·]y[vk ] x[v1,2 ]x[v · x[v· 1,k ]y[v1 1 ]y[v y[vk Edges Vertices

x[v1,2 ]x[v2,3 ] · ·2,3 ] · k· x[vk 1,k]y[v2 ] · · · 2 ] · · ·]y[vk ] x[v1,2 ]x[v · x[v· 1,k ]y[v1 1 ]y[v y[vk Edges Vertices We want terms corresponding to walks to cancel out,

x[v1,2 ]x[v2,3 ] · ·2,3 ] · k· x[vk 1,k]y[v2 ] · · · 2 ] · · ·]y[vk ] x[v1,2 ]x[v · x[v· 1,k ]y[v1 1 ]y[v y[vk Edges Vertices We want terms corresponding to walks to cancel out, somehow.

The Trick

Evaluate these polynomials over finite fields of characteristic two.

Evaluate these polynomials over finite fields of characteristic two. a+a=0

x[v1,2 ]x[v2,3 ] · ·2,3 ] · k· x[vk 1,k]y[v2 ] · · · 2 ] · · ·]y[vk ] x[v1,2 ]x[v · x[v· 1,k ]y[v1 1 ]y[v y[vk Edges Vertices

x[v1,2 ]x[v2,3 ] · ·2,3 ] · k· x[vk 1,k]y[v2 ] · · · 2 ] · · ·]y[vk ] x[v1,2 ]x[v · x[v· 1,k ]y[v1 1 ]y[v y[vk Edges 1,2 ]x[v2,3 ] · · · x[vk 1,k ]y[v1 ]y[v2 ] · · · y[vk ] Vertices

x[v1,2 ]x[v2,3 ] · ·2,3 ] · k· x[vk 1,k]y[v2 ] · · · 2 ] · · ·]y[vk ] x[v1,2 ]x[v · x[v· 1,k ]y[v1 1 ]y[v y[vk Edges 1,2 ]x[v2,3 ] · · · x[vk 1,k ]y[v1 ]y[v2 ] · · · y[vk ] Vertices

x[v1,2 ]x[v2,3 ] · ·2,3 ] · k· x[vk 1,k]y[v2 ] · · · 2 ] · · ·]y[vk ] x[v1,2 ]x[v · x[v· 1,k ]y[v1 1 ]y[v y[vk Edges 1,2 ]x[v2,3 ] · · · x[vk 1,k ]y[v1 ]y[v2 ] · · · y[vk ] Vertices

x[v1,2 ]x[v2,3 ] · ·2,3 ] · k· x[vk 1,k]y[v2 ] · · · 2 ] · · ·]y[vk ] x[v1,2 ]x[v · x[v· 1,k ]y[v1 1 ]y[v y[vk Edges 1,2 ]x[v2,3 ] · · · x[vk 1,k ]y[v1 ]y[v2 ] · · · y[vk ] 1,2 ]x[v2,3 ] · · · x[vk 1,k ]y[v1 ]y[v2 ] · · · y[vk ] 1,2 ]x[v2,3 ] · · · x[vk 1,k ]y[v1 ]y[v2 ] · · · y[vk ] 1,2 ]x[v2,3 ] · · · x[vk 1,k ]y[v1 ]y[v2 ] · · · y[vk ] 1,2 ]x[v2,3 ] · · · x[vk 1,k ]y[v1 ]y[v2 ] · · · y[vk ] Vertices

x[v1,2 ]x[v2,3 ] · ·2,3 ] · k· x[vk 1,k]y[v2 ] · · · 2 ] · · ·]y[vk ] x[v1,2 ]x[v · x[v· 1,k ]y[v1 1 ]y[v y[vk Edges 1,2 ]x[v2,3 ] · · · x[vk 1,k ]y[v1 ]y[v2 ] · · · y[vk ] 1,2 ]x[v2,3 ] · · · x[vk 1,k ]y[v1 ]y[v2 ] · · · y[vk ] 1,2 ]x[v2,3 ] · · · x[vk 1,k ]y[v1 ]y[v2 ] · · · y[vk ] 1,2 ]x[v2,3 ] · · · x[vk 1,k ]y[v1 ]y[v2 ] · · · y[vk ] 1,2 ]x[v2,3 ] · · · x[vk 1,k ]y[v1 ]y[v2 ] · · · y[vk ] Vertices

For a walk W, we will dump all these terms into the formula:

For a walk W, we will dump all these terms into the formula: :[k] [k] x[v1,2 ]x[v2,3 ] · · · x[vk 1,k ]y[v1 , (1)]y[v2 , (2)] · · · y[vk , (k)]

For a walk W, we will dump all these terms into the formula: :[k] [k] x[v1,2 ]x[v2,3 ] · · · x[vk 1,k ]y[v1 , (1)]y[v2 , (2)] · · · y[vk , (k)] Sum this over all walks W:

For a walk W, we will dump all these terms into the formula: :[k] [k] x[v1,2 ]x[v2,3 ] · · · x[vk 1,k ]y[v1 , (1)]y[v2 , (2)] · · · y[vk , (k)] Sum this over all walks W: (W, ) W:=v1 ,...,vk

This polynomial captures exactly the paths in G, i.e, it is identically zero precisely when G has no paths of length k.

(W, ) W:=v1 ,...,vk

(W, ) W:=v1 ,...,vk How do we evaluate this polynomial now?

(W, ) W:=v1 ,...,vk How do we evaluate this polynomial now?

Inclusion Exclusion RELOADED

Add a comment

Related presentations

Presentación que realice en el Evento Nacional de Gobierno Abierto, realizado los ...

In this presentation we will describe our experience developing with a highly dyna...

Presentation to the LITA Forum 7th November 2014 Albuquerque, NM

Un recorrido por los cambios que nos generará el wearabletech en el futuro

Um paralelo entre as novidades & mercado em Wearable Computing e Tecnologias Assis...

Microsoft finally joins the smartwatch and fitness tracker game by introducing the...

Related pages

Cumulants, lattice paths, and orthogonal polynomials ...

Read "Cumulants, lattice paths, and orthogonal polynomials" on DeepDyve - Instant access to the journals you need!
Read more

Lattice paths and orthogonal polynomials: a case study

Lattice paths and orthogonal polynomials: a case study Michael Anshelevich April 13, 2007
Read more

Cumulants, lattice paths, and orthogonal polynomials

A formula expressing free cumulants in terms of Jacobi parameters of the corresponding orthogonal polynomials is derived. It combines Flajolet's theory of ...
Read more

LATTICE PATHS AND FABER POLYNOMIALS - Brandeis Users' Home ...

LATTICE PATHS AND FABER POLYNOMIALS Ira M. Gessel1 and Sangwook Ree Department of Mathematics Brandeis University Waltham, MA 02254-9110 gessel@math ...
Read more

Polynomial - Wikipedia, the free encyclopedia

A composition of two polynomials is a polynomial, which is obtained by substituting a variable of the first polynomial by the second polynomial.
Read more

CiteSeerX — Paths and Kostka-Macdonald Polynomials

BibTeX @MISC{Kirillov09pathsand, author = {Anatol N. Kirillov and Reiho Sakamoto}, title = {Paths and Kostka-Macdonald Polynomials}, year = {2009}}
Read more

Potential polynomials and Motzkin paths | DeepDyve

Read "Potential polynomials and Motzkin paths" on DeepDyve - Instant access to the journals you need!
Read more

Solving Polynomials - Math is Fun - Maths Resources

Solving Polynomials A polynomial looks like this: example of a polynomial: ... We can directly solve polynomials of Degree 1 (linear) and 2 (quadratic)
Read more