×

Parameterized extension complexity of independent set and related problems. (English) Zbl 1395.05125

Summary: Let \(G\) be a graph on \(n\) vertices and \(\mathrm{STAB}_k(G)\) be the convex hull of characteristic vectors of its independent sets of size at most \(k\). We study extension complexity of \(\mathrm{STAB}_k(G)\) with respect to a fixed parameter \(k\) (analogously to, e.g., parameterized computational complexity of problems). We show that for graphs \(G\) from a class of bounded expansion it holds that \(\mathrm{xc}(\mathrm{STAB}_k(G)) \leqslant \mathcal{O}(f(k) \cdot n)\) where the function \(f\) depends only on the class. This result can be extended in a simple way to a wide range of similarly defined graph polytopes. In case of general graphs we show that there is no function \(f\) such that, for all values of the parameter \(k\) and for all graphs on \(n\) vertices, the extension complexity of \(\mathrm{STAB}_k(G)\) is at most \(f(k) \cdot n^{\mathcal{O}(1)}\). While such results are not surprising since it is known that optimizing over \(\mathrm{STAB}_k(G)\) is \(FPT\) for graphs of bounded expansion and \(W [1]\)-hard in general, they are also not trivial and in both cases stronger than the corresponding computational complexity results.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] D. Avis, H.R. Tiwary, On the extension complexity of combinatorial polytopes, in: ICALP(1)’13, 2013, pp. 57-68.; D. Avis, H.R. Tiwary, On the extension complexity of combinatorial polytopes, in: ICALP(1)’13, 2013, pp. 57-68. · Zbl 1336.68112
[2] Balas, E., Disjunctive programming: properties of the convex hull of feasible points, Discrete Appl. Math., 89, 1-3, 3-44, (1998) · Zbl 0921.90118
[3] Bodlaender, H., A linear time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput., 25, 1305-1317, (1996) · Zbl 0864.68074
[4] Braun, G.; Fiorini, S.; Pokutta, S.; Steurer, D., Approximation limits of linear programs (beyond hierarchies), Math. Oper. Res., 40, 3, 756-772, (2015) · Zbl 1343.68308
[5] Buchanan, A., Extended formulations for vertex cover, Oper. Res. Lett., 44, 3, 374-378, (2016)
[6] A. Buchanan, S. Butenko, Tight extended formulations for independent set, 2014. Available on Optimization Online: http://www.optimization-online.org/DB_HTML/2014/09/4540.html; A. Buchanan, S. Butenko, Tight extended formulations for independent set, 2014. Available on Optimization Online: http://www.optimization-online.org/DB_HTML/2014/09/4540.html
[7] S.O. Chan, J.R. Lee, P. Raghavendra, D. Steurer, Approximate constraint satisfaction requires large LP relaxations, in: FOCS’13, 2013, pp. 350-359.; S.O. Chan, J.R. Lee, P. Raghavendra, D. Steurer, Approximate constraint satisfaction requires large LP relaxations, in: FOCS’13, 2013, pp. 350-359. · Zbl 1394.68170
[8] Conforti, M.; Cornuéjols, G.; Zambelli, G., Extended formulations in combinatorial optimization, 4OR-Q J. Oper. Res., 8, 1-48, (2010) · Zbl 1219.90193
[9] Downey, R. G.; Fellows, M. R., (Fundamentals of Parameterized Complexity, Texts in Computer Science, (2013), Springer) · Zbl 1358.68006
[10] Fiorini, S.; Massar, S.; Pokutta, S.; Tiwary, H. R.; de Wolf, R., Exponential lower bounds for polytopes in combinatorial optimization, J. ACM, 62, 2, 17, (2015) · Zbl 1333.90107
[11] Grohe, M.; Kreutzer, S., Methods for algorithmic meta theorems, (Model Theoretic Methods in Finite Combinatorics: AMS-ASL Special Session, January 5-8, 2009, Contemporary Mathematics, (2011), AMS), 181-206 · Zbl 1278.68099
[12] Grohe, M.; Kreutzer, S.; Siebertz, S., Deciding first-order properties of nowhere dense graphs, (STOC’14, (2014), ACM), 89-98 · Zbl 1315.05118
[13] Kaibel, V., Extended formulations in combinatorial optimization, Optima, 85, 2-7, (2011)
[14] P. Kolman, M. Koutecký, H.R. Tiwary, Extension complexity, MSO logic, and treewidth, in: SWAT’16, 2016, pp. 18:1-18:14.; P. Kolman, M. Koutecký, H.R. Tiwary, Extension complexity, MSO logic, and treewidth, in: SWAT’16, 2016, pp. 18:1-18:14.
[15] Nešetřil, J.; Ossona de Mendez, P., Linear time low tree-width partitions and algorithmic consequences, (STOC’06, (2006), ACM), 391-400 · Zbl 1301.05268
[16] Nešetřil, J.; Ossona de Mendez, P., Grad and classes with bounded expansion I. decompositions, European J. Combin., 29, 3, 760-776, (2008) · Zbl 1156.05056
[17] Nešetřil, J.; Ossona de Mendez, P., (Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, (2012), Springer) · Zbl 1268.05002
[18] Pokutta, S.; Van Vyve, M., A note on the extension complexity of the knapsack polytope, Oper. Res. Lett., 41, 4, 347-350, (2013) · Zbl 1286.90168
[19] T. Rothvoß, The matching polytope has exponential extension complexity, in: STOC ’14, 2014, pp. 263-272.; T. Rothvoß, The matching polytope has exponential extension complexity, in: STOC ’14, 2014, pp. 263-272. · Zbl 1315.90038
[20] Vanderbeck, F.; Wolsey, L. A., Reformulation and decomposition of integer programs, (Jünger, M.; etal., 50 Years of Integer Programming 1958-2008, (2010), Springer), 431-502 · Zbl 1187.90207
[21] Wolsey, L. A., Using extended formulations in practice, Optima, 85, 7-9, (2011)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.