TY - GEN

T1 - The density maximization problem in graphs

AU - Kao, Mong Jen

AU - Katz, Bastian

AU - Krug, Marcus

AU - Lee, D. T.

AU - Rutter, Ignaz

AU - Wagner, Dorothea

N1 - Funding Information:
Supported by NSC-DFG Projects NSC98-2221-E-001-007-MY3 and WA 654/18.

PY - 2011

Y1 - 2011

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

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

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

U2 - 10.1007/978-3-642-22685-4_3

DO - 10.1007/978-3-642-22685-4_3

M3 - Conference contribution

AN - SCOPUS:80051960500

SN - 9783642226847

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

SP - 25

EP - 36

BT - Computing and Combinatorics - 17th Annual International Conference, COCOON 2011, Proceedings

T2 - 17th Annual International Computing and Combinatorics Conference, COCOON 2011

Y2 - 14 August 2011 through 16 August 2011

ER -