High-Multiplicity Fair Allocation: Lenstra Empowered by N-fold Integer Programming

Autoři
Knop, D.; Bredereck, R.; Kaczmarczyk, A.; Niedermeier, R.
Rok
2019
Publikováno
EC '19 Proceedings of the 2019 ACM Conference on Economics and Computation. New York: ACM, 2019. p. 505-523. ISBN 9781450367929.
Typ
Stať ve sborníku
Anotace
We study the (parameterized) computational complexity of problems in the context of fair allocations of indivisible goods. More specifically, we show fixed-parameter tractability results for a broad set of problems concerned with envy-free, Pareto-efficient allocations of items (with agent-specific utility functions) to agents. In principle, this implies efficient exact algorithms for these in general computationally intractable problems whenever we face instances with few agents and low maximum (absolute) utility values. This holds true also in high-multiplicity settings where we may have high numbers of identical items. On the technical side, our approach provides algorithmic meta-theorems covering a rich set of fair allocation problems in the additive preferences model. To achieve this, our main technical contribution is to make an elaborate use of tools from integer linear programming. More specifically, we exploit results originally going back to a famous theorem of Lenstra [Math. Oper. Res. 1983] concerning (the fixed-parameter tractability of) Integer Linear Programs (ILPs) with bounded dimension (that is, the dimension shall be considered as a (small) parameter) and the more recent framework of (combinatorial) N-fold ILPs. We reveal and exploit a fruitful interaction between these two cornerstones in the theory of integer linear programming, which may be of independent interest in applications going beyond fair allocations.

On Induced Online Ramsey Number of Paths, Cycles, and Trees

Autoři
Blažej, V.; Valla, T.; Dvořák, P.
Rok
2019
Publikováno
The 14th International Computer Science Symposium in Russia. Springer, Cham, 2019. p. 60-69. Lecture Notes in Computer Science. vol. 11532. ISSN 0302-9743. ISBN 978-3-030-19954-8.
Typ
Stať ve sborníku
Anotace
An online Ramsey game is a game between Builder and Painter, alternating in turns. They are given a fixed graph $H$ and a an infinite set of independent vertices $G$. In each round Builder draws a new edge in $G$ and Painter colors it either red or blue. Builder wins if after some finite round there is a monochromatic copy of the graph $H$, otherwise Painter wins. The online Ramsey number $\widetilde{r}(H)$ is the minimum number of rounds such that Builder can force a monochromatic copy of $H$ in $G$. This is an analogy to the size-Ramsey number $\overline{r}(H)$ defined as the minimum number such that there exists graph $G$ with $\overline{r}(H)$ edges where for any edge two-coloring $G$ contains a monochromatic copy of $H$. In this extended abstract, we introduce the concept of induced online Ramsey numbers: the induced online Ramsey number $\overline{r}_{ind}(H)$ is the minimum number of rounds Builder can force an induced monochromatic copy of $H$ in $G$. We prove asymptotically tight bounds on the induced online Ramsey numbers of paths, cycles and two families of trees. Moreover, we provide a result analogous to Conlon [On-line Ramsey Numbers, SIAM J. Discr. Math. 2009], showing that there is an infinite family of trees $T_1,T_2,\dots$, $|T_i|<|T_{i+1}|$ for $i\ge1$, such that \[ \lim_{i\to\infty} \frac{\widetilde{r}(T_i)}{\overline{r}(T_i)} = 0. \]

On the m-eternal Domination Number of Cactus Graphs

Rok
2019
Publikováno
Reachability Problems. Springer, Cham, 2019. p. 33-47. ISSN 0302-9743. ISBN 978-3-030-30805-6.
Typ
Stať ve sborníku
Anotace
Given a graph $G$, guards are placed on vertices of $G$. Then vertices are subject to an infinite sequence of attacks so that each attack must be defended by a guard moving from a neighboring vertex. The m-eternal domination number is the minimum number of guards such that the graph can be defended indefinitely. In this paper we study the m-eternal domination number of cactus graphs, that is, connected graphs where each edge lies in at most two cycles, and we consider three variants of the m-eternal domination number: first variant allows multiple guards to occupy a single vertex, second variant does not allow it, and in the third variant additional ``eviction'' attacks must be defended. We provide a new upper bound for the m-eternal domination number of cactus graphs, and for a subclass of cactus graphs called Christmas cactus graphs, where each vertex lies in at most two cycles, we prove that these three numbers are equal. Moreover, we present a linear-time algorithm for computing them.

