Integer Programming and Incidence Treedepth
| Autor: | Sebastian Ordyniak, Michał Pilipczuk, Dušan Knop, Marcin Wrochna, Robert Ganian, Eduard Eiben |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Discrete mathematics
FOS: Computer and information sciences 050101 languages & linguistics Computational complexity theory 05 social sciences 02 engineering and technology Computational Complexity (cs.CC) Graph Computer Science - Computational Complexity Bounded function Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing 0501 psychology and cognitive sciences Data Structures and Algorithms (cs.DS) Constraint matrix Integer programming Mathematics |
| Zdroj: | Integer Programming and Combinatorial Optimization-20th International Conference, IPCO 2019, Ann Arbor, MI, USA, May 22-24, 2019, Proceedings Lecture Notes in Computer Science Lecture Notes in Computer Science-Integer Programming and Combinatorial Optimization Integer Programming and Combinatorial Optimization ISBN: 9783030179526 IPCO |
| ISSN: | 0302-9743 1611-3349 |
| Popis: | Recently a strong connection has been shown between the tractability of integer programming (IP) with bounded coefficients on the one side and the structure of its constraint matrix on the other side. To that end, integer linear programming is fixed-parameter tractable with respect to the primal (or dual) treedepth of the Gaifman graph of its constraint matrix and the largest coefficient (in absolute value). Motivated by this, Kouteck\'y, Levin, and Onn [ICALP 2018] asked whether it is possible to extend these result to a more broader class of integer linear programs. More formally, is integer linear programming fixed-parameter tractable with respect to the incidence treedepth of its constraint matrix and the largest coefficient (in absolute value)? We answer this question in negative. In particular, we prove that deciding the feasibility of a system in the standard form, ${A\mathbf{x} = \mathbf{b}}, {\mathbf{l} \le \mathbf{x} \le \mathbf{u}}$, is $\mathsf{NP}$-hard even when the absolute value of any coefficient in $A$ is 1 and the incidence treedepth of $A$ is 5. Consequently, it is not possible to decide feasibility in polynomial time even if both the assumed parameters are constant, unless $\mathsf{P}=\mathsf{NP}$. Moreover, we complement this intractability result by showing tractability for natural and only slightly more restrictive settings, namely: (1) treedepth with an additional bound on either the maximum arity of constraints or the maximum number of occurrences of variables and (2) the vertex cover number. Comment: 11 pages, 1 figure. This is an extended version of an article that appeared at IPCO 2019 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|