# Tag Info

Accepted

### Easy/hard NP-hard problems on perfect graphs

ISGCI is the go-to site for finding such results. On the perfect graph page, you can find that the Hamiltonian cycle problem is NP-hard for perfect graphs, because the problem is already NP-hard for ...
• 2,727
Accepted

### Undecidable problems in finite graphs

Given a graph class $\mathcal G$, computing the set of forbidden graph minors of $\mathcal G$ is undecidable. A Note on the Computability of Graph Minor Obstruction Sets for Monadic Second Order ...
• 16.7k

### Usage of matrix multiplication for distance products

Nice idea! But no, that doesn't work, alas. The problem with your approach is that the numbers become enormous, which makes matrix multiplication slow. It is tempting to say that the running time of ...
• 161k
Accepted

### MSOL and Courcelle's theorem for maximum clique

The formula as stated in the question has to modified before Courcelle's theorem can be applied to prove FPT w.r.t. tree width. Courcelle's theorem allows a cardinality predicate. i.e., you can ...
• 340
Accepted

### Find the transitive closure but with a twist

Your problem (called path avoiding forbidden pairs problem) is NP-hard. Here is a reduction from the CNF SAT problem. We construct a set of relations such that $s \mathbin{R'} t$ if and only if a ...
• 2,727

### Find hierarchical clustering of documents

One thing you might like to consider is hierarchical topic modelling. But first, let's talk about topic modelling. One way to think about a document is that it covers certain topics. A news article ...
• 22.3k
Accepted

### Why there is no definition of cut vertex in directed graph?

Cut-points (or cut-vertices, or articulation points) in undirected graphs have a property that deleting a vertex from the graph (either cut-point or not) one may get new cut-points, but can't ...
• 303

### Shortest path between two nodes with time-dependent edge weights

You need to build a bigger graph (a "product graph", in the jargon). Each vertex is identified by a pair $(V,t)$, where $V$ is a location (a point on the map where two road segments join) ...
• 161k

### Shortest path between two nodes with time-dependent edge weights

Instead of having the vertices in your navigation graph defined by only the location you can have vertices defined by location and time. That way the result of $cost((V1, t), V2)$ will depend on time ...
• 4,516
Accepted

### Given a family of 0-1 matrices $M$ find the sum of matrices from $M$ which has minimal rank

This is a homogeneous variant of the minrank problem over $\mathbb{F}_2$. We looked at it in the following paper: M. BlĂ¤ser et al, "On the Orbit Closure Containment Problem and Slice Rank of ...

### Undecidable problems in finite graphs

Given $k$ pairs of source and sink nodes $(s_i,t_i)$, $i=1,\ldots,k$ in a network (directed graph), the multi-commodity flow problem asks whether we can simultaneously transport commodities from $s_i$ ...
1 vote

### Proof of NP-hardness: Is the problem of finding the minimum edge-weighted subgraph with at least M pairwise connectivity NP-hard?

This is still reducible from the k-minimum spanning tree problem. To reduce an instance, add a big number $W > \sum_{e \in E} c_e$ to every edge weights. Now, any optimal solution will use the ...
• 2,727
1 vote

### MSOL for a vertex-cover enlargement problem

You can use CMSOL which allows cardinality predicates. See 5.2.6 in this report. This is authored by Courcelle himself. You can refer the original paper by Courcelle too, but it is a bit more terse. ...
• 340
1 vote

### BFS on directed graph with disjointed edges?

Assuming you want the following: Given a graph $G=(V,E)$ and a set of nodes $N \subseteq V$, find a tree $T$ that spans over all nodes in $N$. Here, $T$ is a spanning tree of the induced subgraph of a ...
• 1,340
1 vote

### Implementation of planar graph max cut

Yes, you can. There is a preprint of the paper available for download (PDF) which likely contains all details you need. It seems like they actually implemented the algorithm, so it could be possible ...
• 16.7k
1 vote
Accepted

There is a paper by Babenko and Gusakov ("New Exact and Approximation Algorithms for the Star Packing Problem in Undirected Graphs"). It discusses the star packing problem. Given an integer $... • 932 1 vote ### How to get the shortest simple path in a directed Graph with an additional constraint that it needs to use two arcs in the said path The problem of finding 2 disjoints paths from$s_1$to$t_1$and from$s_2$to$t_2\$ is NP-complete for directed graphs. Your problem is therefore NP-complete. Reduction: Given an instance of 2-...
• 16.7k

Only top scored, non community-wiki answers of a minimum length are eligible