Έστω M = (E,I) μητροειδές και S = {S1,...,St} οικογένεια υποσυνόλων του E με |Si| = p
∀i ∈ {1, . . . , t}. Μια υποοικογένεια S′ ⊆ S ονομάζεται q-αντιπροσωπευτική της S, αν για κάθε σύνολο
της οικογένειας S που μπορεί να επεκταθεί σε μεγαλύτερο ανεξάρτητο σύνολο προσθέτοντας του q
νέα στοιχεία υπάρχει και κάποιο σύνολο της υποοικογένειας S′, το οποίο μπορεί να επεκταθεί σε
μεγαλύτερο ανεξάρτητο σύνολο προσθέτοντας του τα ίδια q στοιχεία. Από το Θεώρημα Δύο Οικογενειών
του Bollobás και τη γενικευσή του σε διανυσματικούς χώρους από τον Lovász, προκύπτει ότι υπάρχει
q-αντιπροσωπευτική οικογένεια με το πολύ (p+q) ανά p σύνολα.
Σε αυτήν την εργασία, δίνουμε δύο αλγορίθμους για την κατασκευή αντιπροσωπευτικής οικογένειας μεγέθους (p+q) ανά p. Ο πρώτος αλγόριθμος αφορά τα γραμμικά μητροειδή και «αλγοριθμοποιεί» την από-
δειξη του Lovász κατασκευάζοντας οικογένεια σε χρόνο πολυωνυμικό ως προς (p+q) ανά p, t και τον χρόνο
που απαιτείται για την πραγματοποίηση μιας πράξης σε κάποιο σώμα F. Ο δεύτερος αφορά μόνο τα ομοιόμορφα μητροειδή και τρέχει σε O((1 − x)^{−q} · 2^{o(p+q)} · t · log n) χρόνο.
Στη συνέχεια, δείχνουμε πως υπολογίζοντας αποδοτικά αντιπροσωπευτικές οικογένειες, μπορούμε να κατασκευάσουμε γρήγορους παραμετρικούς αλγορίθμους για τα ακόλουθα προβλήματα: ΤΟΜΗ l-ΜΗΤΡΟΕΙΔΩΝ, ΜΑΚΡΥΣ ΚΑΤΕΥΘΥΝΟΜΕΝΟΣ ΚΥΚΛΟΣ και k-ΜΟΝΟΠΑΤΙ.
(EL)
Let $M = (E, I)$ be a matroid and let $\mathcal{S} = {S_1, ... , S_t}$ be a family of subsets of $E$ of size $p$. A subfamily of $\mathcal{S}$ is said to be $q$-representative for $\mathcal{S}$ if some independent set in S can be extended to a larger independent set by $q$ new elements, then there is a set in subfamily that can be extended by the same $q$ elements. By the Two Families Theorem of Bollobás and its algebraic version by Lovász, there is a $q$-representative family with at most sets.
In this paper, we give two algorithms computing representative families. The first algorithm is about linear matroids and it turns Lovász ’s proof into an algorithm constructing a $q$-representative family in time bounded by a polynomial in $\binom{p+q}{p}$, $t$ and the time required for field operations. The second one is
about uniform matroids and computes a representative family in time $\mathcal{O}((1-x)^{-q} 2^{o(p+q)|} t logn)$.
We demonstrate how the efficient construction of representative families can be a powerful tool for designing parameterized algorithms for the following problems: ℓ-MATROID INTERSECTION, LONG DIRECTED CYCLE and k-PATH.
(EN)
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