Kernelization of graph hamiltonicity: Proper H-graphs

Autoři
Knop, D.; Chaplick, S.; Fomin, F.V.; Golovach, P.A.; Zeman, P.
Rok
2019
Publikováno
16th International Symposium on Algorithms and Data Structures (WADS 2019). Cham: Springer, 2019. p. 296-310. vol. 11646. ISSN 0302-9743. ISBN 978-3-030-24765-2.
Typ
Stať ve sborníku
Anotace
We obtain new polynomial kernels and compression algorithms for Path Cover and Cycle Cover, the well-known generalizations of the classical Hamiltonian Path and Hamiltonian Cycle problems. Our choice of parameterization is strongly influenced by the work of Biró, Hujter, and Tuza, who in 1992 introduced H-graphs, intersection graphs of connected subgraphs of a subdivision of a fixed (multi) graph H. In this work, we turn to proper H-graphs, where the containment relationship between the representations of the vertices is forbidden. As the treewidth of a graph measures how similar the graph is to a tree, the size of graph H is the parameter measuring the closeness of the graph to a proper interval graph. We prove the following results. Path Cover admits a kernel of size O(formula presented), that is, we design an algorithm that for an n-vertex graph G and an integer k≥ 1, in time polynomial in n and (formula presented), outputs a graph G′ of size (formula presented) and k′≤ | V(G′) | such that the vertex set of G is coverable by k vertex-disjoint paths if and only if the vertex set of G′ is coverable by k′ vertex-disjoint paths.Cycle Cover admits a compression of size (formula presented) into another problem, called Prize Collecting Cycle Cover, that is, we design an algorithm that, in time polynomial in n and (formula presented), outputs an equivalent instance of Prize Collecting Cycle Cover of size (formula presented). In all our algorithms we assume that a proper H-decomposition is given as a part of the input.

A Tight Lower Bound for Planar Steiner Orientation

Autoři
Suchý, O.; Chitnis, R.; Feldmann, A.
Rok
2019
Publikováno
Algorithmica. 2019, 81(8), 3200-3216. ISSN 0178-4617.
Typ
Článek
Anotace
In the Steiner Orientation problem, the input is a mixed graph G (it has both directed and undirected edges) and a set of k terminal pairs T. The question is whether we can orient the undirected edges in a way such that there is a directed s?t path for each terminal pair (s,t)T. Arkin and Hassin [DAM'02] showed that the Steiner Orientation problem is NP-complete. They also gave a polynomial time algorithm for the special case when k=2. From the viewpoint of exact algorithms, Cygan et al.[ESA'12, SIDMA'13] designed an XP algorithm running in nO(k) time for all k1. Pilipczuk and Wahlstrom [SODA'16, TOCT'18] showed that the Steiner Orientation problem is W[1]-hard parameterized by k. As a byproduct of their reduction, they were able to show that under the Exponential Time Hypothesis (ETH) of Impagliazzo, Paturi and Zane [JCSS'01] the Steiner Orientation problem does not admit an f(k)no(k/logk) algorithm for any computable functionf. In this paper, we give a short and easy proof that the nO(k) algorithm of Cygan etal. is asymptotically optimal, even if the input graph is planar. Formally, we show that the Planar Steiner Orientation problem is W[1]-hard parameterized by the number k of terminal pairs, and, under ETH, cannot be solved in f(k)no(k) time for any computable function f. Moreover, under a stronger hypothesis called Gap-ETH of Dinur [ECCC'16] and Manurangsi and Raghavendra [ICALP'17], we are able to show that there is no constant ?>0 such that Planar Steiner Orientation admits an -approximation in FPT time, i.e., no f(k)no(k) time algorithm can distinguish between the case when all k pairs are satisfiable versus the case when less than k pairs are satisfiable. To the best of our knowledge, this is the first FPT inapproximability result on planar graphs.

Faster FPT algorithm for 5-path vertex cover

