Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.
10 votes
Accepted

Find research partner (profession and beginner)

I don't know of such a page. Most researchers have specific problems that they are interested in working on, and would only want to collaborate on those. If you pick a particular area and focus on ...
user avatar
  • 7,022
6 votes

The complexity of determining if a fixed graph is a minor of another

There are old results showing that linear minor testing is possible for some specific graphs H, basically by looking at back-edge patterns in depth-first search, with significant effort for each H, ...
user avatar
6 votes

Finding the single-crossing embedding of a single-crossing graph

You can in cubic time figure out which pair of edges to let cross. For this, try all $O(n^2)$ pairs, augment the graph by replacing the two edges by a degree 4 vertex (representing the crossing), and ...
user avatar
  • 562
6 votes
Accepted

Complexity of "can we get a cycle by stacking directed bipartite graphs?"

Update: Davide showed that this problem is PSPACE-hard here, settling PSPACE-completeness. NP-hardness This is NP-hard by reduction from 3SAT. Let's consider a formula in $k$ variables. Below is the ...
user avatar
  • 562
6 votes
Accepted

exact path cover for undirected graph

Found the following paper "NP-completeness of some problems of partitioning and covering in graphs" by B.Péroche. The paper proves that deciding whether the edges of a graph can be ...
user avatar
6 votes
Accepted

Pagerank in directed *acyclic* graphs (DAG)

As suggested by the comments (thanks!), the answer is positive and rather easy. We want to compute the pagerank of all vertices of a DAG (Directed Acyclic Graph) $G = (V,E)$ with $n$ vertices and $m$ ...
user avatar
5 votes
Accepted

Proving a property of minimal st-separators that are not minimum st-separators

It does not hold, as can be seen from the red separator in this example. Furthermore, a vertex in a minimum separator can be separated from $s$ and $t$ by a minimal separator:
user avatar
  • 166
5 votes

Complexity of "can we get a cycle by stacking directed bipartite graphs?"

PSPACE-completeness As suggested by Tim here, the problem can be shown to be PSPACE-hard by reduction from the Corridor Tiling Problem: Instance: a finite set of Wang tiles $\mathcal{T}=\{T_1,\ldots,...
user avatar
5 votes
Accepted

Are there an algorithm that find Minimum spanning tree in $O(n^2\log\log^*n)$?

Yes, there are many such algorithms. Two of the easiest are (1) Use Borůvka's algorithm, where each vertex finds its minimum-weight outgoing edge, you form trees from selected edges, collapse each ...
user avatar
4 votes
Accepted

Partition the edges of a bipartite graph into perfect $b$-matchings

Here's a counter-example for $k= 4$. Take $G = K_{2,2}$, specifically $G=(V, E)$ where $V=\{1,2,3,4\}$ and $E=\{(1,3), (1, 4), (2,3), (2,4)\}$. Define $b^1$ by $b^1_1 = b^1_3 = 1$ and $b^1_2=b^1_4=0$. ...
user avatar
  • 8,133
4 votes

Coloring intersection graph of squares

Even computing a maximum independent set of unit axis-parallel squares is known to be np-hard: https://www.sciencedirect.com/science/article/pii/0020019081901113?via%3Dihub Since coloring is a "...
user avatar
4 votes

Does such a graph exist?

EDIT: The answers below are for previous versions of the question. Answer for third version: [This version asked for an edge-colored graph $G$ with a vertex $r$ such that has exactly three edges $a,b,...
user avatar
  • 8,133
4 votes

Is there a standard axiomatization of graph width parameters?

This isn't quite what you were asking for, but one of the first papers on treewidth found this parameter by axiomatizing a lattice of parameters for graphs, among which treewidth is the top element. ...
user avatar
4 votes
Accepted

Question about algorithm for enumerating minimal AB-separators

tldr: your counterexample is correct. Longer Answer: The way $A$-$B$-separators are defined above the problem to determine whether at least one $A$-$B$-separator exists is NP-complete. In particular ...
user avatar
  • 3,216
3 votes
Accepted

Is a grid graph a vertex-minor of a complete graph?

Vertex-minors of complete graphs are either complete graphs, star graphs, or edgeless graphs, so this does not hold for $k \ge 2$. Proof that vertex-minors of complete graphs are complete, star, or ...
user avatar
  • 1,423
3 votes
Accepted

State of the art approximation algorithm for $\text{MAXCUT}$ that does better than Goemans and Williamson

These are not directly comparable: Goemans–Williamson and related work: find a cut in any graph G [of some graph family] that is at least X times the size of the maximum cut of G. This is the usual ...
user avatar
3 votes

Can this special case of Node Weighted Steiner Tree be solved in polynomial time?

To answer my own question, I have found that this problem is indeed NP-Hard via a reduction from the Cactus Augmentation Problem (which is NP-hard). In "Parameterized Algorithms to Preserve ...
user avatar
2 votes

Dynamic programming and shortest path problem

Here's a less formal answer that I hope nonetheless addresses the spirit of the question. Many standard dynamic-programming algorithms are easily seen to be equivalent to shortest-path (or longest-...
user avatar
  • 8,133
2 votes

exact path cover for undirected graph

Just a partial answer. Gallai's conjecture was recently proven for planar graphs: https://arxiv.org/abs/2110.08870. The paper gives an algorithm to find the $\lceil \frac{n}{2}\rceil$ desired paths. ...
user avatar
  • 1,133
2 votes
Accepted

Nontrivial Algorithms for Coloring (Parameterized by Pathwidth)

I’m 99% certain that the proof in the paper you cite already shows this - the statement of Theorem 4 states the running time lower bound correctly as $(k-\epsilon)^{fvs}$ and incorrectly as $(3-\...
user avatar
  • 3,216
2 votes
Accepted

Parameterized algorithm when the parameter is not known in advance?

I turn my different comments into an answer as I think it gives most answers. The original definition of FPT states that a parametrized problem $(L, p)$ is FPT if there exists an algorithm deciding ...
user avatar
  • 1,855
2 votes
Accepted

Proof of SPFA's worst-case complexity?

Here's the algorithm (from the wikipedia page) then a proof of the time bound: ...
user avatar
  • 8,133
2 votes

Is the center of a BFS tree a good approximation of the graphs center?

In the worst case, this algorithm gives a 2-approximation (the trivial upper bound). Take a cycle on some $n=4m$ vertices, vertex set $v_0,\ldots,v_{n-1}$, with one chord between $v_0$ and $v_{2m}$. ...
user avatar
  • 211
1 vote
Accepted

Is there FPT or XP algorithms knowm for Shortest Steiner cycle and $(a,b)$-Steiner path problem

Note that you can reduce shortest $(a,b)$-Steiner path to shortest Steiner cycle by adding a terminal vertex of degree 2 adjacent to $a$ and $b$. If you are asking for derandomization of the Björklund,...
user avatar
  • 1,423
1 vote
Accepted

Finding a path in a graph hitting a particular vertex

here is a sketch of the idea: If you don't have the constraint that the path is simple (i.e. no edge is used twice) then you just have to find a path from $u$ to $v$ and one from $v$ to $w$. If you ...
user avatar
  • 685
1 vote

Why is "topological sorting" topological?

Topology is the study of how "shapes" change when you apply continuous transformations to them. The central object of study is a topological space, which can be thought of as a way of saying ...
user avatar

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