×

zbMATH — the first resource for mathematics

Hardness of vertex deletion and project scheduling. (English) Zbl 1366.68083
Summary: Assuming the Unique Games Conjecture, we show strong inapproximability results for two natural vertex deletion problems on directed graphs: for any integer \(k\geq 2\) and arbitrary small \(\epsilon > 0\), the Feedback Vertex Set problem and the DAG Vertex Deletion problem are inapproximable within a factor \(k-\epsilon\) even on graphs where the vertices can be almost partitioned into \(k\) solutions. This gives a more structured and yet simpler (albeit using the “It Ain’t Over Till It’s Over” theorem) UG-hardness result for the Feedback Vertex Set problem than the previous hardness result. {
} In comparison to the classical Feedback Vertex Set problem, the DAG Vertex Deletion problem has received little attention and, although we think it is a natural and interesting problem, the main motivation for our inapproximability result stems from its relationship with the classical Discrete Time-Cost Tradeoff Problem. More specifically, our results imply that the deadline version is UG-hard to approximate within any constant. This explains the difficulty in obtaining good approximation algorithms for that problem and further motivates previous alternative approaches such as bicriteria approximations.

MSC:
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68R10 Graph theory (including graph drawing) in computer science
68W25 Approximation algorithms
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] [1] NIKHILBANSAL ANDSUBHASHKHOT: Optimal long code test with one free bit. In Proc. 50th FOCS, pp. 453–462. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.23]761,763,769, 773,777
[2] [2] NIKHILBANSAL ANDSUBHASHKHOT: Inapproximability of hypergraph vertex cover and applications to scheduling problems. In Proc. 37th Internat. Colloq. on Automata, Languages and Programming (ICALP’10), pp. 250–261. Springer, 2010. [doi:10.1007/978-3-642-14165-2_22]761
[3] [3] PRABUDDHADE, E. JAMESDUNNE, JAYB. GHOSH,ANDCHARLESE. WELLS: The discrete time-cost tradeoff problem revisited. European Journal of Operational Research, 81(2):225–238, 1995. [doi:10.1016/0377-2217(94)00187-H]760
[4] [4] IRITDINUR ANDSHMUELSAFRA: On the hardness of approximating minimum vertex cover. Ann. of Math., 162(1):439–485, 2005. Preliminary version inSTOC’02. See also atECCC. [doi:10.4007/annals.2005.162.439]761
[5] [5] GUYEVEN, JOSEPHNAOR, BARUCHSCHIEBER,ANDMADHUSUDAN: Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica, 20(2):151–174, 1998. Preliminary version inIPCO’95. [doi:10.1007/PL00009191]760,761
[6] [6] DELBERTR. FULKERSON: A network flow computation for project cost curves. Management Science, 7(2):167–178, 1961. [doi:10.1287/mnsc.7.2.167]760 · Zbl 0995.90519
[7] [7] ALEXANDERGRIGORIEV ANDGERHARDJ. WOEGINGER: Project scheduling with irregular costs: complexity, approximability, and algorithms. Acta Inf., 41(2-3):83–97, 2004. Preliminary version inISAAC’02. [doi:10.1007/s00236-004-0150-2]760,761
[8] [8] VENKATESANGURUSWAMI, JOHANHÅSTAD, RAJSEKARMANOKARAN, PRASADRAGHAVENDRA,ANDMOSESCHARIKAR: Beating the random ordering is hard: Every ordering CSP is approximation resistant. SIAM J. Comput., 40(3):878–914, 2011. Preliminary versions inFOCS’08 and inCCC’09. See also atECCC. [doi:10.1137/090756144]761
[9] [9] RICHARDM. KARP: Reducibility among combinatorial problems. In R. E. MILLER AND J. W. THATCHER, editors, Complexity of Computer Computations, pp. 85–103. Springer, 1972. [doi:10.1007/978-1-4684-2001-2_9]760 THEORY OFCOMPUTING, Volume 9 (24), 2013, pp. 759–781779 OLASVENSSON
[10] [10] JAMESE. KELLEY, JR.: Critical-path planning and scheduling: Mathematical basis. Operations Research, 9(3):296–320, 1961. [doi:10.1287/opre.9.3.296]760 · Zbl 0098.12103
[11] [11] JAMESE. KELLEY, JR.ANDMORGANR. WALKER: Critical-path planning and scheduling. In Papers presented at the December 1-3, 1959, eastern joint IRE-AIEE-ACM computer conference, pp. 160–173. ACM Press, 1959. [doi:10.1145/1460299.1460318]760
[12] [12] SUBHASHKHOT: On the power of unique 2-prover 1-round games. In Proc. 34th STOC, pp. 767–775. ACM Press, 2002. [doi:10.1145/509907.510017]761,764
[13] [13] FRANKTHOMSONLEIGHTON ANDSATISHRAO: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM, 46(6):787–832, 1999. Preliminary version inFOCS’88. [doi:10.1145/331524.331526]760
[14] [14] ELCHANANMOSSEL, RYANO’DONNELL,ANDKRZYSZTOFOLESZKIEWICZ: Noise stability of functions with low influences: Invariance and optimality. Ann. of Math., 171(1):295–341, 2010. Preliminary version inFOCS’05. [doi:10.4007/annals.2010.171.295]762,763,769
[15] [15] DOOWONPAIK, SUDHAKARM. REDDY,ANDSARTAJSAHNI: Deleting vertices to bound path length. IEEE Trans. Computers, 43(9):1091–1096, 1994. [doi:10.1109/12.312117]760 · Zbl 1061.68541
[16] [16] PRASADRAGHAVENDRA: Optimal algorithms and inapproximability results for every CSP? In Proc. 40th STOC, pp. 245–254. ACM Press, 2008. [doi:10.1145/1374376.1374414]761
[17] [17] PAULD. SEYMOUR: Packing directed circuits fractionally. Combinatorica, 15(2):281–288, 1995. [doi:10.1007/BF01200760]760
[18] [18] MARTINSKUTELLA: Approximation algorithms for the discrete time-cost tradeoff problem. Math. Oper. Res., 23(4):909–929, 1998. Preliminary version inSODA’97. [doi:10.1287/moor.23.4.909] 760,762
[19] [19] OLASVENSSON: Hardness of vertex deletion and project scheduling. In Proc. 15th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’12), pp. 301–312. Springer, 2012. [doi:10.1007/978-3-642-32512-0_26]759 AUTHOR Ola Svensson assistant professor École Polytechnique Fédérale de Lausanne ola.svenssonepfl ch http://theory.epfl.ch/osven THEORY OFCOMPUTING, Volume 9 (24), 2013, pp. 759–781780 HARDNESS OFVERTEXDELETION ANDPROJECTSCHEDULING ABOUT THE AUTHOR OLASVENSSON(not to be confused with the singerOla Svensson) graduated fromIDSIA in 2009; his advisor wasMonaldo Mastrolilli. The subject of his thesis was the approximability of graph and scheduling problems. After spending two years as a postdoc withJohan HåstadatKTH Royal Institute of Technology, Sweden, he is now back in Switzerland as an assistant professor in thetheory groupatEPFL. Apart from doing research, he enjoys the Alps that are in complete contrast to the flat but still beautiful landscape in South Sweden where he grew up. THEORY OFCOMPUTING, Volume 9 (24), 2013, pp. 759–781781
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.