The checkpoint problem

Mohammadtaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz, Julián Mestre

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

In this paper, we consider the checkpoint problem. The input consists of an undirected graph G, a set of source-destination pairs ( s1, t1),( s2, t2),...,( sk, tk), and a collection P of paths connecting the ( si, ti) pairs. A feasible solution is a multicut E′, namely, a set of edges whose removal disconnects every source-destination pair. For each p∈P we define cp E′(p)=|p∩ E′|. In the sum checkpoint (SCP) problem the goal is to minimize ∑ p∈Pcp E′(p), while in the maximum checkpoint (MCP) problem the goal is to minimize max p∈Pcp E′(p). These problems have several natural applications, e.g., in urban transportation and network security. In a sense, they combine the multicut problem and the minimum membership set cover problem. For the sum objective we show that weighted SCP is equivalent, with respect to approximability, to undirected multicut. Thus there exists an O(logn) approximation for SCP in general graphs. Our current approximability results for the max objective have a wide gap: we provide an approximation factor of O(nlognopt) for MCP and a hardness of 2 under the assumption P≠NP. The hardness holds for trees. This solves an open problem of Nelson (2009) [25]. We complement the lower bound by an almost matching upper bound with an asymptotic approximation factor of 2. On trees with all si, ti having an ancestor-descendant relation, we give a combinatorial exact algorithm. Besides the algorithm being combinatorial, its running time improves by many orders of magnitude the LP algorithm that follows from total unimodularity. Finally, we show strong hardness for the well-known problem of finding a path with minimum forbidden pairs, which in a sense can be considered the dual to the checkpoint problem. Despite various works on this problem, hardness of approximation was not known prior to this work. We show that the problem cannot be approximated within cn for some constant c>0, unless P=NP. This is the strongest type of hardness possible. It carries over to directed acyclic graphs and is a huge improvement over the plain NP-hardness of Gabow [H.N. Gabow, Finding paths and cycles of superpolylogarithmic length, SIAM J. Comput. 36 (6) (2007) 1648-1671].

Original languageEnglish (US)
Pages (from-to)88-99
Number of pages12
JournalTheoretical Computer Science
Volume452
DOIs
StatePublished - Sep 21 2012

Fingerprint

Checkpoint
Hardness
Multicut
Combinatorial Algorithms
Approximability
Urban transportation
Network security
Path
Hardness of Approximation
Minimise
Set Cover
NP-hardness
Network Security
Directed Acyclic Graph
Asymptotic Approximation
Exact Algorithms
Approximation
Weighted Sums
Undirected Graph
Open Problems

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Algorithms
  • Approximation
  • Checkpoint
  • Cuts

Cite this