Rok
2019
Publikováno
44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Wadern: Schloss Dagstuhl - Leibniz Center for Informatics, 2019. p. 32:1-32:13. Leibniz International Proceedings in Informatics (LIPIcs). vol. 138. ISSN 1868-8969. ISBN 978-3-95977-117-7.
Typ
Stať ve sborníku
Anotace
The problem of \textsc{$d$-Path Vertex Cover, $d$-PVC} lies in determining a subset~$F$ of vertices of a~given graph $G=(V,E)$ such that $G \setminus F$ does not contain a~path on $d$ vertices. The paths we aim to cover need not to be induced. It is known that the \textsc{$d$-PVC} problem is NP-complete for any $d \ge 2$. When parameterized by the size of the solution $k$, \textsc{5-PVC} has direct trivial algorithm with $\mathcal{O}(5^kn^{\mathcal{O}(1)})$ running time and, since \textsc{$d$-PVC} is a special case of \textsc{$d$-Hitting Set}, an algorithm running in $\mathcal{O}(4.0755^kn^{\mathcal{O}(1)})$ time is known. In this paper we present an iterative compression algorithm that solves the \textsc{5-PVC} problem in $\mathcal{O}(4^kn^{\mathcal{O}(1)})$ time.

Solving Integer Quadratic Programming via Explicit and Structural Restrictions

Autoři
Knop, D.; Eiben, E.; Ganian, R.; Ordyniak, S.
Rok
2019
Publikováno
Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence. Menlo Park, California: AAAI Press, 2019. p. 1477-1484. ISSN 2159-5399. ISBN 978-1-57735-809-1.
Typ
Stať ve sborníku
Anotace
We study the parameterized complexity of Integer Quadratic Programming under two kinds of restrictions: explicit restrictions on the domain or coefficients, and structural restrictions on variable interactions. We argue that both kinds of restrictions are necessary to achieve tractability for Integer Quadratic Programming, and obtain four new algorithms for the problem that are tuned to possible explicit restrictions of instances that we may wish to solve. The presented algorithms are exact, deterministic, and complemented by appropriate lower bounds.

Integer Programming and Incidence Treedepth

Autoři
Knop, D.; Eiben, E.; Ganian, R.; Ordyniak, S.; Pilipczuk, Mi.; Wrochna, M.
Rok
2019
Publikováno
Integer Programming and Combinatorial Optimization. Basel: Springer, 2019. p. 194-204. ISSN 0302-9743. ISBN 978-3-030-17952-6.
Typ
Stať ve sborníku
Anotace
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ý, 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. We prove that deciding the feasibility of a system in the standard form, 𝐴𝐱=𝐛,𝐥≤𝐱≤𝐮, is 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 𝖯=𝖭𝖯.

Complexity of the Steiner Network Problem with Respect to the Number of Terminals

Autoři
Knop, D.; Suchý, O.; Eiben, E.; Panolan, F.
Rok
2019
Publikováno
36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany. Wadern: Schloss Dagstuhl - Leibniz Center for Informatics, 2019. p. 25:1-25:17. LIPIcs. vol. 126. ISSN 1868-8969. ISBN 978-3-95977-100-9.
Typ
Stať ve sborníku
Anotace
In the Directed Steiner Network problem we are given an arc-weighted digraph G, a set of terminals $T\subseteq V(G)$ with |T|=q, and an (unweighted) directed request graph R with V(R)=T. Our task is to output a subgraph $H \subseteq G$ of the minimum cost such that there is a directed path from s to t in H for all st \in A(R). It is known that the problem can be solved in time $|V(G)|^{O(|A(R)|)}$ [Feldman\&Ruhl, SIAM J. Comput. 2006] and cannot be solved in time $|V(G)|^{o(|A(R)|)}$ even if G is planar, unless the Exponential-Time Hypothesis (ETH) fails [Chitnis et al., SODA 2014]. However, the reduction (and other reductions showing hardness of the problem) only shows that the problem cannot be solved in time $|V(G)|^{o(q)}$, unless ETH fails. Therefore, there is a significant gap in the complexity with respect to q in the exponent. We show that \textsc{Directed Steiner Network} is solvable in time $f(q)\cdot |V(G)|^{O(c_g \cdot q)}$, where $c_g$ is a constant depending solely on the genus of G and f is a computable function. We complement this result by showing that there is no $f(q)\cdot |V(G)|^{o(q^2/ \log q)}$ algorithm for any function f for the problem on general graphs, unless ETH fails.

Parameterized complexity of fair vertex evaluation problems

