# Tag Info

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 ...
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 ...
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 ...
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-...
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.