Skip to main content
22 votes

Algorithm for finding a 3-cycle cover

The cycle cover problem (CC) is the problem of finding a spanning set of cycles in a given directed or undirected input graph. If all the cycles in the cover must consist of at least $k$ edges/arcs, ...
Gamow's user avatar
  • 5,772
20 votes
Accepted

Number of 4 cycles

Yes, this is known. For $d = \Omega(n^{1/2})$ with a sufficiently large implicit constant, any $n$-node graph of average degree $d$ has $\Omega(d^4)$ total $C_4$s. This is best possible because it's ...
GMB's user avatar
  • 2,403
18 votes

Are there interesting graph classes where the treewidth is hard (easy) to compute?

Treewidth is NP-hard to compute on co-bipartite graphs, indeed the original NP-hardness proof of treewidth of Arnborg et al. shows this. Additionally, Bodlaender and Thilikos showed that it is NP-hard ...
daniello's user avatar
  • 3,266
17 votes
Accepted

Number of connected components of a random nearest neighbor graph?

For $n$ uniformly random points in a unit square the number of components is $$\frac{3\pi}{8\pi+3\sqrt{3}}n+o(n)$$ See Theorem 2 of D. Eppstein, M. S. Paterson, and F. F. Yao (1997), "On nearest-...
David Eppstein's user avatar
16 votes
Accepted

Are there poly time algorithms to determine if a graph is almost bipartite?

The vertex version is called "odd cycle transversal"; it's NP-complete but fixed-parameter tractable. See: Yannakakis, Mihalis (1978), "Node-and edge-deletion NP-complete problems", Proceedings of ...
David Eppstein's user avatar
16 votes
Accepted

Does Hadwiger conjecture imply that NP = coNP?

I think the problem here is that you are stating the converse of Hadwiger's conjecture. The conjecture (according to Wikipedia) states that "if a graph needs at least k colors for a proper coloring, ...
Michael Lampis's user avatar
15 votes
Accepted

Smallest vertex cover which is also an independent set

This is the "Independent Vertex Cover" problem. It is solvable in polynomial time. To see this, note that for every edge, exactly one endpoint of the edge must be in a vertex cover. We can reduce the ...
Ryan Williams's user avatar
15 votes
Accepted

Connectivity of a random regular graph of degree $d$

For constant $d \geq 3$, a random $d$-regular graph is connected with high probability. In fact, it is an expander with high probability. See for example this note by David Ellis. Friedman even showed ...
Yuval Filmus's user avatar
  • 14.5k
14 votes
Accepted

Is the following graph optimization problem approximable within a constant factor?

The problem is very similar to Min Uncut. In Min Uncut, given a graph $G = (V, E)$, we need to find a subset of edges $E'$ s.t. $G - E'$ is bipartite; the objective is to minimize the size of $|E'|$. ...
Yury's user avatar
  • 3,909
13 votes
Accepted

For which graphs is the DFS tree always a path?

This is equivalent to the property that you can construct a Hamiltonian path by greedily taking an arbitrary edge at every vertex. Searching for greedy Hamiltonian path turned up: Greedily ...
Peter Taylor's user avatar
  • 1,235
13 votes
Accepted

questions on implications Babais quasi P time graph isomorphism result

Johnson graphs are actually easy to recognize. In particular, you can recognize whether an input graph is a Johnson graph in polynomial time, and you can construct an isomorphism between two ...
Yuval Filmus's user avatar
  • 14.5k
13 votes
Accepted

Is there a planar 4-regular graph that is 3-acyclic colourable?

I can prove that no 4-regular graphs are 3-acyclic colorable. Consider a 4-regular graph with a 3-coloring. If we call the colors $a, b, c$, then one of the three subgraphs generated by restricting ...
isaacg's user avatar
  • 806
13 votes
Accepted

Isomorphic graph embeddings in the Euclidean Space

This is not possible in general. The 4-cycle is actually helpful to consider: embedding it in $\mathbb{R}^k$ in the way you describe requires the images of all four vertices to be coplanar, forming a ...
Klaus Draeger's user avatar
12 votes
Accepted

Pathwidth of planarized drawing of $K_{3,n}$

A naive drawing of $K_{3,n}$ will have pathwidth $O(n)$. I think that's tight, and that the pathwidth is always $\Omega(n)$. Here's an argument why. (1) Fix a drawing of $K_{3,n}$. Without loss of ...
David Eppstein's user avatar
12 votes
Accepted

Is there an algorithm that finds the forbidden minors?

