The density maximization problem in graphs

Mong-Jen Kao (), Bastian Katz (), Marcus Krug (), D. T. Lee (), Ignaz Rutter () and Dorothea Wagner ()
Additional contact information
Mong-Jen Kao: National Taiwan University
Bastian Katz: Karlsruhe Institute of Technology (KIT)
Marcus Krug: Karlsruhe Institute of Technology (KIT)
D. T. Lee: National Taiwan University
Ignaz Rutter: Karlsruhe Institute of Technology (KIT)
Dorothea Wagner: Karlsruhe Institute of Technology (KIT)

Journal of Combinatorial Optimization, 2013, vol. 26, issue 4, No 7, 723-754

Abstract: Abstract 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 w e ∈ℤ 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.

Keywords: Subgraph; Multi-criteria optimization; Complexity; Algorithm (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-012-9465-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:26:y:2013:i:4:d:10.1007_s10878-012-9465-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-012-9465-z

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().