Hajiaghayi, Mohammadtaghi ; Khandekar, Rohit ; Kortsarz, Guy ; Mestre, Julián. / The checkpoint problem. In: Theoretical Computer Science. 2012 ; Vol. 452. pp. 88-99.
@article{7ef57d566c7f4aaeb94ac5fd2d6cd212,
title = "The checkpoint problem",
abstract = "In this paper, we consider the checkpoint problem. The input consists of an undirected graph G, a set of source-destination pairs ( s1, t1),( s2, t2),...,( sk, tk), and a collection P of paths connecting the ( si, ti) pairs. A feasible solution is a multicut E′, namely, a set of edges whose removal disconnects every source-destination pair. For each p∈P we define cp E′(p)=|p∩ E′|. In the sum checkpoint (SCP) problem the goal is to minimize ∑ p∈Pcp E′(p), while in the maximum checkpoint (MCP) problem the goal is to minimize max p∈Pcp E′(p). These problems have several natural applications, e.g., in urban transportation and network security. In a sense, they combine the multicut problem and the minimum membership set cover problem. For the sum objective we show that weighted SCP is equivalent, with respect to approximability, to undirected multicut. Thus there exists an O(logn) approximation for SCP in general graphs. Our current approximability results for the max objective have a wide gap: we provide an approximation factor of O(nlognopt) for MCP and a hardness of 2 under the assumption P≠NP. The hardness holds for trees. This solves an open problem of Nelson (2009) [25]. We complement the lower bound by an almost matching upper bound with an asymptotic approximation factor of 2. On trees with all si, ti having an ancestor-descendant relation, we give a combinatorial exact algorithm. Besides the algorithm being combinatorial, its running time improves by many orders of magnitude the LP algorithm that follows from total unimodularity. Finally, we show strong hardness for the well-known problem of finding a path with minimum forbidden pairs, which in a sense can be considered the dual to the checkpoint problem. Despite various works on this problem, hardness of approximation was not known prior to this work. We show that the problem cannot be approximated within cn for some constant c>0, unless P=NP. This is the strongest type of hardness possible. It carries over to directed acyclic graphs and is a huge improvement over the plain NP-hardness of Gabow [H.N. Gabow, Finding paths and cycles of superpolylogarithmic length, SIAM J. Comput. 36 (6) (2007) 1648-1671].",
keywords = "Algorithms, Approximation, Checkpoint, Cuts",
author = "Mohammadtaghi Hajiaghayi and Rohit Khandekar and Guy Kortsarz and Juli{\'a}n Mestre",
year = "2012",
month = "9",
day = "21",
doi = "10.1016/j.tcs.2012.05.021",
language = "English (US)",
volume = "452",
pages = "88--99",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

Hajiaghayi, M, Khandekar, R, Kortsarz, G & Mestre, J 2012, 'The checkpoint problem', Theoretical Computer Science, vol. 452, pp. 88-99. https://doi.org/10.1016/j.tcs.2012.05.021

The checkpoint problem. / Hajiaghayi, Mohammadtaghi; Khandekar, Rohit; Kortsarz, Guy; Mestre, Julián.

In: Theoretical Computer Science, Vol. 452, 21.09.2012, p. 88-99.

Research output: Contribution to journalArticle

TY - JOUR

T1 - The checkpoint problem

AU - Hajiaghayi, Mohammadtaghi

AU - Khandekar, Rohit

AU - Kortsarz, Guy

AU - Mestre, Julián

PY - 2012/9/21

Y1 - 2012/9/21

N2 - In this paper, we consider the checkpoint problem. The input consists of an undirected graph G, a set of source-destination pairs ( s1, t1),( s2, t2),...,( sk, tk), and a collection P of paths connecting the ( si, ti) pairs. A feasible solution is a multicut E′, namely, a set of edges whose removal disconnects every source-destination pair. For each p∈P we define cp E′(p)=|p∩ E′|. In the sum checkpoint (SCP) problem the goal is to minimize ∑ p∈Pcp E′(p), while in the maximum checkpoint (MCP) problem the goal is to minimize max p∈Pcp E′(p). These problems have several natural applications, e.g., in urban transportation and network security. In a sense, they combine the multicut problem and the minimum membership set cover problem. For the sum objective we show that weighted SCP is equivalent, with respect to approximability, to undirected multicut. Thus there exists an O(logn) approximation for SCP in general graphs. Our current approximability results for the max objective have a wide gap: we provide an approximation factor of O(nlognopt) for MCP and a hardness of 2 under the assumption P≠NP. The hardness holds for trees. This solves an open problem of Nelson (2009) [25]. We complement the lower bound by an almost matching upper bound with an asymptotic approximation factor of 2. On trees with all si, ti having an ancestor-descendant relation, we give a combinatorial exact algorithm. Besides the algorithm being combinatorial, its running time improves by many orders of magnitude the LP algorithm that follows from total unimodularity. Finally, we show strong hardness for the well-known problem of finding a path with minimum forbidden pairs, which in a sense can be considered the dual to the checkpoint problem. Despite various works on this problem, hardness of approximation was not known prior to this work. We show that the problem cannot be approximated within cn for some constant c>0, unless P=NP. This is the strongest type of hardness possible. It carries over to directed acyclic graphs and is a huge improvement over the plain NP-hardness of Gabow [H.N. Gabow, Finding paths and cycles of superpolylogarithmic length, SIAM J. Comput. 36 (6) (2007) 1648-1671].

AB - In this paper, we consider the checkpoint problem. The input consists of an undirected graph G, a set of source-destination pairs ( s1, t1),( s2, t2),...,( sk, tk), and a collection P of paths connecting the ( si, ti) pairs. A feasible solution is a multicut E′, namely, a set of edges whose removal disconnects every source-destination pair. For each p∈P we define cp E′(p)=|p∩ E′|. In the sum checkpoint (SCP) problem the goal is to minimize ∑ p∈Pcp E′(p), while in the maximum checkpoint (MCP) problem the goal is to minimize max p∈Pcp E′(p). These problems have several natural applications, e.g., in urban transportation and network security. In a sense, they combine the multicut problem and the minimum membership set cover problem. For the sum objective we show that weighted SCP is equivalent, with respect to approximability, to undirected multicut. Thus there exists an O(logn) approximation for SCP in general graphs. Our current approximability results for the max objective have a wide gap: we provide an approximation factor of O(nlognopt) for MCP and a hardness of 2 under the assumption P≠NP. The hardness holds for trees. This solves an open problem of Nelson (2009) [25]. We complement the lower bound by an almost matching upper bound with an asymptotic approximation factor of 2. On trees with all si, ti having an ancestor-descendant relation, we give a combinatorial exact algorithm. Besides the algorithm being combinatorial, its running time improves by many orders of magnitude the LP algorithm that follows from total unimodularity. Finally, we show strong hardness for the well-known problem of finding a path with minimum forbidden pairs, which in a sense can be considered the dual to the checkpoint problem. Despite various works on this problem, hardness of approximation was not known prior to this work. We show that the problem cannot be approximated within cn for some constant c>0, unless P=NP. This is the strongest type of hardness possible. It carries over to directed acyclic graphs and is a huge improvement over the plain NP-hardness of Gabow [H.N. Gabow, Finding paths and cycles of superpolylogarithmic length, SIAM J. Comput. 36 (6) (2007) 1648-1671].

KW - Algorithms

KW - Approximation

KW - Checkpoint

KW - Cuts

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

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

U2 - 10.1016/j.tcs.2012.05.021

DO - 10.1016/j.tcs.2012.05.021

M3 - Article

AN - SCOPUS:84864288949

VL - 452

SP - 88

EP - 99

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -