New answers tagged graphs
1
vote
Accepted
Is a predecessor subgraph always connected?
Let $s$ be your source vertex and let $d(v)$ denote the distance from $s$ to $v$. Let $v_1, \dots, v_n$ be the vertices of your graph in non-decreasing order of distances from $s$.
You can show by ...
1
vote
Finding a cycle of length log(n) given min degree
Assume that the graph is non-empty, pick an arbitrary vertex $s$ and construct the first $\lceil \log n \rceil$ levels of the BFS tree $T$ from $s$.
You will encounter some non-tree edge $(u,v)$ in ...
1
vote
Number of matchings in a bipartite graph having missing edges
The problem is #P-hard, which means it is believed that there is no efficient algorithm for this problem.
See Counting and finding all perfect/maximum matchings in general graphs and Number of ...

D.W.♦
- 154k
1
vote
Accepted
Minimum edges removed to turn a strongly connected graph into an acyclic graph
This is a classic NP-complete problem called Feedback Arc Set.
The problem is solvable in fixed parameter tractable time $k^{O(k)}$, and there is an approximation algorithm, however it's open whether ...
2
votes
Accepted
Is there an algorithm for the distrubution of ducks into ponds?
This can be solved with max-flow: create a bipartite graph with parks on one side and ponds on another, have an edge with infinite capacity if a duck from park A can fly to pond B, and for each park ...
5
votes
Accepted
Determining circumference of a graph
Unfortunately the following problem is very hard:
Problem: Long Cycle
Input: A graph $G$ and an integer $k$
Question: Does $G$ have a simple cycle of length at least $k$?
The problem is clearly NP-...
0
votes
Accepted
Dominating sets and treewidth
Every graph with a DS of size $\leq k$ has a DS of size exactly $k$ (assuming $k$ is bounded by the number of vertices) as every superset of a DS is itself a DS.
Top 50 recent answers are included
Related Tags
graphs × 4814algorithms × 2188
shortest-path × 467
complexity-theory × 419
graph-traversal × 357
weighted-graphs × 280
trees × 251
optimization × 248
np-complete × 227
network-flow × 181
minimum-spanning-tree × 175
data-structures × 164
time-complexity × 155
algorithm-analysis × 139
combinatorics × 129
np-hard × 118
search-algorithms × 116
dag × 107
approximation × 105
colorings × 101
spanning-trees × 99
reductions × 98
matching × 94
bipartite-matching × 94
terminology × 88