I thought if one could solve one NP-complete problem then one can solve all of them. But you say that the treewidth doesn’t help at all with the Clique problem. Is the parametrized complexity filtration by treewidth not preserved by equivalence between different NP-complete problems somehow?
All NP-complete problems should have parameters that makes the problem polynomial when bounded, trivially so by the ⇒ 3-SAT ⇒ Bayes Net translation, and using the treewidth bound.
This isn’t the case for the clique problem (finding max clique) because it’s not NP-complete (it’s not a decision problem), so we don’t necessarily expect its parameterized version to be polynomial tractable — in fact, it’s the k-clique problem (yes/no is there a clique larger than size k) that is NP-complete. (so by the above translation argument, there certainly exists some graphical quantity that when bounded makes the k-clique problem tractable, though I’m not aware of it, or whether it’s interesting)
To me, the interesting question is whether:
(1) translating a complexity-bounding parameter from one domain to another leads to quantities that are semantically intuitive and natural in the respective domain.
(2) and whether easy instances of the problems in the latter domain in-practice actually have low values of the translated parameter.
rambling: If not, then that implies we need to search for a new k for this new domain. Perhaps this can lead to a whole new way of doing complexity class characterization by finding natural k-s for all sorts of NP-complete problems (whose natural k-s don’t directly translate to one another), and applying these various “difficulty measures” to characterize your NP-complete problem at hand! (I wouldn’t be surprised if this is already widely studied.)
Looking at the 3-SAT example (Qi are the propositional variables, Ci the ORs, and X the AND with Ai serving as intermediate ANDs):
re: (1), at first glance the treewidth of 3-SAT (clearly dependent on the structure of the Qi - Cj interaction) doesn’t seem super insightful or intuitive, though we may count the statement “a 3-SAT problem gets exponentially harder as you increase the formula-treewidth” as progress.
… but even that wouldn’t be an if and only if characterization of 3-SAT difficulty, because re: (2) there exist easy-in-practice 3-SAT problems that don’t necessarily have bounded treewidth (i haven’t read the link).
I would be interested in a similar analysis for more NP-complete problems known to have natural parameterized complexity characterization.
All NP-complete problems should have parameters that makes the problem polynomial when bounded, trivially so by the ⇒ 3-SAT ⇒ Bayes Net translation, and using the treewidth bound.
This isn’t the case for the clique problem (finding max clique) because it’s not NP-complete (it’s not a decision problem), so we don’t necessarily expect its parameterized version to be polynomial tractable — in fact, it’s the k-clique problem (yes/no is there a clique larger than size k) that is NP-complete. (so by the above translation argument, there certainly exists some graphical quantity that when bounded makes the k-clique problem tractable, though I’m not aware of it, or whether it’s interesting)
To me, the interesting question is whether:
(1) translating a complexity-bounding parameter from one domain to another leads to quantities that are semantically intuitive and natural in the respective domain.
(2) and whether easy instances of the problems in the latter domain in-practice actually have low values of the translated parameter.
rambling: If not, then that implies we need to search for a new k for this new domain. Perhaps this can lead to a whole new way of doing complexity class characterization by finding natural k-s for all sorts of NP-complete problems (whose natural k-s don’t directly translate to one another), and applying these various “difficulty measures” to characterize your NP-complete problem at hand! (I wouldn’t be surprised if this is already widely studied.)
Looking at the 3-SAT example (Qi are the propositional variables, Ci the ORs, and X the AND with Ai serving as intermediate ANDs):
re: (1), at first glance the treewidth of 3-SAT (clearly dependent on the structure of the Qi - Cj interaction) doesn’t seem super insightful or intuitive, though we may count the statement “a 3-SAT problem gets exponentially harder as you increase the formula-treewidth” as progress.
… but even that wouldn’t be an if and only if characterization of 3-SAT difficulty, because re: (2) there exist easy-in-practice 3-SAT problems that don’t necessarily have bounded treewidth (i haven’t read the link).
I would be interested in a similar analysis for more NP-complete problems known to have natural parameterized complexity characterization.
Yeah, I probably messed up here quite a bit, sorry.