Understanding Matroids and Representative Sets in Game Theory

Slide Note

Explore the concept of matroids and representative sets in game theory, focusing on Alice vs. Bob scenarios where Alice aims to win by strategically selecting sets. Learn how Bollob's Lemma plays a key role in helping Alice reduce the number of sets she needs to remember to secure victory.

kluesner_j Follow

Uploaded on Sep 16, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript

Matroids & Representative Sets Daniel Lokshtanov

Alice vs Bob F = {{a,b,c}, {a,c,d}, {b,c,e}} {b, e} {a, c} {a,c,d}

Rules of the game Board: universe of size n All Alice s sets have size p Bob a picks set B of size q Alice wins if she has a set disjoint from B

Lazy Alice Alice does not like remembering all those sets. Alice hates losing to Bob. Can she forget a set A from F, and be sure this will not make the difference between winning and losing?

(Ir)relevant Sets A F is irrelevant if: for every set B of size q such that A B = , there is a set A F such that A B = . Alice may forget exactly the irrelevant sets

Only relevant sets? F = { Am} A2 A3 A1 B1 B2 B3 Bm

Bollobs Lemma [1966] Let ?? ??= A1, A2, , Am be sets of size p and ?? ?? No dependence on B1, B2, , Bm be sets of size q s.t: universe size n at all! ?+? ? then m .

Bollobs helps Alice Bollob s lemma immediately implies that Alice only needs to remember at most m sets. yay! ?+? ?

Proof of Bollobs Lemma Consider a random permutation of the universe. Ai Bj Bi Aj 1 P[all of Ai is before all of Bi] = . ?+? ? The events all of Ai before all of Bi and All of Aj before all of Bj are disjoint! 1 ?+? ? ? 1 and hence m So . ?+? ?

Representative Sets Let F be a family of p-sets. Then ? ? q-represents F if for every B of size q such that there exists an ? ? with ? ? = there exists an ? ? with ? ? = . Corollary of Bollob s: For every F there is an ? ? of size at most ?+? ? that q-represents F.

Computational Problem Given a family F of p-sets and an integer q, compute a family F F of size at most that q-represents F. ?+? ?

Computing Representative Sets Will show: we can compute representative sets ? 1 ?+? ? in time essentially O |F| where ? is the matrix multiplication constant < 2.38. But first an easy application

d-Hitting Set Input: Family F = {S1, ,Sm} of sets of size d over universe U = {v1, , vn}, integer k. Question: Does there exist a set X U of size at most k such that for every Si F, Si X ? Easy branching in time dk Next: kernel with O(kd) sets and elements

d-Hitting Set as a Game F = {{a,b,c}, {a,c,d}, {b,c,e}} Is {b, e} a hitting set? No, since {a,c,d}

Kernel for d-Hitting Set Compute a k-representative subfamily F F of size at most ?+? ? ??. Remove all elements not in F (at most dkd) Output the instance F , k.

Why is the kernel correct? May not change a YES instance into a NO instance. Can a NO instance change into a YES instance? NO instance = Alice always wins YES instance = Bob can win We did not forget any sets that made the difference between Alice winning and losing!

Playing on a matroid Suppose now that the universe is the edge set of a matroid. A set A fits a set B if - A and B are disjoint and - A B is independent in the matroid.

Alice vs Bob on a matroid F = {{a,b,c}, {a,c,d}, {b,c,e}} Note: this game on a uniform matroid of rank p+q is exactly the old game. Do you have a set that fits {b, e}? &% &!!

Representative Sets Let F be a family of p-sets (in a matroid M). Then ? ? q-represents F if: for every B of size q such that there exists an ? ? that fits B there exists an ? ? that also fits B. Note: representation in a uniform matroid of rank p+q is exactly the old representation.

Computing Representative Sets Input: Family F of p-sets over a matroid, integer q, matrix M representing the matroid. Task: Compute a q-representative subfamily F F of size at most ?+? ? .

