On edge-independent sets

Ton Kloks; Ching Hao Liu; Sheung Hung Poon

doi:10.1007/978-3-642-38756-2_28

On edge-independent sets

Ton Kloks, Ching Hao Liu, Sheung Hung Poon

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-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 language	English
Title of host publication	Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Third Joint International Conference, FAW-AAIM 2013, Proceedings
Pages	272-283
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-38756-2_28
Publication status	Published - 2013
Externally published	Yes
Event	7th 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 2013 → 28 Jun 2013

Publication series

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

Conference

Conference	7th International Frontiers in Algorithmics Workshop and the 9th International Conference on Algorithmic Aspects in Information and Management, FAW-AAIM 2013
Country/Territory	China
City	Dalian
Period	26/06/13 → 28/06/13

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-38756-2_28

Cite this

Kloks, T., Liu, C. H., & Poon, S. H. (2013). On edge-independent sets. In Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Third Joint International Conference, FAW-AAIM 2013, Proceedings (pp. 272-283). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7924 LNCS). https://doi.org/10.1007/978-3-642-38756-2_28

Kloks, Ton ; Liu, Ching Hao ; Poon, Sheung Hung. / On edge-independent sets. Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Third Joint International Conference, FAW-AAIM 2013, Proceedings. 2013. pp. 272-283 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0a105ff86d35420a86e3780f55a4d59b,

title = "On edge-independent sets",

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.",

author = "Ton Kloks and Liu, {Ching Hao} and Poon, {Sheung Hung}",

note = "Copyright: Copyright 2013 Elsevier B.V., All rights reserved.; 7th International Frontiers in Algorithmics Workshop and the 9th International Conference on Algorithmic Aspects in Information and Management, FAW-AAIM 2013 ; Conference date: 26-06-2013 Through 28-06-2013",

year = "2013",

doi = "10.1007/978-3-642-38756-2_28",

language = "English",

isbn = "9783642387555",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "272--283",

booktitle = "Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Third Joint International Conference, FAW-AAIM 2013, Proceedings",

}

Kloks, T, Liu, CH & Poon, SH 2013, On edge-independent sets. in Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Third Joint International Conference, FAW-AAIM 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7924 LNCS, pp. 272-283, 7th International Frontiers in Algorithmics Workshop and the 9th International Conference on Algorithmic Aspects in Information and Management, FAW-AAIM 2013, Dalian, China, 26/06/13. https://doi.org/10.1007/978-3-642-38756-2_28

On edge-independent sets. / Kloks, Ton; Liu, Ching Hao; Poon, Sheung Hung.
Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Third Joint International Conference, FAW-AAIM 2013, Proceedings. 2013. p. 272-283 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7924 LNCS).

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On edge-independent sets

AU - Kloks, Ton

AU - Liu, Ching Hao

AU - Poon, Sheung Hung

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84884844650&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-38756-2_28

DO - 10.1007/978-3-642-38756-2_28

M3 - Conference contribution

AN - SCOPUS:84884844650

SN - 9783642387555

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 272

EP - 283

BT - Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Third Joint International Conference, FAW-AAIM 2013, Proceedings

T2 - 7th International Frontiers in Algorithmics Workshop and the 9th International Conference on Algorithmic Aspects in Information and Management, FAW-AAIM 2013

Y2 - 26 June 2013 through 28 June 2013

ER -

Kloks T, Liu CH, Poon SH. On edge-independent sets. In Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Third Joint International Conference, FAW-AAIM 2013, Proceedings. 2013. p. 272-283. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-38756-2_28

On edge-independent sets

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this