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 ...
- 27.4k
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 ...
- 27.4k
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 ...
- 15k
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 ...
- 469
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-...
- 15k
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.
- 1,516
Top 50 recent answers are included