Playing on a matroid p=4, q=2 ! F ? 232401 018920 320110 848338 053002 0? Det 304958029038502923840293850230905801012095830321520385 292302302310958042093582023039528303202335020322022582 2202302350203209802104+4267429810983502239582820320502 340958683040938323035802092309532029385308209821522998 208357298739829872398253982359823987235239729019380205 230958203958293958203958203958203958522938572938575292 M = p+q

Fit vs Determinant If Alices set A and Bob s set B overlap, then the same column is used twice determinant is 0! Determinant is nonzero if and only if A fits B.

Matrix game p q a c p+q b d p+q c

Generalized Laplace Expansion almost correct p q Det To compute p+q MA MB Compute the determinants of all p p submatrices of MA Compute the determinants of all q q submatrices of MB ?+? ? dimensional vector vA ?+? ? dimensional vector vB dot product!*

Giant Vector game ? + ? ? ? + ? ? a b c d 0 ? c

Basis If Alice keeps vectors v1,v2,v3 and v3 = v1 + v2 and v3 fits Bob s vector vB Then either v1 or v2 fits vB Alice only needs to keep linearly independent vectors! ?+? ? At most of them, since ?+? ? vectors are - dimensional Finding the basis ? 1 ?+? ? takes O |F| time.

Wrap up Alice has a family of p-sets, family of p (p+q) matrices ?+? ? family of - dimensonal vectors. Keep linearly independent vectors, keep the corresponding sets!

Computing Representative Sets Theorem: we can compute representative sets of size ? 1 ?+? ? is the matrix multiplication constant < 2.38. ?+? ? in time essentially O |F| where ?

Application - Treewidth DP Have seen several approaches for single exponential algorithms for connectivity problems parameterized by treewidth. Representative sets gives yet another one

Hamiltonian Path

Representative Sets for Matroid Classes Is it possible to compute representative sets for uniform matroids, graphic matroids or transversal matroids faster than for linear matroids in general? For uniform matroids, the answer is yes (but proof is sort of complicated)

Application k-Path Input: (directed) graph G, integer k. Question: Is there a simple directed path on k vertices? Theorem: There is a deterministic 2.84????? ? time algorithm for k-Path.

k-Path Fix a source vertex u. For vertex v and integer p, define P[v,p] to be the set of (vertex sets of) paths on exactly p vertices from u to v. Goal: for every v and p k compute a set P [v,p] that (k-p)-represents P[v,p].

k-Path Goal: for every v, p k compute a set P [v,p] that (k-p)-represents P[v,p]. assuming P w,p 1 (k-p+1)-represents P[w,p-1] Need to prove: that X v,p (k-p)-represents P[v,p] P u,1 = u P w,p 1 {v} X v,p = wv E(G) Extend all paths that can be extended by v P v,p = reduce(X v,p ,k p)

Need to prove: that X v,p (k-p)-represents P[v,p] assuming P w,p 1 (k-p+1)-represents P[w,p-1] BB Size q+1 u v w In X v,p In P w,p 1

k-Path ? Size of family to reduce: 2?(?) n ? 1 ? ? ? ? Time to reduce: 2?(?) n ? 1 ? ? Total time: 2.84????? ? Also works for weighted k-Path.

Application k-Cycle Input: (directed) graph G, integer k. Question: Is there a simple directed cycle on at least k vertices? Theorem: 8kpoly(n) algorithm.

k-Cycle main lemma In a shortest cycle C on at least k vertices, we can replace any subpath on k vertices by any other path on k vertices, which is disjoint from the k vertices after it on C.

k-Cycle main lemma proof u Puv Pwv v w Pvw

k-Cycle algorithm Guess a vertex u that a shortest cycle C of length at least k passes through. ?+? ? 4? Size: For every vertex v and integer p, define P[u, p] to be the set of (vertex sets of) paths on exactly p vertices from u to v. For every vertex v compute a set P [v] that k- represents P[v,k] using the method from the k-path algorithm.

k-Cycle algorithm Guess the k th vertex v on the cycle C. Main lemma there is a k-cycle containing a path from P [v] as a subpath! Check whether there is a path Q in P [v] such that there is a path back from v to u in G\Q. Time 8kpoly(n).