Laakeri
  • Member for 3 years, 3 months
  • Last seen this week
Best parameterized algorithm for maximum clique
Accepted answer
13 votes

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

View answer
Implication of solving 3SUM problem of a certain size on the Exponential Time Hypothesis
Accepted answer
9 votes

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

View answer
When does a bipartite graph have bounded treewidth?
7 votes

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

View answer
Finding simple fixed length paths in directed graphs
7 votes

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

View answer
Is the isomorphism problem between posets represented by DAGs GI-complete?
Accepted answer
6 votes

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

View answer
conversion to DAG
6 votes

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

View answer
Parameterized complexity of tree/branch decomposition
Accepted answer
4 votes

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

View answer
Does replacing each vertex of $G$ by $H$ increase treewidth of $G$ by at most $\Delta(G)$?
Accepted answer
4 votes

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

View answer
On $\text{ETH}$ with $m$ as parameter: consequences of algorithm running in time $2^{\delta m}$ where $\delta \to 0$ as $k \to \infty$
4 votes

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

View answer
Is a grid graph a vertex-minor of a complete graph?
Accepted answer
3 votes

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

View answer
Reduction graph to planar bounded treewidth and bounded diameter graph
Accepted answer
3 votes

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

View answer
Find the shortest s-t trail(edge disjoint path) in a graph with negative weight edges
Accepted answer
3 votes

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

View answer
Obtaining Sets of Ancestors Quickly in a Directed Acyclic Graphs
Accepted answer
2 votes

We can reduce Boolean matrix multiplication to this problem by a three level construction, where the edges from the first level to the second level are determined by the first matrix and the edges ...

View answer
Complexity of MAX-ONEs Monotone 2-SAT with $n^{3/2}$ or $C n^2$ clauses?
2 votes

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
Minimum vertex cover and odd cycles
Accepted answer
2 votes

Yes. By Proposition 2.3 of [1], 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
Is homogeneity required in Hyafil's arithmetic circuit decomposition theorem when applied to monotone circuits?
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
Neighborly properties in a bipartite graph
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 ...

View answer