New answers tagged graphs
0
votes
Subgraphs of DAG minimizing overlap
I suppose that all $k$ subsets should be non-empty. (Otherwise all vertices belonging to the same subset is the simplest way to solve the problem optimally.) This problem is $\mathrm{NP}$-hard for ...
- 383
0
votes
Bellman Ford: Why do we need to use the same vertex with edgesAllowed - 1 in the bellman ford recursive recurrence
If you mean $\text {if } i > 0 \text{ and } v \ne s$ as condition for the last line, then you are right. However then you lose an opportunity to check whether there is a negative cycle containing ...
- 383
0
votes
Optimizing node removal in a graph to achieve minimal edge weights while maintaining a certain total node weight
The problem is NP-complete by reduction from the knapsack problem, so you should not expect any efficient algorithm that works correctly in all possible cases.
A plausible approach to solve this in ...
D.W.♦
- 164k
0
votes
Which is more fundamental: key-value or subject-predicate-object?
Intriguing indeed. This boils down to the fundamental question of whether an attribute is more fundamental than a property. Typically, the key in a KV is composed of an object and a field name. The ...
- 1
1
vote
Accepted
UNIQUE-PATH in P assuming LPATH is in P
Hint:
this is perhaps not the best argument, but it follows the intuition you mentioned in the question.
Note that, assuming $\text{LPATH} \in \text{P}$, it is easy to find, in polynomial time, a ...
- 4,735
1
vote
Is there an A*/D* variant for graph where path to destination is unraveled based on whether it's closer to the destination?
Knowing how chunks are connected and the cost to get from one chunk to another, you could run A* or D* on the graph of the chunks. It would even tell you (approximately or precisely) which chunks are ...
- 1,845
1
vote
Assignment problem with no cost
Nicholas Mancuso gave a good response, but it doesn't actually answer the question --- it only outlined a way to generate diverse groups, not how to decide whether a group is diverse (outside of a ...
- 55
0
votes
Accepted
Variant of the k-MST problem on directed graphs?
This problem is $\mathrm{NP}$-hard. We can reduce DFAS to this problem.
Directed Feedback Arc Set (DFAS) problem is the following: given a directed graph $D$ and number $k$ check whether there is an ...
- 383
1
vote
Why is it not possible to recognize a self-complementary graph just by searching for a self-complementary graph on $8$ vertices?
Suppose a graph $G=$ $P_4\cdot P_4$. For any three disjoint induced $P_4$ subgraphs $A,B,C:$ $G[V(A)\cup V(B)]$ or $G[V(A)\cup V(C)]$ is not self-complementary.
This shows that the following statement ...
- 1,966
0
votes
Shortest path to all nodes from a center point, repeats allowed
The answer from StackOverflow:
The typical approach is to create a distance matrix that gives the
shortest-path distance between any two nodes. So d(i,j) = ...
1
vote
Path Through Graph That Minimizes Node Attributes
Produce graph H by replacing each node $v_i$ with two nodes $I_i$ and $O_i$ and an arc $(I_i,O_i)$ between them, where input arcs to original node $v_i$ be as input arcs to new node $I_i$ and output ...
1
vote
Accepted
Find the number of sink nodes per source node efficiently
Assuming you are asking about a directed graph:
As far as I am aware, I believe there is no solution that is significantly faster from running DFS once for each source (or, running DFS on the reverse ...
D.W.♦
- 164k
Top 50 recent answers are included