Covering minimal separators and potential maximal cliques in P-t-free graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10438233" target="_blank" >RIV/00216208:11320/21:10438233 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=9R_k4NwTjC" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=9R_k4NwTjC</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.37236/9473" target="_blank" >10.37236/9473</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Covering minimal separators and potential maximal cliques in P-t-free graphs

Popis výsledku v původním jazyce

A graph is called P-t-free if it does not contain a t-vertex path as an induced subgraph. While P-4-free graphs are exactly cographs, the structure of P-t-free graphs for t &gt;= 5 remains not well-undestood. On one hand, classic computational problems such as MAXIMUM WEIGHT INDEPENDENT SET (MWIS) and 3-COLORING are not known to be NP-hard on P-t-free graphs for any fixed t. On the other hand, despite significant effort, polynomial-time algorithms for MWIS in P-6-free graphs [SODA 2019] and 3-COLORING in P-7-free graphs [Combinatorica 2018] have been found only recently. In both cases, the algorithms rely on deep structural insights into the considered graph classes. One of the main tools in the algorithms for MWIS in P-5-free graphs [SODA 2014] and in P-6-free graphs [SODA 2019] is the so-called Separator Covering Lemma that asserts that every minimal separator in the graph can be covered by the union of neighborhoods of a constant number of vertices. In this note we show that such a statement generalizes to P-7-free graphs and is false in P-8-free graphs. We also discuss analogues of such a statement for covering potential maximal cliques with unions of neighborhoods.

Název v anglickém jazyce

Covering minimal separators and potential maximal cliques in P-t-free graphs

Popis výsledku anglicky

A graph is called P-t-free if it does not contain a t-vertex path as an induced subgraph. While P-4-free graphs are exactly cographs, the structure of P-t-free graphs for t &gt;= 5 remains not well-undestood. On one hand, classic computational problems such as MAXIMUM WEIGHT INDEPENDENT SET (MWIS) and 3-COLORING are not known to be NP-hard on P-t-free graphs for any fixed t. On the other hand, despite significant effort, polynomial-time algorithms for MWIS in P-6-free graphs [SODA 2019] and 3-COLORING in P-7-free graphs [Combinatorica 2018] have been found only recently. In both cases, the algorithms rely on deep structural insights into the considered graph classes. One of the main tools in the algorithms for MWIS in P-5-free graphs [SODA 2014] and in P-6-free graphs [SODA 2019] is the so-called Separator Covering Lemma that asserts that every minimal separator in the graph can be covered by the union of neighborhoods of a constant number of vertices. In this note we show that such a statement generalizes to P-7-free graphs and is false in P-8-free graphs. We also discuss analogues of such a statement for covering potential maximal cliques with unions of neighborhoods.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GJ19-04113Y" target="_blank" >GJ19-04113Y: Pokročilé nástroje v kombinatorice, topologii a příbuzných oblastech</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2021

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Electronic Journal of Combinatorics

ISSN

1077-8926

e-ISSN

—

Svazek periodika

28

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

14

Strana od-do

P1.29

Kód UT WoS článku

000619757400001

EID výsledku v databázi Scopus

2-s2.0-85100546480