New answers tagged

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 ...
Steven's user avatar
  • 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 ...
Steven's user avatar
  • 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.'s user avatar
  • 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 ...
Pål GD's user avatar
  • 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 ...
Command Master's user avatar
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-...
Pål GD's user avatar
  • 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.
Watercrystal's user avatar
  • 1,516

Top 50 recent answers are included