62

If you really want to know what led Neil Robertson and me to tree-width, it wasn't algorithms at all. We were trying to solve Wagner's conjecture that in any infinite set of graphs, one of them is a minor of another, and we were right at the beginning. We knew it was true if we restricted to graphs with no k-vertex path; let me explain why. We knew all such ...


29

Yes, this is known. It appears in one of the must-cite references on triangle finding... Namely, Itai and Rodeh show in SICOMP 1978 how to find, in $O(n^2)$ time, a cycle in a graph that has at most one more edge than the minimum length cycle. (See the first three sentences of the abstract here: http://www.cs.technion.ac.il/~itai/publications/Algorithms/min-...


27

It's GI-complete which means it's probably not NP-complete. Reduction from undirected graph isomorphism to DAG isomorphism: given an undirected graph $(V,E)$, make a DAG whose vertices are $V\cup E$, with an edge from $x$ to $y$ whenever $x\in V$, $y\in E$, and $x$ is an endpoint of $y$. (i.e. replace every undirected edge with a node and two ingoing edges) ...


25

A rainbow matching in an edge-colored graph is a matching whose edges have distinct colors. The problem is: given an edge-colored graph $G$ and an integer $k$, does $G$ have a rainbow matching with at least $k$ edges? This is known as rainbow matching problem, and its NP-complete even for properly edge-colored paths. The authors even note that prior to this ...


21

I think there are lot of similar problems. Here are two in vertex version and one in edge version: 1) Does a given graph have an independent feedback vertex set? (we don't care about the size of the set). This problem is NP-complete; the proof can be derived from the proof of Theorem 2.1 in Garey, Johnson & Stockmeyer. 2) Does a given graph have a ...


21

There are several algorithms that count the simple paths of length $k$ in $f(k)n^{k/2+O(1)}$ time, which is a whole lot better than brute force ($O(n^k)$ time). See e.g. Vassilevska and Williams, 2009.


21

From the comments above: the Hamiltonian cycle problem remains NP-complete even in grid graphs with max degree 3 [1], but in these graphs every traversal of a node requires two edges and at most one edge remains unused, so a node cannot be traversed twice by an Eulerian path. So apparently there is an immediate reduction from the Hamiltonian cycle problem ...


21

I think, your problem is NP-complete. It is a special case of a theorem by Farrugia, stating that it is NP-hard to test if the vertex set a graph can be partitioned into two subsets $V_1,$ and $V_2$ such that $G(V_1)$ belongs to the graph class $\mathcal{P}$ and $G(V_2)$ belongs to the graph class $\mathcal{Q}$, provided $\mathcal{P}$ and $\mathcal{Q}$ ...


21

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, the resulting restriction of the problem is denoted $k$-UCC (in undirected graphs) and $k$-DCC (in directed graphs). The complexity of the directed version is ...


19

It's #P-complete (Valiant, 1979) so you're unlikely to do a whole lot better than brute force, if you want the exact answer. Approximations are discussed by Roberts and Kroese (2007). B. Roberts and D. P. Kroese, "Estimating the number of $s$--$t$ paths in a graph". Journal of Graph Algorithms and Applications, 11(1):195-214, 2007. L. G. Valiant, "The ...


19

I'm not sure about this specific method for achieving $O(n^2)$ time, but two different methods for performing Kruskal in $O(n^2)$ time are given in my paper "Fast hierarchical clustering and other applications of dynamic closest pairs" (SODA 1998, arXiv:cs.DS/9912014, and J. Experimental Algorithms 2000): Use Prim–Dijkstra–Jarník instead and then sort the ...


19

The most natural restriction on the proof DAG is that it be a tree – that is, any "lemma" (intermediate conclusion) is not used more than once. This property is called being "tree-like". General resolution is exponentially more powerful than tree-like resolution, as shown for example by Ben-Sasson, Impagliazzo and Wigderson. The concept has also been ...


19

There is a simple construction: Take any $d$-regular non-bipartite expander $G=(V,E)$ - there are several constructions of those, e.g., Margulis, or the Zig-Zag construction. Now, turn it into a bipartite graph $G' = (V_1 \cup V_2, E')$ as follows: $V_1$ and $V_2$ are copies of $V$. Two vertices $v_1 \in V_1$ and $v_2 \in V_2$ are adjacted in $G'$ if and ...


19

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 realized by a random graph. The earliest reference I'm aware of for this is "Cube-Supersaturated Graphs and Related Problems" by Erdos and Simonovits, where it'...


18

