Aktualny program seminarium
Jeśli chcesz otrzymywać regularnie aktualny plan referatów, to napisz do sekretarza seminarium.
| 18.03.2026 | Vera Chekan | HU Berlin |
| Tight Algorithmic Applications of Clique-Width Generalizations | ||
| \(\quad\)In this work, we study two natural generalizations of clique-width introduced by Martin Fürer. Multi-clique-width (mcw) allows every vertex to hold multiple labels [ITCS 2017], while for fusion-width~(fw) we have a possibility to merge all vertices of a certain label [LATIN 2014]. Fürer has shown that both parameters are upper-bounded by treewidth thus making them more appealing from an algorithmic perspective than clique-width and asked for applications of these parameters for problem solving. First, we determine the relation between these two parameters by showing that mcw <= fw + 1. Then we show that when parameterized by multi-clique-width, many problems (e.g., Connected Dominating Set) admit algorithms with the same running time as for clique-width despite the exponential gap between these two parameters. For some problems (e.g., Hamiltonian Cycle) we show an analogous result for fusion-width: For this we present an alternative view on fusion-width by introducing so-called glue-expressions which might be interesting on their own. All algorithms obtained in this work are tight up to (Strong) Exponential Time Hypothesis. \(\quad\)This is a joint work with Stefan Kratsch. | ||
Archiwalny program seminarium (rok akademicki 2025/2026)
| 11.03.2026 | Ryan Dewolfe | Toronto Metropolitan University |
| Benchmarking community detection with overlaps and outliers: a synthetic model and pragmatic performance measure | ||
| \(\quad\)Community detection, detecting groups of densely connected vertices in a graph, is a fundamental problem in unsupervised network science. Typical community detection algorithms make the strong assumption that each vertex must belong to exactly one community; that is, the communities form a partition. In this talk, we relax this restriction by allowing vertices to be part of many communities (overlap) or no communities (outliers). We cover an extension of the Artificial Benchmark for Community Detection (ABCD), a synthetic graph model with known community structure, to have overlaps and outliers. We will also discuss a recent method for comparing the detected communities to the known communities, which is used to benchmark community detection algorithms. | ||
| 04.03.2026 | Jarosław Grytczuk | PW |
| Problemata duplex | ||
| \(\quad\)Dupleksem nazywamy słowo, które można rozłożyć na dwa identyczne podsłowa. Na przykład słowo ABACBC jest dupleksem zbudowanym z dwóch przeplatających się kopii słowa ABC. Szczególnym przypadkiem dupleksu jest repetycja, czyli słowo będące sklejeniem dwóch kopii tego samego słowa, np. ABCABC. Wiadomo, że istnieją dowolnie długie słowa zbudowane z jedynie trzech liter bez bloków będących repetycjami. Ile liter potrzeba do zbudowania dowolnie długich słów bez bloków będących dupleksami — nie wiadomo. Nie wiadomo też wielu innych rzeczy o dupleksach oraz ich naturalnym uogólnieniu, czyli multipleksach. Na przykład, czy każde nieskończone słowo binarne musi zawierać multipleksy o dowolnie dużej krotności? Tajemnicą owiana jest także dokładna wartość stałej duplikacyjnej, czyli współczynnika decydującego o szybkości mutacji genetycznej opartej na repetycjach tandemowych. Pojęcie dupleksu można właściwie rozważać w kontekście dowolnej struktury kombinatorycznej. Istnieją zatem dupleksy permutacyjne, grafowe, matroidowe, geometryczne, topologiczne, mierzalne itd. Można też rozmaicie osłabiać to pojęcie, dopuszczając różnego typu podobieństwa podstruktur. | ||
| 21.01.2026 | Konstanty Junosza-Szaniawski | PW |
| Kolorowanie grafów mieszanych | ||
| \(\quad\)Graf mieszany definiuje się jako trójkę \((V, E, A)\), gdzie: \(V\) to zbiór wierzchołków, \(E\) to zbiór krawędzi nieskierowanych, \(A\) to zbiór krawędzi skierowanych (łuków). Poprawnym kolorowaniem grafu mieszanego nazywamy przypisanie dodatnich liczb całkowitych (kolorów) do wierzchołków w taki sposób, że: sąsiadujące wierzchołki połączone krawędzią nieskierowaną otrzymują różne kolory, a dla każdej krawędzi skierowanej \((u, v) \in A\), kolor przypisany wierzchołkowi \(v\) jest ściśle większy niż kolor przypisany wierzchołkowi \(u\). \(\quad\)Przedstawię dwa algorytmy wyznaczającą minimalną liczbę kolorów potrzebnych do poprawnego pokolorowania grafu mieszanego. Pierwszy algorytm ma wykładniczą złożoność pamięciową, drugi wielomianową. Analiza złożoności obliczeniowej tych algorytmów, wiąże sie z interesującym problemem ekstremalnej teorii grafów. \(\quad\)Prezentowane wyniki są współautorskie z: Grzegorz Gutowski, Antonio Lauerbach, Paweł Rzążewski, Alexander Wolff. | ||
| 14.01.2026 | Paweł Pękała | AGH |
| Większościowe kolorowania krawędzi grafów | ||
| \(\quad\)Większościowym kolorowaniem krawędzi grafu \(G\) nazywamy kolorowanie krawędzi tego grafu takie, że dla każdego wierzchołka grafu \(G\) co najwyżej połowa krawędzi incydentnych z tym wierzchołkiem ma taki sam kolor. Naturalnym uogólnieniem tego problemu są \(\frac{1}{k}\)-większościowe kolorowania krawędzi. W tym wariancie problemu, dla ustalonej liczby naturalnej \(k\), chcemy znaleźć takie kolorowanie krawędzi grafu, że dla każdego wierzchołka co najwyżej \(\frac{1}{k}\)-ta krawędzi z nim incydentnych ma taki sam kolor. W referacie pokażemy ograniczenia na minimalny stopień grafu, który gwarantuje istnienie 1/k-większościowych kolorowań krawędzi za pomocą \(k+1\) kolorów. Rozważymy także wersję listową tego problemu. \(\quad\)Współautor: Jakub Przybyło. | ||
| 07.01.2026 | Karolina Okrasa | PW, University of Oxford |
| Strong sparsification for 1-in-3-Sat | ||
| \(\quad\)We introduce a new notion of sparsification, called strong sparsification, in which constraints are not removed but variables can be merged. Using the prominent results from the area of additive combinatorics, we show that the instances of 1-in-3-Sat can be strongly sparsified so that the number of clauses becomes subquadratic. As an application, we improve the state-of-the-art algorithm for approximating linearly-ordered colourings of 3-uniform hypergraph, one of the generalizations of the classic notion of graph colouring. \(\quad\)Joint work with B. Bedert, T.-V. Nakajima, and S. Živný | ||
| 17.12.2025 (102) | Maria Chudnovsky | Princeton University |
| Strip Structures: past and present | ||
| \(\quad\)An independent set S of vertices is "constricted" in a graph G if no induced tree in G contains 3 elements of S. In 2009 Paul Seymour and the speaker proved a theorem describing the structure of constricted sets in graphs. It turns out that if a graph G contains a constricted set Z, then G admits a "strip structure", which is to say that it roughly resembles a line graph. Moreover, the location of the vertices of Z is tightly controlled. This result is called "3-In-A-Tree". \(\quad\)The original motivation behind 3-In-A-Tree was to provide a recognition algorithm for induced thetas in graphs, but recently it has been reincarnated. In modern graph optimization algorithms it is used to produce small dominating sets in graphs, or to allow for other ways to track the progress of an algorithm. \(\quad\)In this talk we will explain the theorem, and illustrate some of its applications. | ||
| 10.12.2025 | Tomasz Kościuszko | UAM |
| Zbiór popularnych sum i jego zastosowania w kombinatorycznej teorii liczb | ||
| \(\quad\)Motywem przewodnim referatu będzie zbiór popularnych sum pewnego skończonego podzbioru liczb naturalnych \(A\). Każdy element ze zbioru wszystkich sum \(A+A\) można wyrazić jako sumę dwóch liczb z \(A\) na średnio \(\frac{|A|^2}{|A+A|}\) sposobów. Popularne sumy to takie, które przekraczają ten próg (pomnożony przez wybraną małą stałą): \(P = \Bigl\{s\in A+A : 1_A*1_A(s)\geq \frac{|A|^2}{10\cdot |A+A|}\Bigr\}.\) Tutaj \(1_A*1_A(s)\) oznacza splot, czyli dokładnie liczbę par \((a,b)\in A\times A\) sumujących się do \(s\). \(\quad\)Wspomnimy o wyniku Sandersa [1], który mówi że w zbiorze popularnych sum można znaleźć ciekawe struktury takie jak ciągi arytmetyczne czy zbiory Bohra (tam musimy rozważać popularne sumy w \(A+A+A+A\)). Budując na tym przedstawimy wynik autora [2], który pozwala na znalezienie wielu rozwiązań równań liniowych w gęstych zbiorach liczb. Jeśli czas pozwoli opiszemy również inne kombinatoryczne zastosowania. [1] T. Sanders, On the Bogolyubov–Ruzsa lemma. Anal. PDE 5 (3) 627 - 655, 2012. [2] _, Invariant Equations in Many Variables. Electronic Journal of Combinatorics, Volume 32, Issue 3 (2025) | ||
| 26.11.2025 | Przemysław Gordinowicz | Politechnika Łódzka |
| Dominacyjna liczba drzewiasta | ||
| \(\quad\)Przedmiotem referatu są dekompozycje drzewiaste w których wielkość worka (bagu) opisywana jest przez liczbę dominującą odpowiedniego podgrafu. Pokazany zostanie opis przez rozgrywane przeszukiwaniem grafów oraz związek tytułowego parametru z drzewiastą dekompozycją hipergrafów. Oraz całkiem sporo problemów czekających na rozwiązanie. | ||
| 19.11.2025 | Paweł Rzążewski | PW |
| Problem zbioru niezależnego w grafach uporządkowanych, c.d. | ||
| \(\quad\)Kontynuujemy rozważania na temat problemu największego zbioru niezależnego w klasach grafów uporządkowanych z wykluczonym ustalonym podgrafem indukowanym. Tym razem skupimy się na algorytmach. Wyniki uzyskane we współpracy z Pawłem Rafałem Bielińskim i Martą Piecyk. | ||
| 12.11.2025 | Paweł Rafał Bieliński | PW |
| KTGiZU na kółku matematycznym | ||
| \(\quad\)Zaprezentuję garść problemów z olimpiad matematycznych szczebla międzynarodowego. Ich wspólną cechą jest (nieraz dość błyskotliwe) wykorzystanie metod K, TG i ZU. Przedstawię również klasyczne twierdzenie Steinitza, które wiąże zbiór niezależny w grafie z możliwością wpisania wielościanu w sferę. | ||
| 29.10.2025 | Seminarium odwołane |
| 22.10.2025 | Hubert Grochowski | PW |
| Grafy XOR-magiczne | ||
| \(\quad\) Graf \(G\) o \(2^n\) wierzchołkach nazwiemy grafem otwarcie (domknięcie) XOR-magicznym, jeśli jest spójny i istnieje bijekcja ze zbioru wierzchołków grafu G w zbiór ciągów binarnych długości n taka, że dla każdego wierzchołka tego grafu, suma etykiet wierzchołków w jego otwartym (domkniętym) sąsiedztwie jest równa wektorowi zerowemu. \(\quad\)W jednej z prac dotyczących tego tematu [1], Batal badał problem istnienia regularnych grafów XOR-magicznych. W szczególności, postawił on problem otwarty: czy istnieje graf nieparzyście (parzyście) regularny graf otwarcie (domknięcie) XOR-magiczny? \(\quad\)W trakcie referatu odpowiemy pozytywnie na wyżej wymieniony problem, pokazując istnienie takich grafów rzędu \(2^n\) dla każdego \(n\) większego od 3. Ponadto, przedstawimy warunek konieczny (w nurcie spektralnej teorii grafów) istnienia grafów otwarcie XOR-magicznych wraz z jego zastosowaniami do wybranych grafów Cayleya. \(\quad\)Współautorki: Sylwia Cichacz, Rita Zuazua [1] A. Batal, On the construction of XOR-magic graphs, Discrete Applied Mathematics 379 (2026), 288-315. | ||
| 15.10.2025 | Tomasz Krawczyk | PW |
| Problem Defensywnej Dominacji w klasie grafów przedziałowych | ||
| \(\quad\)W problemie Defensywnej Dominacji dla danego grafu G oraz liczb naturalnych l i k należy rozstrzygnąć, czy na wierzchołkach grafu G można rozmieścić l obrońców w taki sposób, aby chronili oni przed atakiem każdy podzbiór A wierzchołków o rozmiarze co najwyżej k (tzn. każdemu wierzchołkowi z atakowanego zbioru A można przypisać prywatnego obrońcę znajdującego się w tym wierzchołku lub w jego sąsiedztwie). Wiadomo, że problem Defensywnej Dominacji jest \(\Sigma_2^P\)-zupełny. Niestety, nie jest znany jego status złożonościowy w prostych klasach grafów, takich jak grafy przedziałowe czy grafy planarne. W swoim referacie przedstawię prosty algorytm zachłanny rozwiązujący problem Defensywnej Dominacji w klasie grafów przedziałowych w przypadku, gdy w każdym wierzchołku grafu można umieścić dowolną liczbę obrońców. Pokażę również, jaki związek zachodzi między klasycznym problemem Defensywnej Dominacji (co najwyżej jeden obrońca na wierzchołek) a problemem plecakowym. | ||
| 08.10.2025 | Paweł Rafał Bieliński | PW |
| Problem zbioru niezależnego w grafach uporządkowanych | ||
| \(\quad\)Wiele trudnych problemów algorytmicznych może być rozwiązane wydajniej w węższym zakresie sytuacji. Przykładem takiego podejścia jest rozważanie nie grafów dowolnych, ale tylko tych nie zawierających określonej podstruktury. W swoim referacie zaprezentuję wyniki dotyczące trudności problemu zbioru niezależnego w klasach grafów uporządkowanych wolnych od określonych podgrafów indukowanych. Przy pomocy odpowiednich redukcji wskażę szereg przypadków NP-trudnych, a poprzez konkretne algorytmy i wnioski strukturalne zidentyfikuję przypadki, które można rozwiązać w czasie wielomianowym. | ||