On edge-independent sets

Ton Kloks, Ching Hao Liu, Sheung Hung Poon

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

1 Citation (Scopus)

Abstract

A set of edges in a graph G is independent if no two elements are contained in a clique of G. The edge-independent set problem asks for the maximal cardinality of independent sets of edges. We show that the edge-clique graphs of cocktail parties have unbounded rankwidth. There is an elegant formula that solves the edge-independent set problem for graphs of rankwidth one, which are exactly distance-hereditary graphs, and related classes of graphs. We present a PTAS for the edge-independent set problem on planar graphs and show that the problem is polynomial for planar graphs without triangle separators. The set of edges of a bipartite graph is edge-independent. We show that the edge-independent set problem remains NP-complete for graphs in which every neighborhood is bipartite, i.e., the graphs without odd wheels.

Original languageEnglish
Title of host publicationFrontiers in Algorithmics and Algorithmic Aspects in Information and Management - Third Joint International Conference, FAW-AAIM 2013, Proceedings
Pages272-283
Number of pages12
DOIs
Publication statusPublished - 2013
Externally publishedYes
Event7th International Frontiers in Algorithmics Workshop and the 9th International Conference on Algorithmic Aspects in Information and Management, FAW-AAIM 2013 - Dalian, China
Duration: 26 Jun 201328 Jun 2013

Publication series

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

Conference

Conference7th International Frontiers in Algorithmics Workshop and the 9th International Conference on Algorithmic Aspects in Information and Management, FAW-AAIM 2013
Country/TerritoryChina
CityDalian
Period26/06/1328/06/13

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'On edge-independent sets'. Together they form a unique fingerprint.

Cite this