The minimum vulnerability problem on specific graph classes

Yusuke Aoki (), Bjarni V. Halldórsson (), Magnús M. Halldórsson (), Takehiro Ito (), Christian Konrad () and Xiao Zhou ()
Additional contact information
Yusuke Aoki: Tohoku University
Bjarni V. Halldórsson: Reykjavík University
Magnús M. Halldórsson: Reykjavík University
Takehiro Ito: Tohoku University
Christian Konrad: Reykjavík University
Xiao Zhou: Tohoku University

Journal of Combinatorial Optimization, 2016, vol. 32, issue 4, No 18, 1288-1304

Abstract: Abstract Suppose that each edge e of an undirected graph G is associated with three nonnegative integers $$\mathsf{cost}(e)$$ cost ( e ) , $$\mathsf{vul}(e)$$ vul ( e ) and $$\mathsf{cap}(e)$$ cap ( e ) , called the cost, vulnerability and capacity of e, respectively. Then, we consider the problem of finding $$k$$ k paths in G between two prescribed vertices with the minimum total cost; each edge e can be shared without any cost by at most $$\mathsf{vul}(e)$$ vul ( e ) paths, and can be shared by more than $$\mathsf{vul}(e)$$ vul ( e ) paths if we pay $$\mathsf{cost}(e)$$ cost ( e ) , but cannot be shared by more than $$\mathsf{cap}(e)$$ cap ( e ) paths even if we pay the cost for e. This problem generalizes the disjoint path problem, the minimum shared edges problem and the minimum edge cost flow problem for undirected graphs, and it is known to be NP-hard. In this paper, we study the problem from the viewpoint of specific graph classes, and give three results. We first show that the problem is NP-hard even for bipartite outerplanar graphs, 2-trees, graphs with pathwidth two, complete bipartite graphs, and complete graphs. We then give a pseudo-polynomial-time algorithm for bounded treewidth graphs. Finally, we give a fixed-parameter algorithm for chordal graphs when parameterized by the number $$k$$ k of required paths.

Keywords: Bounded treewidth graph; Chordal graph; Fixed parameter tractability; Graph algorithm; Minimum vulnerability problem (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9950-2 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:32:y:2016:i:4:d:10.1007_s10878-015-9950-2

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

DOI: 10.1007/s10878-015-9950-2

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 ().