New answers tagged graphs
0
Your problem is $\rm NP$-hard by a reduction from the minimum-weight Steiner tree problem.
Let $G=(V,E;w)$ be a graph with non-negative edge weights $w(e)$, $e \in E$, and let $S \subseteq V $ be a non-empty set of terminal vertices.
The vertex set in your problem will coincide with $V$. Choose the concave function $c_e(x)$ that describes the cost of ...
0
This problem is NP-Hard. I will present a simple reduction from the vertex-cover problem to this problem. This reduction shows that there is probably no polynomial time algorithm for this problem, since such an algorithm will implies a polynomial time algorithm for the vertex cover problem which will implies that P=NP, since the vertex cover problem is NP-...
0
Let's define a graph $G=(V,E)$, for which:
Set of vertices $V$ is identical to your SET1.
Two vertices $v_1,v_2 \in V$ are connected by an edge, if and only if there exists a vertex from the SET2, incident to both $v_1$ and $v_2$ in your bipartite graph.
For instance, the graph below corresponds to the bipartite graph from the example in your question:
...
0
The greedy algorithm always finds a minimal set (inclusion-wise). However, it does not necessarily find a minimum one.
So what does minimal and minimum mean, you might ask. Minimal set in a family of sets (say the set of all hitting sets), is a set that is not a superset of any other set in the family. That means, a minimal hitting set is a hitting set ...
3
You can actually solve this in $O(|V|+|E|)$ time. Since it is a DAG, we can apply dynamic programming.
Let $p = u_1u_2\dots u_k$ be a path and $cost(p) = w(u_1,u_2)\times w(u_2,u_3)\times\dots \times w(u_{k-1}, u_k)$ be the edge weight product of the path. One important observation is that $cost(u_0p_1) = w(u_0,u_1)\times cost(p_1)$.
Now, for each node $u$,...
1
Here is what it boils down to. There are $n$ vertices $v_1,\ldots,v_{n-1},v$. For each $i$, there is an edge either from $v$ to $v_i$ or from $v_i$ to $v$. We need to show that one of the following holds:
There is an edge from $v$ to $v_1$.
There is $i < n-1$ such that there are edges from $v_i$ to $v$ and from $v$ to $v_{i+1}$.
There is an edge from $v_{...
0
Pathfinding algorithms that are able to recompute the best path when the graph changes without doing a full recomputation are called "Incremental".
The incremental version of Dijkstra's algorithm has the horrible name DynamicSFSW-FP.
The much more common algorithm which combines this with A* is called LPA*
3
The example you specified is not turning a greedy algorithm to a dynamic programming solution. You reduced a problem to another using a greedy argument and solved the other problem using dynamic programming. That is why it is still not clear to me what do you mean by converting greedy to dynamic programming. However, that being said I have three points to ...
2
Yes it exists and the existence of a linear ordering not only shows the existence of the topological oredering over the vertices but also that this ordering is unique. It is not hard to prove that the graph represents a linear ordering using the facts that the graph is complete and acyclic. That should be a good exercise for you (proving a relation is a ...
2
I think I have some suggestions.
You can make a binary variable $e_{ij}$ per edge corresponding to if those two vertices are in a clique together or not. Being in a clique is a transitive property. $e_{ij} \wedge e_{jk} = e_{ik}$. This "and" constraint is expressible as a MIP. This can be achieved with the constraint $e_{ik} <= e_{ij}$, $e_{ik} <= e_{...
1
The second implementation is correct (so Theorem 2.2 survives): If the condition $c(v) > c(u)$ causes the inner while to halt, that same value of $v$ will be give the optimal value for every following value of $g$, simply because the condition is independent of $g$.
1
Your groups of tiles can be considered as graphs, where vertices represent tiles and two vertices are connected by edge if and only if their corresponding tiles touch each other side by side. So, in terms of graph theory, the problem you are trying to solve is known as CISE (Connected Induced Subgraphs Enumerating). You can find a number of papers, ...
0
$\mathbf 1.$
Say there are two paths from node A to node B.
Path1 has 4 edges.
Path2 has 2 edges.
An overall increase in edge weight by x increases,
the cost of Path1 by 4x.
the cost of Path2 by 2x.
If Path 1 was the optimum path found by Dijkstra then in order for it to remain the optimum path even after the increase.
$Cost_{Path1} + 4x < Cost_{...
0
If there is no upper bound on the number of classes per semester and the dependencies are acyclic, this can be solved by a modified topological sort as follows:
Schedule every class for which all (zero or more) prerequisites are met in the earliest semester in which they are available. Repeat this for all remaining classes (i.e. those not yet scheduled), ...
0
In a binary tree, you can represent the tree from root to leaves as follows:
0 root
1 2 root's children
3 4 5 6 root's grandchildren
etc.
To get the children of a node, you take its index x and compute 2x+1 and 2x+2.
This makes some certain assumptions: Each node has exactly two children, except the leaves, which are all on the same (or two neighboring) ...
0
You could compute a full Single Source Shortest Paths (SSSP) at the beginning for both of your vertices (s and t).
Then, whenever you add an edge, you update only the shortest paths affected, i. e. you check whether the edge uv provides an improvent for sv, su, tv or tu. If not, your SSSP is still correct. If it gives an improvement, you then also have to ...
0
A possible solution may be to compute the all pair shortest path matrix and then select the largest value in the matrix.
As long as |E|<<|V|^2 or the graph is not dense, your complexity constraint should be satisifed.
Johnson's algorithm does it in O(|V|^2 log |V|+|V||E|).
Refer to this for a better understanding of time complexity in case of ...
0
This answer on stackoverflow has an example of why 1 is false.
https://stackoverflow.com/questions/10790909/adding-weights-to-all-edges-of-graph-change-in-spanning-tree-and-shortest-path
Quoting from the above:
Consider a graph with 3 vertices (A,B,C), with the following edges:
A-B = 1
A-C = 0
C-B = 0
The shortest weighted path between A and B is ...
1
If the case arrives where you see the case of a node being already visited but it is the parent of your current node, you just have to check whether there is a double edge between them. How to do that depends on your data structure, but if your adjacency list is sorted it would just amount to searching for the edge and checking how often it is in there.
...
1
We first sort all edges according to their costs from small to large. Say the sorted edges are $e_1,e_2,\ldots,e_{n(n-1)}$, and the corresponding costs are $w_1\le w_2\le\cdots\le w_{n(n-1)}$. Then we find the minimal $i$ such that the graph is strongly connected only with the edges $e_1,\ldots,e_i$. Now $w_i$ is the minimal tank capacity we want.
Sorting ...
3
This will not work. Consider
(a)-4->(b)
(a)-1->(c)
(b)-2->(d)
(c)-6->(d)
Looking for the max cost path from (a) to (d), the max heap will follow (a)-4->(b)-2->(d) and never explore the (a)-1->(c) edge.
See here for an alternative based on a topological sort.
2
Your conjecture is false. There are regular graphs with an even number of vertices yet without a 1-regular subgraph. See this question on Mathematics.
The complement of such a graph gives a counterexample to your claim that you can always add a perfect matching to increase the regularity (when the number of vertices is even).
In the bipartite case, however,...
0
The point of my exercise is to encode the path existence in CNF
Well, a trivial way to do this is by reducing the problem to 2-SAT, following this set of rules:
Assing a literal to every edge of your graph, for example first element in first row become $a$, second element in first row become $b$ etc.
Put in OR relation the literal in the "start" position ...
1
While your description of the problem is not super clear. I can guess that you're looking at a maximum bipartite matching problem. Which by the way, can also be viewed as a degenerate case of maxflow problem. Both problems are classic, you should have no problem finding resources on them. For example, this.
1
The class of graphs that contain a Hamiltonian cycle is known as Hamiltonian graphs. Being Hamiltonian doesn't really imply much: a wide range of well-known graph parameters (diameter, treewidth, chromatic number, ...) can still be unbounded. At least partly, this is the reason there aren't many non-trivial subclasses of Hamiltonian graphs known.
As an ...
0
The algorithm in the (edited) answer has worst-case quadratic time complexity. (An worst-case example is a tree where there are just two strands and the given nodes are the two leaves.)
A (non-recursive) $O(n)$ time and $O(1)$ space algorithm, assuming that nodes have parent pointers:
Compute the height of both target nodes.
Until the heights are equal, ...
-1
"I'm having trouble finding literature on this type of graph"
A good book recommended by universities is Discrete Mathematics and It's Applications by Kenneth H. Rosen. You can find the chapter on graphs (Euler and Hamilton paths) on page 666.
1
The minimum cost perfect matching problem is formally defined as an optimization problem where:
The set of instances is the set of all edge-weighted undirected graphs $G=(V, E, w)$, where $w : E \to \mathbb{R}$.
Given an instance $G=(V, E, w)$, the set of feasible solutions are the perfect matchings $M$ of $G$, i.e., all the sets $M \subseteq E$ such that, $...
2
Let me tell you what Bellman-Fords is actually doing because the sentence by relaxing all edges once for every vertex in the graph is not very accurate. In Bellman-Ford you care about single-source-shortest-path. Since every path in the graph have at most $n$ nodes it has at most $n-1$ edges.
Let's say the source node is $s$, then create a table $distance[\...
3
I suggest you use a search algorithm on the following statespace: the state is a set of adjacent tiles whose numbers sum to 7 or less; it is possible to transition from state $s$ to $s'$ if $s'$ is obtained by adding to $s$ one tile that is adjacent to some tile in $s$. The initial state has the empty set $\emptyset$, and it can transition to any state ...
1
Use depth-first search, or breadth-first search, or any other graph search algorithm. You don't need Tarjan's algorithm.
0
The solution provided here is highly inelegant as it uses a lemma which is a more general result. This 'solution' should instead be considered as more of a hint: a minimal solution can instead be found by extracting the most relevant parts of the proof of the lemma.
Note that $w_1(e_1)<w_1(e_2)\Leftrightarrow w_2(e_1)>w_2(e_2)$ implies that $w_1(e_1)=...
0
Using arrays instead of classes and objects would make it easier for you to implement the disjoint set union concept.
Here's a resource to start off with:- Disjoint Set Union
for edge in edges:
if find_set(edge[0], node_map) != find_set(edge[1], node_map):
unioned_set = union(edge[0], edge[1], node_map, sets_map)
cost_map[edge[2]] = ...
4
It turns out that the very popular textbook Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, sneakily avoids this issue by giving a different definition of cycle in undirected vs directed graphs.
In Section B.4, it defines cycle and simple cycle as I do (they also require at least one edge), in directed graphs. In an undirected graph, ...
2
Your post-traversal numbering of the component $C$ is incorrect. The vertex labeled as $1,6$ was assigned its post-traversal number too early; a depth-first search will also explore the vertices of $D$ before assigning the post-traversal number to this vertex.
1
You are on the right track, just keep going: what if you take a slightly larger complete graph? Specifically, what if you take a $K_{101}$?
3
Arguably two of the most definite textbooks on graph theory are Bundy & Murty (BM) (roughly 15000 citations at the time of writing) and Diestel (at least hundreds of citations).
In BM (Section 1.6), the definition of a cycle is obtained via walks and trails, i.e., a cycle is a non-empty trail in which the first and last vertex are repeated. In your ...
3
I'll go with (3)
From Bundy and Murty's Graph Theory with Applications (http://www.maths.lse.ac.uk/Personal/jozef/LTCC/Graph_Theory_Bondy_Murty.pdf), sections 1.6 "Paths and Connections" and 1.7 "Cycles":
A walk is a finite non-null sequence of alternating vertices and edges (repetition of both allowed).
If the edges of a walk are distinct then it is also ...
4
Those answers assume that all edge capacities are integers. Assuming they are, this works.
Suppose the min-cut in the original graph has total capacity $x$; then it will have total capacity $x(|E|+1)+k$ in the transformed graph, where $k$ counts the number of edges crossing that cut. Note that if you consider any cut in the original graph with larger ...
2
The problem statement needs to be specified more precisely to be meaningful.
If I'm being pedantic, I would say that the minimum number of propositional variables is zero: you can solve the graph coloring problem (taking exponential time if necessary), then either use the formula $\text{True}$ or $\text{False}$ according to whether the graph is $C$-...
1
The problem was considered by Kahn and Saks in their paper Balancing poset extensions. Earlier related works are Fredman, How good is the information theory bound in sorting? and Linial, The information-theoretic bound is good for merging.
Kahn and Saks showed that partially sorted lists can be sorted in $O(\log M)$, where $M$ is the number of possible ...
0
I will assume, that all weights are rational (since there is a problem with representing irrational numbers on computer).
You can solve this problem by using linear programming in similar manner to finding maximal flow.
$\forall_{v \in V} w_V$ is constant.
$\forall_{e \in E} w_e$ is variable.
Firstly, for each node we want to be sure that inward flow is ...
1
It is equivalent to the set cover problem. You can regard each vertex in the right side as a set of its neighbors in the left side. In your example, $e,f,g$ correspond respectively to the sets $\{d\},\{d\},\{a,b,c,d\}$. Now a minimum vertex cover in your problem is equivalent to a minimum set cover.
Top 50 recent answers are included
