CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_upper_j_idt162",{id:"formSmash:upper:j_idt162",widgetVar:"widget_formSmash_upper_j_idt162",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:upper:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt165_j_idt167",{id:"formSmash:upper:j_idt165:j_idt167",widgetVar:"widget_formSmash_upper_j_idt165_j_idt167",target:"formSmash:upper:j_idt165:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and MorePrimeFaces.cw("AccordionPanel","widget_formSmash_some",{id:"formSmash:some",widgetVar:"widget_formSmash_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_all",{id:"formSmash:all",widgetVar:"widget_formSmash_all",multiple:true}); PrimeFaces.cw("SelectBooleanButton","widget_formSmash_j_idt277",{id:"formSmash:j_idt277",widgetVar:"widget_formSmash_j_idt277",onLabel:"Hide others and affiliations",offLabel:"Show others and affiliations"});
function selectAll()
{
var panelSome = $(PrimeFaces.escapeClientId("formSmash:some"));
var panelAll = $(PrimeFaces.escapeClientId("formSmash:all"));
panelAll.toggle();
toggleList(panelSome.get(0).childNodes, panelAll);
toggleList(panelAll.get(0).childNodes, panelAll);
}
/*Toggling the list of authorPanel nodes according to the toggling of the closeable second panel */
function toggleList(childList, panel)
{
var panelWasOpen = (panel.get(0).style.display == 'none');
// console.log('panel was open ' + panelWasOpen);
for (var c = 0; c < childList.length; c++) {
if (childList[c].classList.contains('authorPanel')) {
clickNode(panelWasOpen, childList[c]);
}
}
}
/*nodes have styleClass ui-corner-top if they are expanded and ui-corner-all if they are collapsed */
function clickNode(collapse, child)
{
if (collapse && child.classList.contains('ui-corner-top')) {
// console.log('collapse');
child.click();
}
if (!collapse && child.classList.contains('ui-corner-all')) {
// console.log('expand');
child.click();
}
}
2017 (English)In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, 2017, Vol. 2017, p. 743-754Conference paper, Published paper (Refereed)
##### Abstract [en]

##### Place, publisher, year, edition, pages

IEEE Computer Society, 2017. Vol. 2017, p. 743-754
##### Series

Annual IEEE Symposium on Foundations of Computer Science, ISSN 0272-5428
##### Keywords [en]

Fixed Parameter Tractability, Hardness of Approximation, Clique, Set Cover, Dominating Set
##### National Category

Discrete Mathematics Signal Processing
##### Identifiers

URN: urn:nbn:se:kth:diva-220660DOI: 10.1109/FOCS.2017.74ISI: 000417425300065Scopus ID: 2-s2.0-85041136063ISBN: 978-1-5386-3464-6 OAI: oai:DiVA.org:kth-220660DiVA, id: diva2:1172101
##### Conference

58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017, DoubleTree Hotel at the Berkeley Marina, Berkeley, United States, 15 October 2017 through 17 October 2017
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt608",{id:"formSmash:j_idt608",widgetVar:"widget_formSmash_j_idt608",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt621",{id:"formSmash:j_idt621",widgetVar:"widget_formSmash_j_idt621",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt636",{id:"formSmash:j_idt636",widgetVar:"widget_formSmash_j_idt636",multiple:true});
##### Note

We consider questions that arise from the intersection between the areas of approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable algorithms. The questions, which have been asked several times (e.g., [1], [2], [3]) are whether there is a non-trivial FPT-approximation algorithm for the Maximum Clique (Clique) and Minimum Dominating Set (DomSet) problems parameterized by the size of the optimal solution. In particular, letting OPT be the optimum and N be the size of the input, is there an algorithm that runs in t(OPT) poly(N) time and outputs a solution of size f(OPT), for any functions t and f that are independent of N (for Clique, we want f(OPT) = omega(1))? In this paper, we show that both Clique and DomSet admit no non-trivial FPT-approximation algorithm, i.e., there is no o(OPT)-FPT-approximation algorithm for Clique and no f(OPT)-FPT-approximation algorithm for DomSet, for any function f (e.g., this holds even if f is an exponential or the Ackermann function). In fact, our results imply something even stronger: The best way to solve Clique and DomSet, even approximately, is to essentially enumerate all possibilities. Our results hold under the Gap Exponential Time Hypothesis (Gap-ETH) [4], [5], which states that no 2(o(n))-time algorithm can distinguish between a satisfiable 3SAT formula and one which is not even (1 - epsilon)-satisfiable for some constant epsilon > 0. Besides Clique and DomSet, we also rule out non-trivial FPT-approximation for Maximum Balanced Biclique, the problem of finding maximum subgraphs with hereditary properties (e.g., Maximum Induced Planar Subgraph), and Maximum Induced Matching in bipartite graphs. Previously only exact versions of these problems were known to be W[1]-hard [6], [7], [8]. Additionally, we rule out k(o(1))-FPT-approximation algorithm for Densest k-Subgraph although this ratio does not yet match the trivial O(k)-approximation algorithm. To the best of our knowledge, prior results only rule out constant factor approximation for Clique [9], [10] and log(1/4+epsilon) (OPT) approximation for DomSet for any constant epsilon > 0 [11]. Our result on Clique significantly improves on [9], [10]. However, our result on DomSet is incomparable to [11] since their results hold under ETH while our results hold under Gap-ETH, which is a stronger assumption.

QC 20180109

Available from: 2018-01-09 Created: 2018-01-09 Last updated: 2018-02-06Bibliographically approved
doi
isbn
urn-nbn$(function(){PrimeFaces.cw("Tooltip","widget_formSmash_j_idt1565",{id:"formSmash:j_idt1565",widgetVar:"widget_formSmash_j_idt1565",showEffect:"fade",hideEffect:"fade",showDelay:500,hideDelay:300,target:"formSmash:altmetricDiv"});});

CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_lower_j_idt1618",{id:"formSmash:lower:j_idt1618",widgetVar:"widget_formSmash_lower_j_idt1618",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:lower:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_lower_j_idt1619_j_idt1621",{id:"formSmash:lower:j_idt1619:j_idt1621",widgetVar:"widget_formSmash_lower_j_idt1619_j_idt1621",target:"formSmash:lower:j_idt1619:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});