# Tag Info

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

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

### 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 ...
• 164k

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

### 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 ...
• 164k

Top 50 recent answers are included