# Tag Info

### property of minimal triangulations

As @Laakeri commented, the connection between triangulations and minimal separators can be used to show this property. Based on the definitions: A subset $S \subseteq V$ is an $a, b$-separator of $G$ ...
Accepted

### Polynomial time algorihtms for two variants of the decision version of longest walk problem

I deleted my previous answer because there were some inaccuracies. Also I am going to assume that either, you are looking for the longest walk, with any nodes as endpoints, or you are looking for a ...
• 384
Accepted

1 vote

### Approximative counting of matchings in a graph

Both Jerrum and Sinclair have written a lot about this kind of topic over the years, and there are more recent references by them that you can check out. In particular, take a look at [1], it ...
• 11
1 vote

### Upper Bound for distance-two chromatic number in terms of maximum degree

Let $\Delta$ denote the maximum degree of $G$. The bound $\Delta^2+1$ cannot be improved significantly. For instance, even for a colouring variant called 2-ranking (which is a generalisation of ...
• 1,733
1 vote
Accepted

### A non-trivial combinatorial optimization

This is NP-hard even for $d=1$ by reduction from the (strongly NP-hard) Product Partition problem. Lemma 1. The problem (with either objective function) is NP-hard, even for $d=1$. Proof sketch. Given ...
• 10.8k
1 vote

### Generate TSP instances with known optimal

If someone is still searching for this, I might give a gist of how I understood that paper: Generate an optimal permutation $p$ of $\{1...n\}$. Create two random variables, $\alpha_i$ and $\beta_j$, ...
• 11
1 vote

### Maximal classes for which largest independent set can be found in polynomial time?

In the meantime, it was shown that the problem is polynomial-time solvable on $P_6$-free graphs: Andrzej Grzesik, Tereza Klimosová, Marcin Pilipczuk, Michal Pilipczuk: Polynomial-time Algorithm for ...

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