The density maximization problem in graphs

Mong Jen Kao*, Bastian Katz, Marcus Krug, D. T. Lee, Ignaz Rutter, Dorothea Wagner

*Corresponding author for this work

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


We consider a framework for bi-objective network construction problems where one objective is to be maximized while the other is to be minimized. Given a host graph G = (V,E) with edge weights we ∈ ℤ and edge lengths ℓe ∈ ℕ for e ∈ E we define the density of a pattern subgraph H = (V′,E′) ⊆ G as the ρ(H) = ∑eεE′we/∑eεE′e ratio . We consider the problem of computing a maximum density pattern H with weight at least W and and length at most L in a host G. We consider this problem for different classes of hosts and patterns. We show that it is NP-hard even if the host has treewidth 2 and the pattern is a path. However, it can be solved in pseudo-polynomial linear time if the host has bounded treewidth and the pattern is a graph from a given minor-closed family of graphs. Finally, we present an FPTAS for a relaxation of the density maximization problem, in which we are allowed to violate the upper bound on the length at the cost of some penalty.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 17th Annual International Conference, COCOON 2011, Proceedings
Number of pages12
StatePublished - 2011
Event17th Annual International Computing and Combinatorics Conference, COCOON 2011 - Dallas, TX, United States
Duration: 14 Aug 201116 Aug 2011

Publication series

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


Conference17th Annual International Computing and Combinatorics Conference, COCOON 2011
Country/TerritoryUnited States
CityDallas, TX


Dive into the research topics of 'The density maximization problem in graphs'. Together they form a unique fingerprint.

Cite this