# Tag Info

8

If you want an FPT algorithm for the problem (parameterized by treewidth $t$), you want an algorithm working in time $f(t) \cdot n^{O(1)}$, where $f$ is any computable function (depending solely on $t$). Of course, it would be nice to make $f$ as appealing as possible. In addition to the mentioned algorithm running in $O(t^t n)$ time, you can also get a ...

5

There is an outline of the algorithm you want in these slides: http://www.cs.bme.hu/~dmarx/papers/marx-warsaw-fpt2. Given a nice-tree decomposition of width $w$ for $G$, the algorithm runs in time $O(w^w \cdot n)$. As it is based on a nice-tree decomposition, you will need to show what happens in the case of a forget node, an introduce node, and a join node ...

4

This graph is known as a de Bruijn graph, and its Hamiltonian circuits are known as de Bruijn sequences. Both are well understood (for example, we know exactly how many of these exist).

3

The classical version of this question is for Hamiltonian cycles, but there is probably little difference. I will only consider the version with cycles. In order for a graph to contain a Hamiltonian cycle, the minimal degree should be at least 2. This is essentially the only obstruction for Hamiltonicity. To state this we need to define the following ...

3

No. A graph with only the edges of a polygon has an Hamilton circle, but the degree of each vertex is 2.

3

The statement in CRLS is not wrong in any case; an algorithm that runs in $O(n)$ time also runs in $O(n^2)$ time. Of course, it would be more precise to state the running time as $O(n)$ if this were true, so why doesn't CLRS do this? First off, this depends on the encoding chosen for $G$. If an adjacency matrix is used, a graph with $V$ vertices always has ...

3

This result is proved in the senior thesis The complexities of puzzles, cross sum and their another solution problems (ASP) by Takahiro Seta. The systematic study of ASPs was initiated by Ueda and Nagao in their paper NP-completeness Results for NONOGRAM via Parsimonious Reductions. See also Takayuki Yato's master thesis, Complexity and completeness of ...

3

Just add the constraint that $x_{1j}=x_{nj}$ for all $j$, and make a special exception to constraint 2 so that you omit constraint 2 in the case where $i=1$ and $k=n$. Everything works fine for a directed graph. You just need to interpret constraint 5 appropriately.

3

The $n$-ary Hadamard gate acts on $n$ qubits. The state of the $n$ qubits is a unit norm vector of dimension $2^n$. You can take as basis the vectors $|x\rangle$ for $x \in \{0,1\}^n$. As it happens, the $n$-ary Hadamard gate can be simulated by $n$ unary Hadamard gates acting on the individual qubits, which is what you see on page 6-3. The reason is that ...

2

Recall a Hamiltonian cycle visits each vertex of a graph exactly once. Thus, the cycles H1 and H2 in your second example can't be Hamiltonian cycles in the same graph. In your first example, the two cycles could be distinct Hamiltonian cycles in e.g. the complete graph on 4 vertices. That is to say, there can definitely be multiple Hamiltonian cycles in a ...

2

This is NOT an answer. This post is just to construct a concrete numeric example out of the left diagram in the picture in the question. (This answer, too long to fit as a comment, was requested by a user who wanted to see a concrete numeric example which his greedy algorithm may fail. It was written about the same time when OP added a numeric example that ...

1

Does a graph have a hamiltonian cycle if for anyone of its edges, it has a hamiltonian path after the removal of that edge? Note that any hypohamiltonian graph must be such a graph. Is it even true that every hypohamiltonian graph has a hamiltonian cycle? Not necessarily. A counterexample is the Peterson graph, which is hypohamiltonian but not hamiltonian....

1

Counting the number of Hamiltonian circuits in a graph is $\mathsf{\#P}$-hard (see for example this answer). Your problem is even harder, since we can use your problem together with binary search to count the number of Hamiltonian circuits in a given graph. As an aside, let me mention that listing things in lexicographical order might be harder than listing ...

1

Perhaps the most comprehensive list is available via ISGCI, along with references. Examples for which the problem is easy include bounded treewidth graphs and many subclasses of chordal graphs. As to why exponential time seems unavoidable in general, we don't strictly know. As far as we know, P = NP is also possible.

1

There is no "purpose" for the condition that the number of vertices be divisible by 3 – it is part of the problem statement. DHAM3 is the special case of DHAM in which the number of vertices is divisible by 3. In principle this might make the problem easier (a special case can only be easier), but in this case DHAM3 is also NP-hard (and so NP-complete), as ...

1

In order to prove NP-completeness of a given problem $\Pi$, it is enough to prove that $\Pi \in$ NP and that there exists a polynomial time reduction from any NP-complete problem $\Pi^*$ to $\Pi$. The reduction must take instances of $\Pi^*$ and return instances of $\Pi$, in polynomial time, such that the answer is the same in both $\Pi^*$ and $\Pi$. A ...

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