3 years ago

# Fine-Grained Complexity and Conditional Hardness for Sparse Graphs.

Vijaya Ramachandran, Udit Agarwal

There is a large class of path and cycle problems on graphs that currently have $\tilde{O}(n^3)$ time algorithms. Graphs encountered in practice are typically sparse, with $m <<n^2$, were $n$ and $m$ are the number of vertices and edges in the graph. We investigate the fine-grained complexity of these problems on sparse graphs, and our main results are the following:

1. Reductions and Algorithms. We define the notion of a sparse reduction that preserves graph sparsity, and we present several such reductions for graph problems in the $\tilde{O}(mn)$ class. This gives rise to a rich partial order on graph problems with $\tilde{O}(mn)$ time algorithms. Surprisingly, very few of the known subcubic results are sparse reductions. We develop new techniques in order to preserve sparsity in our reductions, many of which are nontrivial and intricate. Some of our reductions also lead to improved algorithms for various problems on finding simple cycles in undirected graphs.

2. Conditional Hardness. We show that if the Strong Exponential Time Hypothesis (SETH) holds, then several problems in the $\tilde{O}(mn)$ class, including certain problems that are also in the sub-cubic equivalence class cannot have sub-$mn time algorithms, i.e., algorithms that run in$O(m^{\alpha} \cdot n^{2-\alpha -\epsilon})$time, for constants$\alpha \geq 0$,$\epsilon > 0$. In particular, this result means that under SETH, the sub-cubic equivalence class is split into at least two classes when sparsity is taken into account, with triangle finding problems having faster algorithms than Eccentricities or Betweenness Centrality. This hardness result for the$\tilde{O}(mn)$class is also surprising because a similar hardness result for the sub-cubic class is considered unlikely since this would falsify NSETH (Nondeterministic SETH). Publisher URL: http://arxiv.org/abs/1611.07008 DOI: arXiv:1611.07008v2 You might also like Discover & Discuss Important Research Keeping up-to-date with research can feel impossible, with papers being published faster than you'll ever be able to read them. That's where Researcher comes in: we're simplifying discovery and making important discussions happen. With over 19,000 sources, including peer-reviewed journals, preprints, blogs, universities, podcasts and Live events across 10 research areas, you'll never miss what's important to you. It's like social media, but better. Oh, and we should mention - it's free. Researcher displays publicly available abstracts and doesn’t host any full article content. If the content is open access, we will direct clicks from the abstracts to the publisher website and display the PDF copy on our platform. Clicks to view the full text will be directed to the publisher website, where only users with subscriptions or access through their institution are able to view the full article. time algorithms, i.e., algorithms that run in\n$O(m^{\\alpha} \\cdot n^{2-\\alpha -\\epsilon})$time, for constants$\\alpha \\geq\n0$,$\\epsilon > 0$. In particular, this result means that under SETH, the\nsub-cubic equivalence class is split into at least two classes when sparsity is\ntaken into account, with triangle finding problems having faster algorithms\nthan Eccentricities or Betweenness Centrality. This hardness result for the\n$\\tilde{O}(mn)$class is also surprising because a similar hardness result for\nthe sub-cubic class is considered unlikely since this would falsify NSETH\n(Nondeterministic SETH).\n ","htmlAbstract":null,"createdDate":"2019-10-02T16:28:24.000Z","media":null,"settings":null,"pdfUrl":"https://arxiv.org/pdf/1611.07008","openAccessUrl":null,"authors":{"type":"json","json":["Vijaya Ramachandran","Udit Agarwal"]},"contentType":null,"actionButton":null,"journal":{"type":"id","generated":false,"id":"Journal:1156","typename":"Journal"},"headlineImage":null,"__typename":"V4Paper","doi":"arXiv:1611.07008v2","paperUrl":"http://arxiv.org/abs/1611.07008","metrics":{"type":"id","generated":true,"id":"$V4Paper:110808.metrics","typename":"Metrics"}},"Journal:1156":{"id":"1156","name":"arXiv Computer Science","cover":{"type":"id","generated":true,"id":"$Journal:1156.cover","typename":"Image"},"__typename":"Journal"},"$Journal:1156.cover":{"baseURL":"https://s3-eu-west-1.amazonaws.com/stackademic/assets/journal_cover_arxviv.png","__typename":"Image"},"$V4Paper:110808.metrics":{"selectedCount":1,"viewedCount":0,"bookmarkedCount":0,"__typename":"Metrics"}}; window.__REDUX_STATE__ = {"feed":{"scrollPos":0,"openAccess":false,"performRefetch":{}},"history":{"historyChanges":0}}; 3 years ago # Fine-Grained Complexity and Conditional Hardness for Sparse Graphs. Vijaya Ramachandran, Udit Agarwal There is a large class of path and cycle problems on graphs that currently have$\tilde{O}(n^3)$time algorithms. Graphs encountered in practice are typically sparse, with$m <<n^2$, were$n$and$m$are the number of vertices and edges in the graph. We investigate the fine-grained complexity of these problems on sparse graphs, and our main results are the following: 1. Reductions and Algorithms. We define the notion of a sparse reduction that preserves graph sparsity, and we present several such reductions for graph problems in the$\tilde{O}(mn)$class. This gives rise to a rich partial order on graph problems with$\tilde{O}(mn)$time algorithms. Surprisingly, very few of the known subcubic results are sparse reductions. We develop new techniques in order to preserve sparsity in our reductions, many of which are nontrivial and intricate. Some of our reductions also lead to improved algorithms for various problems on finding simple cycles in undirected graphs. 2. Conditional Hardness. We show that if the Strong Exponential Time Hypothesis (SETH) holds, then several problems in the$\tilde{O}(mn)$class, including certain problems that are also in the sub-cubic equivalence class cannot have sub-$mn

time algorithms, i.e., algorithms that run in $O(m^{\alpha} \cdot n^{2-\alpha -\epsilon})$ time, for constants $\alpha \geq 0$, $\epsilon > 0$. In particular, this result means that under SETH, the sub-cubic equivalence class is split into at least two classes when sparsity is taken into account, with triangle finding problems having faster algorithms than Eccentricities or Betweenness Centrality. This hardness result for the $\tilde{O}(mn)$ class is also surprising because a similar hardness result for the sub-cubic class is considered unlikely since this would falsify NSETH (Nondeterministic SETH).

Publisher URL: http://arxiv.org/abs/1611.07008

DOI: arXiv:1611.07008v2

You might also like
Discover & Discuss Important Research

Keeping up-to-date with research can feel impossible, with papers being published faster than you'll ever be able to read them. That's where Researcher comes in: we're simplifying discovery and making important discussions happen. With over 19,000 sources, including peer-reviewed journals, preprints, blogs, universities, podcasts and Live events across 10 research areas, you'll never miss what's important to you. It's like social media, but better. Oh, and we should mention - it's free.

Researcher displays publicly available abstracts and doesn’t host any full article content. If the content is open access, we will direct clicks from the abstracts to the publisher website and display the PDF copy on our platform. Clicks to view the full text will be directed to the publisher website, where only users with subscriptions or access through their institution are able to view the full article.