Strona główna > Aktualny program seminarium
Aktualny program seminarium
Jeśli chcesz otrzymywać regularnie aktualny plan referatów to napisz do sekretarza seminarium.
22.01
Tomasz Krawczyk
O pewnym uogólnieniu problemu zbioru dominującego
Streszczenie:
Na swoim referacie wprowadzę pewne uogólnienie problemu zbioru dominującego w grafie, wyrażonego w terminach rozkładu żetonów po wierzchołkach grafu.
Rozkładając żetony po wierzchołkach zbioru dominującego grafu spełniony jest warunek, że dla każdego wierzchołka grafu
albo na tym wierzchołku albo na pewnym jego sąsiedzie leży żeton. Własność tę chcemy teraz wzmocnić tak, aby teraz dla każdego zbioru A liczności co najwyżej k
każdy wierzchołek tego zbioru mógł wybrać swój prywatny żeton, który znajduje się na tym wierzchołku lub pewnym jego sąsiedzie.
Rozkład żetonów po wierzchołkach grafu (na jednym wierzchołku można umieścić kilka żetonów), który posiada taką własność, nazywamy k-zabezpieczającym.
Oczywiście, rozkład żetonów jest 1-zabezpieczający jeżeli wierzchołki z żetonem odpowiadają zbiorowi dominującemu w grafie.
W trakcie referatu zaprezentuję kilka prostych wyników złożonościowych dotyczących problemów związanych z k-zabezpieczającymi rozkładami żetonów w grafie.
Pokażę, że:
- problem testowania, czy rozkład żetonów jest k-zabezpieczający, jest NP-zupełny, zaś parametryzowany liczbą k jest W[1]-trudny,
- problem testowania, czy rozkład żetonów w grafie planarnym jest k-zabezpieczający, należy do klasy FPT,
- problem testowania, czy istnieje k-zabezpieczający rozkład wykorzystujący co najwyżej n żetonów, jest Sigma^P_2-zupełny.
Poprzednie referaty (rok akademicki 2024/2025):
15.01
Paweł Prałat (Toronto Metropolitan University)
Asynchronous Majority Dynamics on Binomial Random Graphs
Abstract:
We study information aggregation in networks when agents interact to learn a binary state of the world. Initially each agent privately observes an independent signal which is correct with probability $1/2+delta$ for some $delta > 0$. At each round, a node is selected uniformly at random to update their public opinion to match the majority of their neighbours (breaking ties in favour of their initial private signal). Our main result shows that for sparse and connected binomial random graphs $G(n,p)$ the process stabilizes in a correct consensus in $O(nlog^2 n/loglog n)$ steps with high probability. In fact, when $log n/n ll p = o(1)$ the process terminates at time $hat T = (1+o(1))nlog n$, where $hat T$ is the first time when all nodes have been selected at least once. However, in dense binomial random graphs with $p=Omega(1)$, there is an information cascade where the process terminates in the incorrect consensus with probability bounded away from zero.
8.01
Seminarium odwołane.
Obowiązuje plan poniedziałkowy na PW.
18.12
Zbigniew Lonc
O sprawiedliwych podziałach drzew
Streszczenie:
Załóżmy, że mamy zbiór niepodzielnych dóbr, które są reprezentowane jako wierzchołki grafu, oraz zbiór agentów. Każdy agent dysponuje funkcją użyteczności, która przypisuje każdemu dobru określoną wartość, odzwierciedlając jego subiektywną ocenę. Naszym celem jest podział tego zbioru między agentów w sposób spełniający określone kryterium sprawiedliwości, przy czym każda część przypisana agentowi musi stanowić spójny podgraf w grafie dóbr. Koncentrujemy się na tzw. kryterium maksyminimalnym. Wiadomo, że jeśli graf dóbr jest drzewem, to podział zapewniający każdemu agentowi jego spójną część o akceptowanej przez niego wartości zawsze istnieje. Rozważmy teraz analogiczny problem, w którym zamiast dóbr występują "antydobra", tj. wierzchołki drzewa mają ujemne wartości dla wszystkich agentów. Taka sytuacja występuje na przykład wtedy, gdy dzielmy się uciążliwymi obowiązkami. Problem, czy w takim modelu możliwe jest podzielenie drzewa między agentów w sposób spełniający maksyminimalne kryterium sprawiedliwości, jest otwarty. W referacie pokażemy wyniki częściowo potwierdzające hipotezę, że tak w istocie jest.
11.12
Tibor Szabó (Freie Universität Berlin)
Global rigidty of random graphs in $mathbb{R}$
Abstract:
We are interested in the distances between all pairs of points in a set $Psubseteq mathbb{R}$, but we only have access to the distances between some of them. Which properties of the graph $G$ of known distances on the vertex set $P$ are sufficient for the unique ''reconstruction'' of $P$, up to isometry? It is computationally difficult to decide about an input graph whether it reconstructs every point set and we investigate how the random graph does. Resolving a conjecture of Benjamini and Tzalik, we prove that as soon as the random graph process has minimum degree 2 with high probability it can reconstruct the distances in any point set in $mathbb{R}$. We also study the possibility/limitation of reconstruction of the distances among almost all points using much sparser random graphs. In this direction we resolve a question of Girao, Illingworth, Michel, Powierski, and Scott.
Joint work with Richard Montgomery, Rajko Nenadov, and Julien Portier.
4.12
Michał Ziembowski
Algebry ścieżek Leavitta
Streszczenie:
Niech K będzie ciałem, a E skierowanym grafem. Podczas referatu przedstawiona zostanie konstrukcja bogatej klasy maksymalnych przemiennych podalgebr algebry ścieżek Leavitta L_K(E), co stanowi daleko idące uogólnienie konstrukcji tzw. jądra przemiennego algebry L_K(E).
27.11
Václav Blažej (University of Warwick)
On the Parameterized Complexity of Eulerian Strong Component Arc Deletion
Abstract:
In this talk we will explore the Eulerian Strong Component Arc Deletion problem, where the input is a directed multigraph and the goal is to delete the minimum number of arcs to ensure every strongly connected component of the resulting digraph is Eulerian. This problem is a natural extension of the Directed Feedback Arc Set problem. The complexity of the problem, when parameterized by solution size (i.e., size of the deletion set), has remained unresolved and has been highlighted in several papers. We answer this question and conduct a broad analysis of the problem with respect to other natural parameterizations.
20.11
Nadzieja Hodur (AGH)
3-kolorowalność i podgrafy zabronione
Streszczenie:
Mówimy, że graf G jest grafem bez H, jeśli G nie zawiera H jako podgrafu indukowanego. Bykiem nazywamy graf K_3 z dwiema dodatkowymi krawędziami wiszącymi, incydentnymi do dwóch różnych wierzchołków trójkąta. W klasie grafów bez byka problem 3-kolorowalności pozostaje NP-zupełny. Jednak w klasie grafów bez byka i bez jednej z gwiazd, S(1, 1, 2) lub S(1, 2, 2), można znaleźć wielomianowy algorytm rozstrzygający 3-kolorowalność, zwracający 3-kolorowanie właściwe danego grafu, jeżeli takie istnieje, lub prosty podgraf, wymagający większej liczby kolorów, jeżeli dany graf nie jest 3-kolorowalny.
W trakcie referatu zostaną zaprezentowane tego rodzaju algorytmy dla dwóch klas grafów: bez byka i bez S(1, 1, 2) oraz bez byka i bez S(1, 2, 2).
W trakcie referatu zostaną zaprezentowane tego rodzaju algorytmy dla dwóch klas grafów: bez byka i bez S(1, 1, 2) oraz bez byka i bez S(1, 2, 2).
13.11
Hubert Grochowski
Problem przycinania bambusów w ogrodzie
Streszczenie:
Wyobraźmy sobie ogród, w którym rośnie N bambusów (ponumerowanych kolejno od 1 do N) takich, że i-ty bambus rośnie na koniec dnia o wysokość h_i > 0. W ogrodzie mieszka też robotyczna panda, która każdego dnia wybiera jeden bambus i obcina go do zera. Naszym celem jest zaprojektować taki harmonogram strzyżenia dla pandy, aby najwyższy bambus, jaki kiedykolwiek pojawi się w ogrodzie, był jak najniższy. Problem ten został postawiony w literaturze w 2017 przez Gąsieńca i innych [1]. W trakcie referatu omówię ten problem, przedstawię algorytmy aproksymacyjne i wskażę możliwe kierunki badań.
[1] Gąsieniec, L., Klasing, R., Levcopoulos, C., Lingas, A., Min, J., & Radzik, T. (2017). Bamboo Garden Trimming Problem (Perpetual Maintenance of Machines with Different Attendance Urgency Factors). In Lecture Notes in Computer Science (pp. 229–240). Springer International Publishing. https://doi.org/10.1007/978-3-319-51963-0_18
06.11
Seminarium odwołane.
30.10
Marta Piecyk
Homomorfizmy grafów o ograniczonej średnicy
Streszczenie:
Dla ustalonego grafu H, w problemie homomorfizmu grafów, ozn. Hom(H), mamy dany graf G i pytamy, czy istnieje funkcja f: V(G) -> V(H), która zachowuje krawędzie. Jeśli H jest trójkątem, to Hom(H) jest równoważny z problemem 3-kolorowania. Nie jest wiadomo, czy istnieje wielomianowy algorytm dla 3-kolorowania grafów o średnicy dwa.
Podczas referatu będę rozważać problem Hom(C_{2k+1}) w grafach o ograniczonej średnicy dla k>=2, czyli w przypadku wszystkich nieparzystych cykli innych niż trójkąt. Pokażę wielomianowy algorytm dla Hom(C_{2k+1}) dla grafów o średnicy k+1 -- taki wynik w przypadku k=1 byłby dokładnie wielomianowym algorytmem dla 3-kolorowania grafów o średnicy 2.
23.10
Paweł Rzążewski
An 11/6-Approximation Algorithm for Vertex Cover on String Graphs
Abstract:
We present a 1.8334-approximation algorithm for Vertex Cover on string graphs given with a representation, which takes polynomial time in the size of the representation; the exact approximation factor is 11/6. Recently, the barrier of 2 was broken by Lokshtanov et al. [SoGC '24] with a 1.9999-approximation algorithm. Thus we increase by three orders of magnitude the distance of the approximation ratio to the trivial bound of 2. Our algorithm is very simple. The intricacies reside in its analysis, where we mainly establish that string graphs without odd cycles of length at most 11 are 8-colorable. Previously, Chudnovsky, Scott, and Seymour [JCTB '21] showed that string graphs without odd cycles of length at most 7 are 80-colorable, and string graphs without odd cycles of length at most 5 have bounded chromatic number.
The talk is based on joint work with Édouard Bonnet.
16.10
Tara Abrishami (University of Hamburg)
Locally chordal graphs
Abstract:
In this talk, I will discuss recent results concerning graphs which behave locally like chordal graphs. A graph is chordal if each of its cycles of length at least four has a chord. Chordal graphs have strong structural properties and many equivalent characterizations. They also have algorithmic applications, for example to the maximum independent set problem. The question we aim to answer is: what can we say about graphs which are locally, but not globally, chordal? First, we will discuss three candidate definitions for locally chordal graphs. Next, we will explain local generalizations of two characterizations of chordal graphs: that chordal graphs are intersection graphs of subtrees of a tree, and that chordal graphs are graphs with tree-decompositions into maximal cliques. Finally, we will look at algorithmic applications of locally chordal graphs. This talk is based on joint work with Raphael Jacobs, Paul Knappe, Jonas Kobler, and Jakob Stegemann.
09.10
Konstanty Junosza-Szaniawski
O minimalizacji kliki przecięć tras w routingu na cyklu
Streszczenie:
Dla cyklu i listy żądań czyli par jego wierzchołków szukamy wyboru ścieżek łączących wierzchołki z żądań, tak aby zminimalizować rozmiar najliczniejszej kliki w grafie przecięć wybranych ścieżek. Opowiem o złożoności tego problemu, przedstawię prosty kombinatoryczny algorytm 2-approksymacyjny oraz 3/2-aproksymacyjny oparty na programowaniu liniowym. Referat będzie oparty o pracę [1] i myślę że potrwa krócej niż zwykle.
[1] Stamati Stefanakos and Thomas Erlebach. Routing in all-optical ring networks revisited. Proceedings. ISCC 2004. Ninth International Symposium on Computers and Communications, volume 1, 288–293, 2004
02.10
Monika Pilśniak (AGH)
The Unfriendly Partition Conjecture holds for line graphs
Streszczenie:
A colouring of edges of a graph $G$ is a majority colouring, if for every vertex $v$ of $G$, at most half the edges incident with $v$ have the same colour. This concept was
recently introduced in [1], where, among others, it was proved that every finite graph without pendant vertices admits a majority 4-edge colouring. Moreover, if the minimum degree of $G$ is at least 4, then $G$ admits a majority 3-edge colouring.In the talk, the list version of the problem is investigated, also for infinite graphs. As a consequence of our results, the Unfriendly Partition Conjecture (cf. Diestel's book) is confirmed for line graphs.
[1] F. Bock, R. Kalinowski, J. Pardey, M. Pilśniak, D. Rautenbach, and M.Woźniak, Majority Edge-Colorings of Graphs, Electron. J. Combin. 30(1) 2023 #P1.42.