Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On the Approximability of the Minimum Rainbow Subgraph Problem and Other Related Problems

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

In this paper, we study the approximability of the minimum rainbow subgraph (MRS) problem and other related problems. The input to the problem is an n-vertex undirected graph, with each edge colored with one of p colors. The goal is to find a subgraph on a minimum number of vertices which has one induced edge of each color. The problem is known to be NP-hard, and has an upper bound of \(O(\sqrt{n})\) and a lower bound of \(\Omega (\log n)\) on its approximation ratio. We define a new problem called the densest colored k-subgraph problem, which has the same input as the MRS problem along with a parameter k. The goal is to output a subgraph on k vertices, which has the maximum number of edges of distinct colors. We give an \(O(n^{1/3})\)-approximation algorithm for it, and then, using that algorithm, give an \(O(n^{1/3}\log n)\)-approximation algorithm for the MRS problem. We observe that the Min-Rep problem (the minimization variant of the famous Label Cover problem) is indeed a special case of the MRS problem. This also implies a combinatorial \(O(n^{1/3}\log n)\)-approximation algorithm for the Min-Rep problem. Previously, Charikar et al. (Algorithmica 61(1):190–206, 2011) showed an ingenious LP-rounding based algorithm with an approximation ratio of \(O(n^{1/3}\log ^{2/3}n)\) for Min-Rep. It is quasi-NP-hard to approximate the Min-Rep problem to within a factor of \(2^{\log ^{1-\epsilon }n}\) (Kortsarz in Algorithmica 30(3): 432–450, 2001). The same hardness result now applies to the MRS problem. We also give approximation preserving reductions between various problems related to the MRS problem for which the best known approximation ratio is \(O(n^c)\) where n is the size of the input and c is a fixed constant less than one.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aazami, A., Stilp, K.: Approximation algorithms and hardness for domination with propagation. SIAM J. Discret. Math. 23(3), 1382–1399 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  2. Alon, N., Jiang, T., Miller, Z., Pritikin, D.: Properly colored subgraphs and rainbow subgraphs in edge-colorings with local constraints. Random Struct. Algorithms 23(4), 409–433 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., Vijayaraghavan, A.: Detecting high log-densities: an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph. In: Proceedings of the Forty-second ACM Symposium on Theory of Computing, STOC ’10, pp. 201–210. ACM (2010)

  4. Bhaskara, A., Charikar, M., Vijayaraghavan, A., Guruswami, V., Zhou, Y.: Polynomial integrality gaps for strong SDP relaxations of densest \(k\)-subgraph. In: Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’12, pp. 388–405. SIAM (2012)

  5. Camacho, S.M., Schiermeyer, I., Tuza, Z.: Approximation algorithms for the minimum rainbow subgraph problem. Discret. Math. 310(20), 2666–2670 (2010). Graph Theory—Dedicated to Carsten Thomassen on his 60th Birthday

    Article  MathSciNet  MATH  Google Scholar 

  6. Carr, R.D., Doddi, S., Konjevod, G., Marathe, M.: On the red-blue set cover problem. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’00, pp. 345–353. SIAM (2000)

  7. Charikar, M., Hajiaghayi, M.T., Karloff, H.: Improved approximation algorithms for label cover problems. Algorithmica 61(1), 190–206 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  8. Chen, N.: On the approximability of influence in social networks. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’08, pp. 1029–1037. SIAM (2008)

  9. Dawar, A., Grohe, M., Kreutzer, S., Schweikardt, N.: Approximation schemes for first-order definable optimization problems. In: Proceedings of the Twenty-first Annual IEEE Symposium on Logic in Computer Science (LICS 2006), pp. 411–420. IEEE Computer Society Press (2006)

  10. Erdős, P., Tuza, Z.: Rainbow subgraphs in edge-colorings of complete graphs. In: Quo Vadis, Graph Theory? A Source Book for Challenges and Directions. Annals of Discrete Mathematics, vol. 55, pp. 81–88. Elsevier (1993)

  11. Feige, U.: A threshold of \(\ln N\) for approximating set cover. J. ACM 45(4), 634–652 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  12. Feige, U.: Relations between average case complexity and approximation complexity. In: Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing, STOC ’02, pp. 534–543. ACM (2002)

  13. Feige, U., Kortsarz, G., Peleg, D.: The Dense \(k\)-subgraph problem. Algorithmica 29(3), 410–421 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  14. Gusfield, D.: Haplotype inference by pure parsimony. In: Combinatorial Pattern Matching. Lecture Notes in Computer Science, vol. 2676, pp. 144–155. Springer (2003)

  15. Hahn, G., Thomassen, C.: Path and cycle sub-ramsey numbers and an edge-colouring conjecture. Discret. Math. 62(1), 29–33 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  16. Hajiaghayi, M.T., Jain, K., Konwar, K., Lau, L.C., Măndoiu, I.I., Russell, A., Shvartsman, A., Vazirani, V.V.: The minimum \(k\)-colored subgraph problem in haplotyping and DNA primer selection. In: Proceedings of the International Workshop on Bioinformatics Research and Applications (IWBRA) (2006)

  17. Huang, Y.T., Chao, K.M., Chen, T.: An approximation algorithm for haplotype inference by maximum parsimony. J. Comput. Biol. 12(10), 1261–1274 (2005)

    Article  Google Scholar 

  18. Hüffner, F., Komusiewicz, C., Niedermeier, R., Rötzschke, M.: The parameterized complexity of the rainbow subgraph problem. Algorithms 8(1), 60–81 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  19. Katrenič, J., Schiermeyer, I.: Improved approximation bounds for the minimum rainbow subgraph problem. Inf. Process. Lett. 111(3), 110–114 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  20. Khot, S.: Ruling out PTAS for graph min-bisection, dense \(k\)-subgraph, and bipartite clique. SIAM J. Comput. 36(4), 1025–1071 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  21. Kortsarz, G.: On the hardness of approximating spanners. Algorithmica 30(3), 432–450 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  22. Peleg, D.: Approximation algorithms for the label-cover\(_{max}\) and red-blue set cover problems. J. Discret. Algorithms 5(1), 55–64 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  23. Popa, A.: Approximating the rainbow—better lower and upper bounds. In: COCOON. Lecture Notes in Computer Science, vol. 7434, pp. 193–203. Springer (2012)

  24. Raghavendra, P., Steurer, D., Tulsiani, D.: Reductions between expansion problems. Electron. Colloq. Comput. Complex. (ECCC) 17, 172 (2010)

    Google Scholar 

  25. Rödl, V., Tuza, Z.: Rainbow subgraphs in properly edge-colored graphs. Random Struct. Algorithms 3(2), 175–182 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  26. Simonovits, M., Sós, V.T.: On restricted colourings of \(K_n\). Combinatorica 4(1), 101–110 (1984)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Indian Institute of Technology Bombay, Mumbai, India

    Sumedh Tirodkar & Sundar Vishwanathan

Authors
  1. Sumedh Tirodkar
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sundar Vishwanathan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sumedh Tirodkar.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Tirodkar, S., Vishwanathan, S. On the Approximability of the Minimum Rainbow Subgraph Problem and Other Related Problems. Algorithmica 79, 909–924 (2017). https://doi.org/10.1007/s00453-017-0278-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-017-0278-4

Keywords

Search

Navigation