On distance-d independent set and other problems in graphs with “few” minimal separators

Pedro Montealegre, Ioan Todinca

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

10 Scopus citations

Abstract

Fomin and Villanger ([14], STACS 2010) proved that MAXIMUM INDEPENDENT SET, FEEDBACK VERTEX SET, and more generally the problem of finding a maximum induced subgraph of treewith at most a constant t, can be solved in polynomial time on graph classes with polynomially many minimal separators. We extend these results in two directions. Let Gpoly be the class of graphs with at most poly(n) minimal separators, for some polynomial poly. We show that the odd powers of a graph G have at most as many minimal separators as G. Consequently, DISTANCE-d INDEPENDENT SET, which consists in finding maximum set of vertices at pairwise distance at least d, is polynomial on Gpoly, for any even d. The problem is NP-hard on chordal graphs for any odd d ≥ 3 [12]. We also provide polynomial algorithms for CONNECTED VERTEX COVER AND CONNECTED FEEDBACK VERTEX SET on subclasses of Gpoly including chordal and circular-arc graphs, and we discuss variants of independent domination problems.

Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science - 42nd International Workshop, WG 2016, Revised Selected Papers
EditorsPinar Heggernes
PublisherSpringer Verlag
Pages183-194
Number of pages12
ISBN (Print)9783662535356
DOIs
StatePublished - 2016
Event42nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2016 - Istanbul, Turkey
Duration: 22 Jun 201624 Jun 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9941 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference42nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2016
Country/TerritoryTurkey
CityIstanbul
Period22/06/1624/06/16

Fingerprint

Dive into the research topics of 'On distance-d independent set and other problems in graphs with “few” minimal separators'. Together they form a unique fingerprint.

Cite this