| Naslov: | Graph classes closed under self-intersection |
|---|
| Avtorji: | ID Dabrowski, Konrad K. (Avtor)
ID Lozin, Vadim V. (Avtor)
ID Milanič, Martin (Avtor)
ID Munaro, Andrea (Avtor)
ID Paulusma, Daniël (Avtor)
ID Zamaraev, Viktor (Avtor) |
|---|
| Datoteke: |  RAZ_Dabrowski_Konrad_K._2026.pdf (805,02 KB)
MD5: DDA83B67DF90D4EC1C1EDAC76A12BBE3
 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.14
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Neznano |
|---|
| Tipologija: | 1.08 - Objavljeni znanstveni prispevek na konferenci |
|---|
| Organizacija: | FAMNIT - Fakulteta za matematiko, naravoslovje in informacijske tehnologije
|
|---|
| Opis: | A graph class is monotone if it is closed under taking subgraphs. A monotone class defined by finitely many obstructions has bounded treewidth if and only if one of the obstructions is a tripod, i.e. a disjoint union of subdivided claws and paths. This dichotomy also characterizes exactly those monotone graph classes for which many NP-hard graph problems admit polynomial-time algorithms. These dichotomies do not extend to the universe of all hereditary classes. This leads to the question of whether we can extend known dichotomies for monotone classes to larger families of hereditary classes. We answer this question affirmatively by considering the family of hereditary graph classes closed under self-intersection. This family is known to be located strictly between the monotone and hereditary classes. We prove a new structural characterization of graphs in self-intersection-closed classes excluding a tripod. In contrast to monotone classes excluding a tripod, these classes do not necessarily have bounded treewidth; in fact, they do not even need to be sparse. We use our characterization to give a complete dichotomy for Maximum Independent Set, and its weighted variant, on self-intersection-closed classes defined by finitely many obstructions: these problems are in P if the class excludes a tripod and NP-hard otherwise. Our dichotomy generalizes several known results on Maximum Independent Set in the literature. We also apply our characterization to obtain a dichotomy for Maximum Induced Matching on self-intersection-closed classes of bipartite graphs defined by finitely many obstructions, and for Satisfiability and Counting Satisfiability on self-intersection-closed classes of (bipartite) incidence graphs defined by finitely many obstructions. Finally, we use our characterization to obtain a dichotomy for boundedness of clique-width for self-intersection-closed classes of bipartite graphs defined by finitely many obstructions. |
|---|
| Ključne besede: | graph classes, self-intersection closed, dichotomy, independent set, clique-width, treewidth |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 02.07.2026 |
|---|
| Leto izida: | 2026 |
|---|
| Št. strani: | Str. 14:1–14:15 |
|---|
| PID: | 20.500.12556/RUP-23314  |
|---|
| UDK: | 519.17 |
|---|
| ISSN pri članku: | 1868-8969 |
|---|
| DOI: | 10.4230/LIPIcs.WG.2026.14 |
|---|
| COBISS.SI-ID: | 284824579 |
|---|
| Datum objave v RUP: | 15.07.2026 |
|---|
| Število ogledov: | 23 |
|---|
| Število prenosov: | 2 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
