Beating Treewidth for Average-Case Subgraph Isomorphism

Author Gregory Rosenthal



PDF
Thumbnail PDF

File

LIPIcs.IPEC.2019.24.pdf
  • Filesize: 0.57 MB
  • 14 pages

Document Identifiers

Author Details

Gregory Rosenthal
  • University of Toronto, Canada

Acknowledgements

Thanks to Benjamin Rossman for introducing me to this topic, and for having many helpful discussions about the research and about drafts of this paper. Thanks to Henry Yuen for providing feedback on a draft of this paper as well. Part of this work was done while the author was visiting the Simons Institute for the Theory of Computing.

Cite AsGet BibTex

Gregory Rosenthal. Beating Treewidth for Average-Case Subgraph Isomorphism. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.IPEC.2019.24

Abstract

For any fixed graph G, the subgraph isomorphism problem asks whether an n-vertex input graph has a subgraph isomorphic to G. A well-known algorithm of Alon, Yuster and Zwick (1995) efficiently reduces this to the "colored" version of the problem, denoted G-SUB, and then solves G-SUB in time O(n^{tw(G)+1}) where tw(G) is the treewidth of G. Marx (2010) conjectured that G-SUB requires time Omega(n^{const * tw(G)}) and, assuming the Exponential Time Hypothesis, proved a lower bound of Omega(n^{const * emb(G)}) for a certain graph parameter emb(G) = Omega(tw(G)/log tw(G)). With respect to the size of AC^0 circuits solving G-SUB, Li, Razborov and Rossman (2017) proved an unconditional average-case lower bound of Omega(n^{kappa(G)}) for a different graph parameter kappa(G) = Omega(tw(G)/log tw(G)). Our contributions are as follows. First, we show that emb(G) is at most O(kappa(G)) for all graphs G. Next, we show that kappa(G) can be asymptotically less than tw(G); for example, if G is a hypercube then kappa(G) is Theta(tw(G)/sqrt{log tw(G)}). Finally, we construct AC^0 circuits of size O(n^{kappa(G)+const}) that solve G-SUB in the average case, on a variety of product distributions. This improves an O(n^{2 kappa(G)+const}) upper bound of Li et al., and shows that the average-case complexity of G-SUB is n^{o(tw(G))} for certain families of graphs G such as hypercubes.

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
  • Theory of computation → Fixed parameter tractability
  • Mathematics of computing → Graph algorithms
Keywords
  • subgraph isomorphism
  • average-case complexity
  • AC^0
  • circuit complexity

Metrics

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

References

  1. Noga Alon and Dániel Marx. Sparse balanced partitions and the complexity of subgraph problems. SIAM J. Discrete Math., 25(2):631-644, 2011. URL: https://doi.org/10.1137/100812653.
  2. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844-856, 1995. URL: https://doi.org/10.1145/210332.210337.
  3. Kazuyuki Amano. k-subgraph isomorphism on AC⁰ circuits. Comput. Complexity, 19(2):183-210, 2010. URL: https://doi.org/10.1007/s00037-010-0288-y.
  4. L. Sunil Chandran and Telikepalli Kavitha. The treewidth and pathwidth of hypercubes. Discrete Math., 306(3):359-365, 2006. URL: https://doi.org/10.1016/j.disc.2005.12.011.
  5. Friedrich Eisenbrand and Fabrizio Grandoni. On the complexity of fixed parameter clique and dominating set. Theoret. Comput. Sci., 326(1-3):57-67, 2004. URL: https://doi.org/10.1016/j.tcs.2004.05.009.
  6. L. H. Harper. On an isoperimetric problem for Hamming graphs. Discrete Appl. Math., 95(1-3):285-309, 1999. URL: https://doi.org/10.1016/S0166-218X(99)00082-7.
  7. Johan Håstad. Almost optimal lower bounds for small depth circuits. In Proc. 18th Ann. ACM Symp. on Theory of Computing, pages 6-20, 1986. URL: https://doi.org/10.1145/12130.12132.
  8. Johan Håstad, Ingo Wegener, Norbert Wurm, and Sang-Zin Yi. Optimal depth, very small size circuits for symmetric functions in AC⁰. Inform. and Comput., 108(2):200-211, 1994. URL: https://doi.org/10.1006/inco.1994.1008.
  9. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. System Sci., 63(4):512-530, 2001. URL: https://doi.org/10.1006/jcss.2001.1774.
  10. Yuan Li, Alexander Razborov, and Benjamin Rossman. On the AC⁰ complexity of subgraph isomorphism. SIAM J. Comput., 46(3):936-971, 2017. URL: https://doi.org/10.1137/14099721X.
  11. Dániel Marx. Can you beat treewidth? Theory Comput., 6(1):85-112, 2010. URL: https://doi.org/10.4086/toc.2010.v006a005.
  12. Dániel Marx and Michał Pilipczuk. Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask). In STACS, volume 25 of LIPIcs, pages 542-553. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014. URL: https://doi.org/10.4230/LIPIcs.STACS.2014.542.
  13. K. Nakagawa and O. Watanabe. Gap Between Two Combinatorial Measures for Constant Depth Circuit Complexity of Subgraph Isomorphism. Technical report, Tokyo Institute of Technology, 2011. Google Scholar
  14. Jaroslav Nešetřil and Svatopluk Poljak. On the complexity of the subgraph problem. Comment. Math. Univ. Carolin., 26(2):415-419, 1985. Google Scholar
  15. Neil Robertson and P. D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms, 7(3):309-322, 1986. URL: https://doi.org/10.1016/0196-6774(86)90023-4.
  16. Benjamin Rossman. On the constant-depth complexity of k-clique. In Proc. 40th Ann. ACM Symp. on Theory of Computing (STOC), pages 721-730, 2008. URL: https://doi.org/10.1145/1374376.1374480.
  17. Benjamin Rossman. Average-Case Complexity of Detecting Cliques. Ph.d., MIT, 2010. Google Scholar
  18. Benjamin Rossman. The monotone complexity of k-clique on random graphs. SIAM J. Comput., 43(1):256-279, 2014. URL: https://doi.org/10.1137/110839059.
  19. Benjamin Rossman. Lower bounds for subgraph isomorphism. In Proc. Intern. Congress of Mathematicians (ICM), volume 3, pages 3409-3430, 2018. URL: https://eta.impa.br/dl/051.pdf.
  20. Abraham Silberschatz, Henry F. Korth, and S. Sudarshan. Database System Concepts. McGraw-Hill Book Company, 6 edition, 2011. Google Scholar
  21. Andrew Chi-Chih Yao. Probabilistic computations: Toward a unified measure of complexity. In Proc. 18th Ann. IEEE Symp. on Foundations of Computer Science, pages 222-227, 1977. URL: https://doi.org/10.1109/SFCS.1977.24.
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