Maximum clique in graphs with degree $d$ can be reduced to $n$ instances of maximum clique in a graph with at most $d$ vertices: for each vertex, compute maximum clique in the induced subgraph of the ...

I think currently it is not even known if strong ETH and 3SUM are related, see e.g. . For the relation of ETH and 3SUM, note that ETH really cannot be refuted by improving polynomial time ...

I think there is no simpler characterization than just the fact that the treewidth of $G$ is bounded. The intuition for why is that by subdividing each edge of a graph we get a bipartite graph with ...

The color coding technique for deciding if a graph contains a $k$-path, presented for example in the book Parameterized Algorithms, can be turned into output-sensitive enumeration algorithm for such ...

Graph isomorphism is GI-complete for DAGs: https://en.wikipedia.org/wiki/Graph_isomorphism_problem#Complexity_class_GI. The problem for partial orders is also GI-complete: We can reduce bipartite ...

This problem is equivalent to feedback arc set (in a tournament graph). It is NP-hard.

This paper https://arxiv.org/abs/2104.07463 gives an overview of treewidth algorithms in Table 1. Similar table also exists in Wikipedia. The situation for parameterized computing of an optimal tree ...

Let $G$ be a complete graph with $n$ vertices and $H$ be a complete graph with $n-1$ vertices, all marked. We replace each vertex of $G$ with $H$ to produce a graph $G^*$ with $n(n-1)$ vertices that ...

This is an answer to the updated question (the original question seems harder). Let $\mu'_k$ be the smallest constant such that $k$-SAT that has clauses of length exactly $k$ and no trivial clauses ...

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 ...

The diameter of $G'$ will not be bounded. Replacing edge crossings with gadgets can effectively cut each edge $O(n)$ times, so the diameter can blow up by a factor of $O(n)$.

The longest path problem can be reduced to this problem. Let $G = (V,E)$ be an instance of longest $s,t$-path problem. For each vertex $v \in V$ create two vertices, $v_{in}$ and $v_{out}$, and a ...

In both questions the answer is the same for any exponent $1 < \alpha < 2$. For the first question, we can use a degeneracy based algorithm to find an independent set of size $\Omega(\frac{n}{n^{... View answer Accepted answer 2 votes Yes. By Proposition 2.3 of , all elementary fractional extreme points of the LP correspond to subgraphs that contain odd cycles, and therefore if the graph contains no odd cycles, the LP has an ... View answer Accepted answer 1 votes No, homogeneity is not required when applying this theorem to monotone circuits, and in fact homogeneity is a quite technical restriction that can be removed even in the general case by weakening the ... View answer Accepted answer 1 votes There is a polynomial time algorithm for this problem. First, as pointed out by D.W., by Hall's theorem we can assume that there is a perfect matching between$A$and$B\$. In particular, if there is ...