New answers tagged graph-algorithms
0
A linear bound is impossible. Suppose your graph is a star, with half of the edges oriented towards the universal vertex $u$ and the rest oriented outward. In the transitive closure, the maximal cliques will be triangles, each of them containing $u$ and exactly one of its inneighbors and one of its outneighbors. This gives a quadratic number of maximal (and ...
0
After a bit more searching, it appears that what I'm looking for is unlikely to exist.
In [1], it is proven that approximating the minimum maximal independence number (which is equivalent to the minimum size of an independent dominating set) within a factor of $O(n^{1-\epsilon})$ is $\mathrm{NP}$-hard for any $\epsilon > 0$. This remains true even when ...
4
Per the section quoted in the comments, it appears that one of the cited documents takes input in the form of an adjacency matrix. In this scenario, taking $s$ and $t$ to correspond to the first and last indices respectively, we can prove that $\Omega(n^2)$ bits of the matrix may need to be read to decide STCONN even under the promise that the $(n/2)\times(n/...
Top 50 recent answers are included
Related Tags
graph-algorithms × 931graph-theory × 479
ds.algorithms × 307
cc.complexity-theory × 127
reference-request × 99
np-hardness × 65
approximation-algorithms × 64
co.combinatorics × 56
optimization × 41
directed-acyclic-graph × 41
shortest-path × 39
planar-graphs × 34
clique × 32
ds.data-structures × 28
matching × 26
graph-isomorphism × 25
time-complexity × 23
tree × 22
graph-colouring × 21
counting-complexity × 20
linear-programming × 19
parameterized-complexity × 18
treewidth × 17
fixed-parameter-tractable × 16
max-flow × 15