Autoři
Knop, D.; Masařík, T.; Toufar, T.
Rok
2019
Publikováno
44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Wadern: Schloss Dagstuhl - Leibniz Center for Informatics, 2019. p. 33:1-33:16. Leibniz International Proceedings in Informatics (LIPIcs). vol. 138. ISSN 1868-8969. ISBN 978-3-95977-117-7.
Typ
Stať ve sborníku
Anotace
A prototypical graph problem is centered around a graph-theoretic property for a set of vertices and a solution to it is a set of vertices for which the desired property holds. The task is to decide whether, in the given graph, there exists a solution of a certain quality, where we use size as a quality measure. In this work, we are changing the measure to the fair measure (cf. Lin and Sahni [27]). The fair measure of a set of vertices S is (at most) k if the number of neighbors in the set S of any vertex (in the input graph) does not exceed k. One possible way to study graph problems is by defining the property in a certain logic. For a given objective, an evaluation problem is to find a set (of vertices) that simultaneously minimizes the assumed measure and satisfies an appropriate formula. More formally, we study the MSO Fair Vertex Evaluation, where the graph-theoretic property is described by an MSO formula. In the presented paper we show that there is an FPT algorithm for the MSO Fair Vertex Evaluation problem for formulas with one free variable parameterized by the twin cover number of the input graph and the size of the formula. One may define an extended variant of MSO Fair Vertex Evaluation for formulas with ℓ free variables; here we measure a maximum number of neighbors in each of the ℓ sets. However, such variant is W[1]-hard for parameter ℓ even on graphs with twin cover one. Furthermore, we study the Fair Vertex Cover (Fair VC) problem. Fair VC is among the simplest problems with respect to the demanded property (i.e., the rest forms an edgeless graph). On the negative side, Fair VC is W[1]-hard when parameterized by both treedepth and feedback vertex set of the input graph. On the positive side, we provide an FPT algorithm for the parameter modular width.

Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints

