TY - JOUR

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. Also supported by the Institute of Information Science, Academia Sinica, Taiwan.

PY - 2013/11

Y1 - 2013/11

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 ratio Ï±(H)= Σ e* E′ w e /Σ e*E′ ℓ e . We consider the problem of computing a maximum density pattern H under various additional constraints. In doing so, we compute a single Pareto-optimal solution with the best weight per cost ratio subject to additional constraints further narrowing down feasible solutions for the underlying bi-objective network construction problem. First, we consider the problem of computing a maximum density pattern with weight at least W and length at most L in a host G. We call this problem the biconstrained density maximization problem. This problem can be interpreted in terms of maximizing the return on investment for network construction problems in the presence of a limited budget and a target profit. 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. Second, we consider the maximum density subgraph problem under structural constraints on the vertex set that is used by the patterns. While a maximum density perfect matching can be computed efficiently in general graphs, the maximum density Steiner-subgraph problem, which requires a subset of the vertices in any feasible solution, is NP-hard and unlikely to admit a constant-factor approximation. When parameterized by the number of vertices of the pattern, this problem is W[1]-hard in general graphs. On the other hand, it is FPT on planar graphs if there is no constraint on the pattern and on general graphs if the pattern is a path.

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 ratio Ï±(H)= Σ e* E′ w e /Σ e*E′ ℓ e . We consider the problem of computing a maximum density pattern H under various additional constraints. In doing so, we compute a single Pareto-optimal solution with the best weight per cost ratio subject to additional constraints further narrowing down feasible solutions for the underlying bi-objective network construction problem. First, we consider the problem of computing a maximum density pattern with weight at least W and length at most L in a host G. We call this problem the biconstrained density maximization problem. This problem can be interpreted in terms of maximizing the return on investment for network construction problems in the presence of a limited budget and a target profit. 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. Second, we consider the maximum density subgraph problem under structural constraints on the vertex set that is used by the patterns. While a maximum density perfect matching can be computed efficiently in general graphs, the maximum density Steiner-subgraph problem, which requires a subset of the vertices in any feasible solution, is NP-hard and unlikely to admit a constant-factor approximation. When parameterized by the number of vertices of the pattern, this problem is W[1]-hard in general graphs. On the other hand, it is FPT on planar graphs if there is no constraint on the pattern and on general graphs if the pattern is a path.

KW - Algorithm

KW - Complexity

KW - Multi-criteria optimization

KW - Subgraph

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

U2 - 10.1007/s10878-012-9465-z

DO - 10.1007/s10878-012-9465-z

M3 - Article

AN - SCOPUS:84886447280

VL - 26

SP - 723

EP - 754

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

SN - 1382-6905

IS - 4

ER -