Daniel Marx
  • Member for 11 years
  • Last seen more than 5 years ago
If you could rename dynamic programming...
35 votes

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

View answer
What does 'gadget' mean in NP-hard reduction?
Accepted answer
26 votes

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

View answer
Small steps for better TCS conferences?
20 votes

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

View answer
What separates easy global problems from hard global problems on graphs of bounded treewidth?
Accepted answer
16 votes

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

View answer
Curious about computer-assisted NP-completeness proofs
15 votes

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

View answer
Existence of $opt^c$-approximation of Dominating Set with $c < 1$?
Accepted answer
15 votes

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

View answer
"Directed" problems that are easier than their "undirected" variant.
13 votes

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

View answer
Is there any problem in $\mathsf{\Sigma^P_2}$ which is solvable in bounded tree width graphs?
Accepted answer
11 votes

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

View answer
Deciding graph homomorphism
9 votes

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

View answer
Parametrized Complexity of Counting Bicliques
Accepted answer
9 votes

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

View answer
Algebraic formulation for packing problem
Accepted answer
9 votes

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

View answer
Instance of FPT-reductions that is not a polynomial-time reduction
9 votes

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

View answer
Is it known whether counting $q$-dimensional $p$-matching is $\#W[1]$-Hard?
Accepted answer
8 votes

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

View answer
Decomposing k-connected graphs into (k+1)-connected components
8 votes

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

View answer
Complexity of finding a graph separator with a given property
Accepted answer
8 votes

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

View answer
Graph problems with good characterization but not known to be in $P$
7 votes

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

View answer
Who are active researchers in the scheduling theory?
6 votes

It could be useful to look at the list of participants of recent Dagstuhl seminars on scheduling http://www.dagstuhl.de/program/calendar/partlist/?semnr=13111 http://www.dagstuhl.de/program/calendar/...

View answer
Variants of Cluster-Vertex-Deletion problem
Accepted answer
4 votes

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

View answer