Autoři
Knop, D.; Pilipczuk, M.; Wrochna, M.
Rok
2019
Publikováno
36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany. Wadern: Schloss Dagstuhl - Leibniz Center for Informatics, 2019. p. 44:1-44:15. LIPIcs. vol. 126. ISSN 1868-8969. ISBN 978-3-95977-100-9.
Typ
Stať ve sborníku
Anotace
We consider the standard ILP FEASIBILITY problem: given an integer linear program of the form {Ax = b, x 0}, where A is an integer matrix with k rows and Ji columns, x is a vector of Ji variables, and b is a vector of k integers, we ask whether there exists x E Ilk that satisfies Ax = b. Each row of A specifies one linear constraint on x; our goal is to study the complexity of ILP FEASIBILITY when both k, the number of constraints, and MAILD.0, the largest absolute value of an entry in A, are small. Papadimitriou [29] was the first to give a fixed-parameter algorithm for ILP FEASIBILITY under parameterization by the number of constraints that runs in time ((MAIL, +1113110.0) " k) lk2). This was very recently improved by Eisenbrand and Weismantel [9], who used the Steinitz lemma to design an algorithm with running time (142410.) (k) "11b112, which was subsequently improved by Jansen and Rohwedder [17] to 0(14241o)k " log MbIfx,. We prove that for {0, 1}-matrices A, the running time of the algorithm of Eisenbrand and Weismantel is probably optimal: an algorithm with running time 2 (k log k) " 14 0Y(k) would contradict the Exponential Time Hypothesis (ETH). This improves previous non-tight lower bounds of Fomin et al. [10]. We then consider integer linear programs that may have many constraints, but they need to be structured in a "shallow" way. Precisely, we consider the parameter dual treedepth of the matrix A, denoted tdD (A), which is the treedepth of the graph over the rows of A, where two rows are adjacent if in some column they simultaneously contain a non-zero entry. It was recently shown by KouteckST 0 (td (A)) et al. [24] that ILP FEASIBILITY can be solved in time 112,1112 D (k loglIblfx,)(9(1). We present a streamlined proof of this fact and prove that, again, this running time is probably optimal: even assuming that all entries of A and b are in {-1, 0, 1}, the existence of an algorithm with running time 2' tdp (A)) " (k + f)(9(1) would contradict the ETH.

Efficient Implementation of Color Coding Algorithm for Subgraph Isomorphism Problem

Rok
2019
Publikováno
Analysis of Experimental Algorithms. Basel: Springer Nature Switzerland AG, 2019. p. 283-299. Lecture Notes in Computer Science. vol. 11544. ISSN 0302-9743. ISBN 978-3-030-34028-5.
Typ
Stať ve sborníku
Anotace
We consider the subgraph isomorphism problem where, given two graphs G (source graph) and F (pattern graph), one is to decide whether there is a (not necessarily induced) subgraph of G isomorphic to F. While many practical heuristic algorithms have been developed for the problem, as pointed out by McCreesh et al. [JAIR 2018], for each of them there are rather small instances which they cannot cope. Therefore, developing an alternative approach that could possibly cope with these hard instances would be of interest. A seminal paper by Alon, Yuster and Zwick [J. ACM 1995] introduced the color coding approach to solve the problem, where the main part is a dynamic programming over color subsets and partial mappings. As with many exponential-time dynamic programming algorithms, the memory requirements constitute the main limiting factor for its usage. Because these requirements grow exponentially with the treewidth of the pattern graph, all existing implementations based on the color coding principle restrict themselves to specific pattern graphs, e.g., paths or trees. In contrast, we provide an efficient implementation of the algorithm significantly reducing its memory requirements so that it can be used for pattern graphs of larger treewidth. Moreover, our implementation not only decides the existence of an isomorphic subgraph, but it also enumerates all such subgraphs (or given number of them). We provide an extensive experimental comparison of our implementation to other available solvers for the problem.

Evaluating and Tuning n-fold Integer Programming

Autoři
Knop, D.; Altmanová, K.; Koutecký, M.
Rok
2019
Publikováno
Journal of Experimental Algorithmics. 2019, 24(1), 2.2:1-2.2:22. ISSN 1084-6654.
Typ
Článek
Anotace
In recent years, algorithmic breakthroughs in stringology, computational social choice, scheduling, and so on, were achieved by applying the theory of so-called n-fold integer programming. An n-fold integer program (IP) has a highly uniform block structured constraint matrix. Hemmecke, Onn, and Romanchuk [Math. Program., 2013] showed an algorithm with runtime ΔO(rst + r2s) n3, where Δ is the largest coefficient, r,s, and t are dimensions of blocks of the constraint matrix and n is the total dimension of the IP; thus, an algorithm efficient if the blocks are of small size and with small coefficients. The algorithm works by iteratively improving a feasible solution with augmenting steps, and n-fold IPs have the special property that augmenting steps are guaranteed to exist in a not-too-large neighborhood. However, this algorithm has never been implemented and evaluated. We have implemented the algorithm and learned the following along the way. The original algorithm is practically unusable, but we discover a series of improvements that make its evaluation possible. Crucially, we observe that a certain constant in the algorithm can be treated as a tuning parameter, which yields an efficient heuristic (essentially searching in a smaller-than-guaranteed neighborhood). Furthermore, the algorithm uses an overly expensive strategy to find a “best” step, while finding only an “approximately best” step is much cheaper, yet sufficient for quick convergence. Using this insight, we improve the asymptotic dependence on n from n3 to n2 log n.

The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs

Autoři
Suchý, O.; van Bevern, R.; Fluschnik, T.; Mertzios, G.B.; Molter, H.; Sorge, M.
Rok
2018
Publikováno
Discrete Optimization. 2018, 30 20-50. ISSN 1572-5286.
Typ
Článek
Anotace
This work studies the parameterized complexity of finding secluded solutions to classical combinatorial optimization problems on graphs such as finding minimum - separators, feedback vertex sets, dominating sets, maximum independent sets, and vertex Herein, one searches not only to minimize or maximize the size of the solution, but also to minimize the size of its neighborhood. This restriction has applications in secure routing and community detection.

Cluster Editing in Multi-Layer and Temporal Graphs

Autoři
Suchý, O.; Chen, J.; Molter, H.; Sorge, M.
Rok
2018
Publikováno
29th International Symposium on Algorithms and Computation (ISAAC 2018). Saarbrücken: Dagstuhl Publishing,, 2018. p. 24:1-24:13. Leibniz International Proceedings in Informatics (LIPIcs). vol. 123. ISSN 1868-8969. ISBN 978-3-95977-094-1.
Typ
Stať ve sborníku
Anotace
Motivated by the recent rapid growth of research for algorithms to cluster multi-layer and temporal graphs, we study extensions of the classical Cluster Editing problem. In Multi-Layer Cluster Editing we receive a set of graphs on the same vertex set, called layers and aim to transform all layers into cluster graphs (disjoint unions of cliques) that differ only slightly. More specifically, we want to mark at most d vertices and to transform each layer into a cluster graph using at most k edge additions or deletions per layer so that, if we remove the marked vertices, we obtain the same cluster graph in all layers. In Temporal Cluster Editing we receive a sequence of layers and we want to transform each layer into a cluster graph so that consecutive layers differ only slightly. That is, we want to transform each layer into a cluster graph with at most k edge additions or deletions and to mark a distinct set of d vertices in each layer so that each two consecutive layers are the same after removing the vertices marked in the first of the two layers. We study the combinatorial structure of the two problems via their parameterized complexity with respect to the parameters d and k, among others. Despite the similar definition, the two problems behave quite differently: In particular, Multi-Layer Cluster Editing is fixed-parameter tractable with running time k^{O(k + d)} s^{O(1)} for inputs of size s, whereas Temporal Cluster Editing is W[1]-hard with respect to k even if d = 3.

Target Set Selection in Dense Graph Classes

Autoři
Knop, D.; Dvořák, P.; Toufar, T.
Rok
2018
Publikováno
29th International Symposium on Algorithms and Computation (ISAAC 2018). Saarbrücken: Dagstuhl Publishing,, 2018. p. 18:1-18:13. Leibniz International Proceedings in Informatics (LIPIcs). vol. 123. ISSN 1868-8969. ISBN 978-3-95977-094-1.
Typ
Stať ve sborníku
Anotace
In this paper we study the Target Set Selection problem from a parameterized complexity perspective. Here for a given graph and a threshold for each vertex the task is to find a set of vertices (called a target set) to activate at the beginning which activates the whole graph during the following iterative process. A vertex outside the active set becomes active if the number of so far activated vertices in its neighborhood is at least its threshold. We give two parameterized algorithms for a special case where each vertex has the threshold set to the half of its neighbors (the so called Majority Target Set Selection problem) for parameterizations by the neighborhood diversity and the twin cover number of the input graph. We complement these results from the negative side. We give a hardness proof for the Majority Target Set Selection problem when parameterized by (a restriction of) the modular-width - a natural generalization of both previous structural parameters. We show that the Target Set Selection problem parameterized by the neighborhood diversity when there is no restriction on the thresholds is W[1]-hard.

Integer Programming in Parameterized Complexity: Three Miniatures

Autoři
Knop, D.; Gavenčiak, T.; Koutacký, M.
Rok
2019
Publikováno
13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2019. p. 21:1-21:16. vol. 115. ISSN 1868-8969. ISBN 978-3-95977-084-2.
Typ
Stať ve sborníku
Anotace
Powerful results from the theory of integer programming have recently led to substantial advances in parameterized complexity. However, our perception is that, except for Lenstra's algorithm for solving integer linear programming in fixed dimension, there is still little understanding in the parameterized complexity community of the strengths and limitations of the available tools. This is understandable: it is often difficult to infer exact runtimes or even the distinction between FPT and XP algorithms, and some knowledge is simply unwritten folklore in a different community. We wish to make a step in remedying this situation. To that end, we first provide an easy to navigate quick reference guide of integer programming algorithms from the perspective of parameterized complexity. Then, we show their applications in three case studies, obtaining FPT algorithms with runtime f(k) poly(n). We focus on: - Modeling: since the algorithmic results follow by applying existing algorithms to new models, we shift the focus from the complexity result to the modeling result, highlighting common patterns and tricks which are used. - Optimality program: after giving an FPT algorithm, we are interested in reducing the dependence on the parameter; we show which algorithms and tricks are often useful for speed-ups. - Minding the poly(n): reducing f(k) often has the unintended consequence of increasing poly(n); so we highlight the common trade-offs and show how to get the best of both worlds. Specifically, we consider graphs of bounded neighborhood diversity which are in a sense the simplest of dense graphs, and we show several FPT algorithms for Capacitated Dominating Set, Sum Coloring, and Max-q-Cut by modeling them as convex programs in fixed dimension, n-fold integer programs, bounded dual treewidth programs, and indefinite quadratic programs in fixed dimension.

Za obsah stránky zodpovídá: doc. Ing. Štěpán Starosta, Ph.D.