Document Open Access Logo

Parameterized Inapproximability for Steiner Orientation by Gap Amplification

Author Michał Włodarczyk

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.104.pdf
  • Filesize: 0.78 MB
  • 19 pages

Document Identifiers

Author Details

Michał Włodarczyk
  • Eindhoven University of Technology, The Netherlands

Funding

The main part of the work has been done when the author was a Ph.D. student at the University of Warsaw and it was a part of the project TOTAL, that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 677651). The author was also supported by the Foundation for Polish Science (FNP).

Cite AsGet BibTex

Michał Włodarczyk. Parameterized Inapproximability for Steiner Orientation by Gap Amplification. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 104:1-104:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.104

Abstract

In the k-Steiner Orientation problem, we are given a mixed graph, that is, with both directed and undirected edges, and a set of k terminal pairs. The goal is to find an orientation of the undirected edges that maximizes the number of terminal pairs for which there is a path from the source to the sink. The problem is known to be W[1]-hard when parameterized by k and hard to approximate up to some constant for FPT algorithms assuming Gap-ETH. On the other hand, no approximation factor better than 𝒪(k) is known. We show that k-Steiner Orientation is unlikely to admit an approximation algorithm with any constant factor, even within FPT running time. To obtain this result, we construct a self-reduction via a hashing-based gap amplification technique, which turns out useful even outside of the FPT paradigm. Precisely, we rule out any approximation factor of the form (log k)^o(1) for FPT algorithms (assuming FPT ≠ W[1]) and (log n)^o(1) for purely polynomial-time algorithms (assuming that the class W[1] does not admit randomized FPT algorithms). This constitutes a novel inapproximability result for polynomial-time algorithms obtained via tools from the FPT theory. Moreover, we prove k-Steiner Orientation to belong to W[1], which entails W[1]-completeness of (log k)^o(1)-approximation for k-Steiner Orientation. This provides an example of a natural approximation task that is complete in a parameterized complexity class. Finally, we apply our technique to the maximization version of directed multicut - Max (k,p)-Directed Multicut - where we are given a directed graph, k terminals pairs, and a budget p. The goal is to maximize the number of separated terminal pairs by removing p edges. We present a simple proof that the problem admits no FPT approximation with factor 𝒪(k^(1/2 - ε)) (assuming FPT ≠ W[1]) and no polynomial-time approximation with ratio 𝒪(|E(G)|^(1/2 - ε)) (assuming NP ⊈ co-RP).

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
Keywords
  • approximation algorithms
  • fixed-parameter tractability
  • hardness of approximation
  • gap amplification

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Marek Adamczyk, Jaroslaw Byrka, Jan Marcinkowski, Syed M. Meesum, and Michal Wlodarczyk. Constant-Factor FPT Approximation for Capacitated k-Median. In 27th Annual European Symposium on Algorithms (ESA 2019), volume 144 of Leibniz International Proceedings in Informatics (LIPIcs), pages 1:1-1:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.1.
  2. Amit Agarwal, Noga Alon, and Moses S. Charikar. Improved approximation for directed cut problems. In Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing, STOC '07, pages 671-680, New York, NY, USA, 2007. ACM. URL: https://doi.org/10.1145/1250790.1250888.
  3. Esther M. Arkin and Refael Hassin. A note on orientations of mixed graphs. Discrete Applied Mathematics, 116(3):271-278, 2002. URL: https://doi.org/10.1016/S0166-218X(01)00228-1.
  4. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3):501–555, May 1998. URL: https://doi.org/10.1145/278298.278306.
  5. Nikhil Bansal and Subhash Khot. Optimal long code test with one free bit. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 453-462. IEEE, 2009. Google Scholar
  6. Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., and Pasin Manurangsi. Parameterized intractability of Even Set and Shortest Vector Problem from Gap-ETH. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 17:1-17:15, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.17.
  7. Nicolas Bousquet, Jean Daligault, and Stéphan Thomassé. Multicut is FPT. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC '11, pages 459-468, New York, NY, USA, 2011. ACM. URL: https://doi.org/10.1145/1993636.1993698.
  8. J.Lawrence Carter and Mark N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18(2):143-154, 1979. URL: https://doi.org/10.1016/0022-0000(79)90044-8.
  9. Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, and Luca Trevisan. From Gap-ETH to FPT-inapproximability: Clique, Dominating Set, and more. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 743-754, October 2017. URL: https://doi.org/10.1109/FOCS.2017.74.
  10. Rajesh Chitnis, Andreas Emil Feldmann, and Pasin Manurangsi. Parameterized approximation algorithms for bidirected steiner network problems. In 26th Annual European Symposium on Algorithms (ESA 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  11. Rajesh Chitnis, Andreas Emil Feldmann, and Ondřej Suchý. A tight lower bound for Planar Steiner Orientation. Algorithmica, May 2019. URL: https://doi.org/10.1007/s00453-019-00580-x.
  12. Julia Chuzhoy and Sanjeev Khanna. Polynomial flow-cut gaps and hardness of directed cut problems. J. ACM, 56(2):6:1-6:28, April 2009. URL: https://doi.org/10.1145/1502793.1502795.
  13. Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li. Tight FPT Approximations for k-Median and k-Means. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 42:1-42:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.42.
  14. Vincent Cohen-Addad and Jason Li. On the Fixed-Parameter Tractability of Capacitated Clustering. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 41:1-41:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.41.
  15. Marek Cygan, Guy Kortsarz, and Zeev Nutov. Steiner forest orientation problems. SIAM Journal on Discrete Mathematics, 27(3):1503-1513, 2013. URL: https://doi.org/10.1137/120883931.
  16. Irit Dinur. The PCP theorem by gap amplification. J. ACM, 54(3), June 2007. URL: https://doi.org/10.1145/1236457.1236459.
  17. Irit Dinur. Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. Electronic Colloquium on Computational Complexity (ECCC), 23:128, 2016. Google Scholar
  18. Britta Dorn, Falk Hüffner, Dominikus Krüger, Rolf Niedermeier, and Johannes Uhlmann. Exploiting bounded signal flow for graph orientation based on cause-effect pairs. In Theory and Practice of Algorithms in (Computer) Systems, pages 104-115, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. Google Scholar
  19. Guillaume Fertin, Hafedh Mohamed-Babou, and Irena Rusu. On the Complexity of two Problems on Orientations of Mixed Graphs. In In Proc. 5èmes Journées Ouvertes Biologie Informatique Mathématiques (JOBIM 2012), pages 161-170, Rennes, France, July 2012. URL: https://hal.archives-ouvertes.fr/hal-00826863.
  20. Iftah Gamzu, Danny Segev, and Roded Sharan. Improved orientations of physical networks. In Algorithms in Bioinformatics, pages 215-225, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. Google Scholar
  21. David Gillman. A Chernoff bound for random walks on expander graphs. SIAM J. Comput., 27:1203-1220, 1998. Google Scholar
  22. Anupam Gupta, Euiwoong Lee, and Jason Li. Faster exact and approximate algorithms for k-Cut. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 113-123, 2018. URL: https://doi.org/10.1109/FOCS.2018.00020.
  23. Venkatesan Guruswami, Rajsekar Manokaran, and Prasad Raghavendra. Beating the random ordering is hard: Inapproximability of maximum acyclic subgraph. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 573-582. IEEE, 2008. Google Scholar
  24. Rafael Hassin and Nimrod Megiddo. On orientations and shortest paths. Linear Algebra and its Applications, 114-115:589-602, 1989. URL: https://doi.org/10.1016/0024-3795(89)90481-3.
  25. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. URL: https://doi.org/10.1006/jcss.2001.1774.
  26. Karthik C. S., Bundit Laekhanukit, and Pasin Manurangsi. On the parameterized complexity of approximating Dominating Set. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 1283-1296, 2018. URL: https://doi.org/10.1145/3188745.3188896.
  27. Ken-ichi Kawarabayashi and Bingkai Lin. A nearly 5/3-approximation FPT algorithm for Min-k-Cut. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, pages 990-999, 2020. URL: https://doi.org/10.1137/1.9781611975994.59.
  28. Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing, STOC '02, pages 767-775, New York, NY, USA, 2002. ACM. URL: https://doi.org/10.1145/509907.510017.
  29. Bingkai Lin. The parameterized complexity of k-Biclique. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 605-615, 2015. URL: https://doi.org/10.1137/1.9781611973730.41.
  30. Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, and Meirav Zehavi. Parameterized complexity and approximability of directed odd cycle transversal. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 2181-2200, 2020. URL: https://doi.org/10.1137/1.9781611975994.134.
  31. Rajsekar Manokaran, Joseph Naor, Prasad Raghavendra, and Roy Schwartz. SDP gaps and UGC hardness for multiway cut, 0-extension, and metric labeling. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 11-20, 2008. Google Scholar
  32. Pasin Manurangsi. Almost-polynomial ratio ETH-hardness of approximating Densest k-Subgraph. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 954-961, New York, NY, USA, 2017. ACM. URL: https://doi.org/10.1145/3055399.3055412.
  33. Pasin Manurangsi. Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), pages 79:1-79:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.79.
  34. Pasin Manurangsi and Prasad Raghavendra. A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), pages 78:1-78:15, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.78.
  35. Daniel Marx. Completely inapproximable monotone and antimonotone parameterized problems. In 2010 IEEE 25th Annual Conference on Computational Complexity, pages 181-187, June 2010. URL: https://doi.org/10.1109/CCC.2010.25.
  36. Alexander Medvedovsky, Vineet Bafna, Uri Zwick, and Roded Sharan. An algorithm for orienting graphs based on cause-effect pairs and its applications to orienting protein networks. In Algorithms in Bioinformatics, pages 222-232, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. Google Scholar
  37. Joseph Naor and Moni Naor. Small-bias probability spaces: Efficient constructions and applications. SIAM Journal on Computing, 22, March 2001. URL: https://doi.org/10.1145/100216.100244.
  38. Marcin Pilipczuk and Magnus Wahlström. Directed Multicut is W[1]-hard, even for four terminal pairs. ACM Trans. Comput. Theory, 10(3):13:1-13:18, May 2018. URL: https://doi.org/10.1145/3201775.
  39. Alan. Siegel. On universal classes of extremely random constant-time hash functions. SIAM Journal on Computing, 33(3):505-543, 2004. URL: https://doi.org/10.1137/S0097539701386216.
  40. Umesh Virkumar Vazirani. Randomness, Adversaries and Computation (Random Polynomial Time). PhD thesis, University of California, Berkeley, 1986. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact