Skip to main content
6 votes
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 ...
pcpthm's user avatar
  • 2,727
5 votes
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 ...
Pål GD's user avatar
  • 16.7k
4 votes

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 ...
D.W.'s user avatar
  • 161k
4 votes
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 ...
Sriram's user avatar
  • 340
4 votes
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 ...
pcpthm's user avatar
  • 2,727
3 votes

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 ...
Pseudonym's user avatar
  • 22.3k
3 votes
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 ...
Smylic's user avatar
  • 303
2 votes

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) ...
D.W.'s user avatar
  • 161k
2 votes

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 ...
ratchet freak's user avatar
2 votes
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 ...
Vladimir Lysikov's user avatar
2 votes

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$ ...
Cheuk Ting Li's user avatar
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 ...
pcpthm's user avatar
  • 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. ...
Sriram's user avatar
  • 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 ...
codeR's user avatar
  • 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 ...
Pål GD's user avatar
  • 16.7k
1 vote
Accepted

Algorithm for finding a path factor in a graph

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 $...
Ivan Smirnov's user avatar
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-...
Pål GD's user avatar
  • 16.7k

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