The first problem comes to my mind is the 2-path problem (or more generally k-path problem). Given $(s_1,t_1)$ and $(s_2,t_2)$, find two disjoint paths from $s_1$ to $t_1$ and $s_2$ to $t_2$, respectively. The problem is NPC for directed graphs but polynomial-time solvable for undirected graphs (although not trivial).


18

Yes; they are known as $2K_2$-free graphs. Some additional references: "On Toughness and Hamiltonicity of $2K_2$-Free Graphs" "The maximum number of edges in $2K_2$-free graphs of bounded degree"; "Two characterisations of minimal triangulations of $2_{K2}$-free graphs"


17

This recent paper finally proves that edge contractions do not preserve the property that a set of graphs has bounded clique-width.


17

Yes, a polynomial time algorithm was first given in: Neil Robertson, P. D. Seymour, Robin Thomas. "Permanents, Pfaffian orientations, and even directed circuits." Annals of Mathematics 150.3 (1999): 929-975. arXiv edit: Actually, according to the acknowledgements section of the above paper, the result was first obtained by McCuaig who later published it as:...


17

Locally bipartite graphs obviously contain the locally independent (= triangle-free) graphs. According to graphclasses.org, most of the standard graph problems are already NP-complete for triangle-free graphs, and therefore also NP-complete for locally bipartite graphs. The two exceptions are clique (which is obviously polynomial for locally bipartite graphs ...


17

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-neighbor graphs", Disc. Comput. Geom. 17: 263–282, https://www.ics.uci.edu/~eppstein/pubs/EppPatYao-DCG-97.pdf For points in any fixed higher dimension it is $\...


16

In the notation of Lee and Streinu (citation below) the second class you list are the (2,3)-sparse graphs. They give an algorithm to test whether a graph is (k,l)-sparse in polynomial time. However, the situation with planar graphs and $|E'|\le 3|V'|-6$ is a little more complicated, because that inequality is not true for all sets of vertices (if it were ...


16

I think that we can do slightly better than $O(n^{1+\omega})$ for dense graphs, by using rectangular matrix multiplication. A similar idea was used by Eisenbrand and Grandoni ("On the complexity of fixed parameter clique and dominating set", Theoretical Computer Science Volume 326(2004) 57–67) for 4-clique detection. Let $G=(V,E)$ be the graph in which we ...


16

Most algorithms for graphs of bounded treewidth are based on some form of dynamic programming. For these algorithms to be efficient, we need to bound the number of states in the dynamic programming table: if you want a polynomial-time algorithm, then you need a polynomial number of states (e.g., n^tw), if you want to show that the problem is FPT, you usually ...


16

The problem is that you confused the definiton in the paper of Aharoni & Szabo and the normally used definition for the term "independence domination number". The former one refers to the largest size over all minimum set dominating an independent set, and the latter one is the smallest size of a dominating set which is also an independent set. These ...


16

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 the 10th ACM Symposium on Theory of Computing (STOC '78), pp. 253–264, doi:10.1145/800133.804355. Reed, Bruce; Smith, Kaleigh; Vetta, Adrian (2004), "Finding odd ...


16

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 to compute the treewidth of graphs of maximum degree $9$. Finally, for any graph of treewidth at least $2$, subdividing an edge (i.e, replacing the edge by a ...


15

If I'm not mistaken your question was answered by Chen-Thurley-Weyer-2008 modulo parameterized complexity assumptions. I didn't read the paper carefully yet, but as far as I understood, there is a dichotomy in the sense that if $C$ is finite then the problem is in $P$, but if $C$ has an infinite number of graphs then the induced subgraph isomorphism is $W[...


15

Computing ad(G) in $O(n^{2-\delta})$ time for constant $\delta>0$ even in graphs with $\tilde{O}(n)$ edges and $n$ vertices would imply that the Strong Exponential Time Hypothesis (SETH) is false. (SETH was defined by Impagliazzo, Paturi and Zane'01 and implies that CNF-SAT on $n$ variables does not have $O(2^{(1-\varepsilon)n})$ time algorithms.) To ...


15

I don't know how to avoid doing $n$ matrix multiplies, but you can analyze it in such a way that the time is effectively that of a smaller number of them. This trick is from Kloks, Ton; Kratsch, Dieter; Müller, Haiko (2000), "Finding and counting small induced subgraphs efficiently", Information Processing Letters 74 (3–4): 115–121, doi:10.1016/S0020-0190(...


15

The earliest reference I could find for topological sort is from [Lasser61]: A network of directed line segments free of circular elements is assumed. The lines are identified by their terminal nodes and the nodes are assumed to be numbered by a non-topological system. Given a list of these lines in numeric order, a simple technique can be used to create ...


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