One, two, three, many, or: complexity aspects of dynamic network flows with dedicated arcs

B. Klinz, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    7 Citations (Scopus)

    Abstract

    A dynamic network consists of a directed graph with a source s, a sink t and capacities and integral transit times on the arcs. We investigate the computational complexity of dynamic network flow problems where sending flow along an arc blocks this arc as long as the transmission continues. Such arcs are called dedicated arcs. We are mainly interested in questions of the type "Given an integral time bound T and an integral flow value v, is it possible to transmit v flow units from the source s to the sink t within T time units?". The complexity of this question strongly depends on whether the values T and v are encoded in binary, in unary, or are constant. We provide a complete classification of all variants of this problem from the computational complexity point of view. Our results establish a sharp borderline between easy and difficult cases of this dynamic network flow problem. We prove that in the dedicated arc model it is NP-hard to find the maximum flow value v that can be transmitted within T=3 time units, whereas the maximum flow value v for T=2 can be computed in polynomial time. Moreover, we prove that it is NP-hard to find the minimum time T during which v=2 units of flow can be transmitted, whereas the corresponding question for v=1 can be answered in polynomial time. Finally, we prove that the variant where T is encoded in unary and where v is not part of the input can be solved in polynomial time.
    Original languageEnglish
    Pages (from-to)119-127
    Number of pages9
    JournalOperations Research Letters
    Volume22
    Issue number4-5
    DOIs
    Publication statusPublished - 1998

    Fingerprint Dive into the research topics of 'One, two, three, many, or: complexity aspects of dynamic network flows with dedicated arcs'. Together they form a unique fingerprint.

  • Cite this