The answer by Mamadou Moustapha Kanté (who did his PhD under supervision of Bruno Courcelle) to a similar question cites A Note on the Computability of Graph Minor Obstruction Sets for Monadic Second ...
Thomas Klimpel's user avatar
12 votes
Accepted

Number of simple paths between two vertices in a DAG

Every simple path is uniquely determined by the subset of vertices that it passes through: if you topologically order the DAG (arbitrarily) then a path through any subset of vertices must go through ...
David Eppstein's user avatar
11 votes

Number of connected components of a random nearest neighbor graph?

EDIT 2: Made explicit the underlying non-asymptotic bounds in the calculation. EDIT: Replaced the calculation for two dimensions by the case of arbitrary constant dimension. Added a table of the ...
Neal Young's user avatar
  • 10.8k
11 votes
Accepted

Finding vertex separator such that the induced subgraph has minimal number of edges

An independent set that disconnects its graph is called an "independent cut", graphs that contain an independent cut are called "fragile graphs", and recognizing fragile graphs is ...
David Eppstein's user avatar
10 votes
Accepted

Hard extendability problems

n-coloring the n x n Sudoku graph is trivial, but if some of the colors are given to you (the extendability version) it becomes NP-complete. By the "Sudoku graph" I mean the natural graph whose ...
Joshua Grochow's user avatar
10 votes
Accepted

The maximum number of induced cycles in a simple directed graph

I don't know what's already known but the obvious bounds are that it is at most $\binom{n}{n/2}$ (Sperner's theorem) and at least $3^{n/3}$ (for $n$ a multiple of three that is at least 9: form a ...
David Eppstein's user avatar
10 votes
Accepted

What is the connection between moments of Gaussians and perfect matchings of graphs?

This fact is a corollary of a more general theorem. Let $\gamma_1,\dots, \gamma_{2n}$ be (jointly) Gaussian random variables; we don't assume that they are independent or identically distributed. Let $...
Yury's user avatar
  • 3,909
10 votes
Accepted

Is this vertex ordering optimization NP-Hard?

Consider your problem restricted to 3-regular graphs. Consider some ordering of the vertices. Define a split vertex to be a vertex $v$ such that both $succ(v)$ and $pred(v)$ are non-empty and define a ...
Mikhail Rudoy's user avatar
10 votes
Accepted

Natural (well studied) classes of graphs with treewidth $\Theta(n^\alpha)$ with $1/2 < \alpha < 1$

The intersection graph of interior disjoint balls in $\mathbb{R}^d$, should have treewidth $O(n^{1-1/d})$, if there is justice in the universe (let me think about it - yep - there is). The treewidth ...
Sariel Har-Peled's user avatar
10 votes
Accepted

Known property? Maximum radius of connected induced subgraph

The property $\Pi_r$, defined as containing exactly the graphs $G$ such that every induced subgraph $H$ of $G$ has diameter at most $r$, is the same as the class of graphs that do not contain a $P_{r+...
Christian Komusiewicz's user avatar
10 votes
Accepted

Is the maximum independent set in cubic planar graphs NP-complete?

A complete NP-completeness proof for this problem is given right after Theorem 4.1 in the following paper. Bojan Mohar: "Face Covers and the Genus Problem for Apex Graphs" Journal of ...
Gamow's user avatar
  • 5,772
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 ...
usul's user avatar
  • 7,615
9 votes

What is the best exact algorithm to compute the core of a graph?

The problem of determining whether a given graph is a core graph is easily seen to be in co-NP. In fact, it is co-NP complete. The problem of determining whether a given subgraph H is a core of a ...
Szymon Toruńczyk's user avatar
9 votes
Accepted

Are social networks typically good expanders?

Social networks typically have many vertices with just one or two connections to the rest of the graph. Such vertices will typically lead to a bad spectral gap. What you could hope for is good ...
Adam Smith's user avatar
9 votes
Accepted

Proof that the graph optimization problem is NP-hard

This problem is in P, it can be reduced to the Minimum cut problem. The graph construction is as follows - Add a source and a sink vertex. For each vertex $i$, add an edge with cost $w(i)$ from ...
saisandeep's user avatar
9 votes
Accepted

For any two non-isomorphic graphs $G, H$, does there exist a polysize, polylog quantifier depth first order formula which witnesses this?

Thanks to my colleague Maxim Zhukovskii for suggesting this answer. It turns out that the answer is negative, and the counterexample is rather simple. Just take $G=K_m\sqcup \overline{K_m}$ and $H=K_{...
Daniil Musatov's user avatar

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