Daniel Marx
• Member for 11 years
• Last seen more than 5 years ago

There are two important aspects of DP: (1) defining the subproblems (i.e., setting up a "table", which could be a multidimensional array indexed maybe by integers, vertices, subsets of vertices etc.) ...

A "gadget" is a small specialized device for some particular task. In NP-hardness proofs, when doing a reduction from problem A to problem B, the colloquial term "gadget" refers to small (partial) ...

Post a printed program near the door of the session room(s). Sounds like a basic thing, but for some reason most conferences do not do this. It costs nothing, but would be very helpful for answering ...

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

In this paper, I showed that if for some $k\geq 3$ there is a graph with maximum degree $k$ and chromatic edge strength strictly greater than $k$, then it is $\Theta_2^p$-complete to decide if ...

I think it is still open if Dominating Set or Hitting Set have a f(OPT) approximation for some (nontrivial) function f. This is should be a very difficult (and possible deep) question to answer. I ...

Maybe this is not the best example, but consider (Directed) Cycle Cover, where the task is to cover all the vertices by vertex-disjoint (directed) cycles. In the directed case, this can be reduced to ...

List Chromatic Number (Is it true that the graph has a vertex coloring whenever every vertex gets a list of k admissible colors?) is a $\Pi_2^P$-complete problem, but linear-time solvable on bounded-...

If $\mathcal{G}$ is a class of graphs with bounded treewidth, then the homomorphism problem from graphs in $\mathcal{G}$ is polynomial-time solvable. This can be generalized to the more general ...

This should be #W[1]-hard by a standard interpolation argument. Here is a rough sketch. First, consider the multicolored version of the biclique problem: given a graph whose set of vertices is ...

It is possible to prove the fixed-parameter tractability of various graph-theoretical problems (e.g., finding a path of length k or finding k disjoint triangles) using algebraic techniques by reducing ...

The following paper contains reductions for various parameterizations of Closest Substring where the running time depends exponentially or double exponentially on the parameter (and this dependence ...

Our recent paper shows that counting k-matchings is #W[1]-hard even in bipartite graphs. This answers your question. Radu Curticapean, Dániel Marx: Complexity of counting subgraphs: only the ...

The following recent paper seems to be related to your question: Connectivity and tree structure in finite graphs Johannes Carmesin, Reinhard Diestel, Fabian Hundertmark, Maya Stein http://arxiv.org/...

Our paper: http://arxiv.org/abs/1110.4765 shows that many of these problems are fixed-parameter tractable, i.e., we can decide in time f(k)*O(n+m) if an s-t separator of size k exists. This is true ...

Determining the winner of a "parity game" is known to be in $NP\cap coNP$, but it is an outstanding open problem whether it is in $P$. See e.g., http://lovelace.thi.informatik.uni-frankfurt.de/~...

The following paper gives an FPT algorithm for another variant of the problem, where we have to delete $k$ vertices to make the graph the disjoint union of s-plexes. An s-plex is a graph where every ...