Kernelization of graph hamiltonicity: Proper H-graphs

Autoři
Chaplick, S.; Fomin, F.V.; Golovach, P.A.; Knop, D.; Zeman, P.
Rok
2021
Publikováno
SIAM Journal on Discrete Mathematics. 2021, 35(2), 840-892. ISSN 0895-4801.
Typ
Článek
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(||H||^8), where ||H|| is the size of graph H. In other words, we design an algorithm that for an n-vertex graph G and integer k >= 1, in time polynomial in n and ||H||, outputs a graph G' of size O(||H||^8) 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. Hamiltonian Cycle admits a kernel of size O(||H||^8). Cycle Cover admits a polynomial kernel. We prove it by providing a compression of size O(||H||^10) into another NP-complete problem, namely, Prize Collecting Cycle Cover, that is, we design an algorithm that, in time polynomial in n and ||H||, outputs an equivalent instance of Prize Collecting Cycle Cover of size O(||H||^10). In all our algorithms we assume that a proper H-decomposition is given as a part of the input.

High-Multiplicity Fair Allocation Made More Practical

Autoři
Bredereck, R.; Figiel, A.; Kaczmarczyk, A.; Knop, D.; Niedermeier, R.
Rok
2021
Publikováno
AAMAS '21: 20th International Conference on Autonomous Agents and Multiagent Systems, Virtual Event, United Kingdom, May 3-7, 2021. New York: ACM, 2021. p. 260-268. ISSN 1548-8403. ISBN 978-1-7138-3262-1.
Typ
Stať ve sborníku
Anotace
The envy-free, Pareto-efficient allocation of indivisible goods leads to computationally hard problems. There is a big variety of modeling issues, such as agent-specific utility functions or (high numbers of) different types of goods. In recent work, Bredereck et al. [ACM EC~2019] addressed this topic by showing (theoretical) fixed-parameter tractability results for "high-multiplicity fair allocation", exploiting parameters such as the number of agents or maximum absolute utility values. To this end, they used a number of tools from (theoretical) integer linear programming. We "engineer" their work towards practical usefulness, thereby being able to solve all real-world instances from the state-of-art online platform "spliddit.org for provably fair solutions". Besides providing the foundations for a fast tool for fair allocations, we also offer a flexible framework with the possibility to relax fairness or efficiency demands so to, e.g., allow tradeoffs between fairness and social welfare. Moreover, our framework provides ways to interpret and explain "solution paths" which makes it possible to perform further explorations in cases when no envy-free and efficient allocations exist.

Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices

Autoři
Dvorak, P.; Feldmann, Andreas E.; Knop, D.; Masarik, T.; Toufar, T.; Veselý, P.
Rok
2021
Publikováno
SIAM Journal on Discrete Mathematics. 2021, 35(1), 546-574. ISSN 0895-4801.
Typ
Článek
Anotace
We study the Steiner Tree problem, in which a set of terminal vertices needs to be connected in the cheapest possible way in an edge-weighted graph. This problem has been extensively studied from the viewpoint of approximation and also parameterization. In particular, on one hand Steiner Tree is known to be APX-hard, and W[2]-hard on the other, if parameterized by the number of nonterminals (Steiner vertices) in the optimum solution. In contrast to this, we give an efficient parameterized approximation scheme (EPAS), which circumvents both hardness results. Moreover, our methods imply the existence of a polynomial size approximate kernelization scheme (PSAKS) for the considered parameter. We further study the parameterized approximability of other variants of Steiner Tree, such as Directed Steiner Tree and Steiner Forest. For none of these is an EPAS likely to exist for the studied parameter. For Steiner Forest an easy observation shows that the problem is APX-hard, even if the input graph contains no Steiner vertices. For Directed Steiner Tree we prove that approximating within any function of the studied parameter is W[1]-hard. Nevertheless, we show that an EPAS exists for Unweighted Directed Steiner Tree, but a PSAKS does not. We also prove that there is an EPAS and a PSAKS for Steiner Forest if in addition to the number of Steiner vertices, the number of connected components of an optimal solution is considered to be a parameter.

Local linear set on graphs with bounded twin cover number

Autoři
Rok
2021
Publikováno
Information Processing Letters. 2021, 170 ISSN 1872-6119.
Typ
Článek
Anotace
Inspired by recent results for the so-called fair and local linear problems, we define two problems, LOCAL LINEAR SET and LOCAL LINEAR VERTEX COVER. Here the task is to find a set of vertices X subset of V (which is a vertex cover) of the input graph (V, E) such that the local linear constraints l(v) <= vertical bar X boolean AND N(v)vertical bar <= u(v) hold for all v is an element of V; here, l(v) and u( v) are on the input. We prove that both problems are in FPT for the parameter twin cover number (using integer linear programming).

Graph isomorphism restricted by lists

Autoři
Klavík, P.; Knop, D.; Zeman, P.
Rok
2021
Publikováno
Theoretical Computer Science. 2021, 860 51-71. ISSN 0304-3975.
Typ
Článek
Anotace
The complexity of graph isomorphism (GRAPHISO) is a famous problem in computer science. For graphs G and H, it asks whether they are the same up to a relabeling of vertices. In 1981, Lubiw proved that list restricted graph isomorphism (LISTISO ) is NP -complete: for each u∈V(G), we are given a list L(u)⊆V(H) of possible images of u. After 35 years, we revive the study of this problem and consider which results for GRAPHISO can be modified to solve LISTISO. We prove: 1) Under certain conditions, GI -completeness of a class of graphs implies NP -completeness of LISTISO. 2) Several combinatorial algorithms for GRAPHISO can be modified to solve LISTISO: for trees, planar graphs, interval graphs, circle graphs, permutation graphs, and bounded treewidth graphs. 3) LISTISO is NP -complete for cubic colored graphs with sizes of color classes bounded by 8 with all lists of size at most 3.

Automorphisms of the cube n^d

Autoři
Dvořák, P.; Valla, T.
Rok
2021
Publikováno
Discrete Mathematics. 2021, 2021(344(3)), ISSN 0012-365X.
Typ
Článek
Anotace
Consider a hypergraph n^d where the vertices are points of the d-dimensional cube [n]^d and the edges are all sets of n points such that they are in one line. We study the structure of the group of automorphisms of n^d, i.e., permutations of points of [n]^d preserving the edges. In this paper we provide a complete characterization. Moreover, we consider the Colored Cube Isomorphism problem of deciding whether for two colorings of the vertices of n^d there exists an automorphism of n^d preserving the colors. We show that this problem is GI-complete.

On the Intersections of Non-homotopic Loops

Autoři
Blažej, V.; Opler, M.; Šileikis, M.; Valtr, P.
Rok
2021
Publikováno
Algorithms and Discrete Applied Mathematics. Cham: Springer, 2021. p. 196-205. Lecture Notes in Computer Science. vol. 12601. ISSN 0302-9743. ISBN 978-3-030-67898-2.
Typ
Stať ve sborníku
Anotace
Let $V = \{v_1, \dots, v_n\}$ be a set of $n$ points in the plane and let $x \in V$. An \emph{$x$-loop} is a continuous closed curve not containing any point of $V$, except of passing exactly once through the point $x$. We say that two $x$-loops are \emph{non-homotopic} if they cannot be transformed continuously into each other without passing through a point of $V$. For $n=2$, we give an upper bound $2^{O(k)}$ on the maximum size of a family of pairwise non-homotopic $x$-loops such that every loop has fewer than $k$ self-intersections and any two loops have fewer than $k$ intersections. This result is inspired by a very recent result of Pach, Tardos, and T\'oth who proved the upper bounds $2^{16k^4}$ for the slightly different scenario when $x\not\in V$.

On the Edge-Length Ratio of 2-Trees

Autoři
Blažej, V.; Fiala, J.; Liotta, G.
Rok
2021
Publikováno
Graph Drawing and Network Visualization. Cham: Springer, 2021. p. 85-98. Lecture Notes in Computer Science. vol. 12590. ISSN 0302-9743. ISBN 978-3-030-68765-6.
Typ
Stať ve sborníku
Anotace
We study planar straight-line drawings of graphs that minimize the ratio between the length of the longest and the shortest edge. We answer a question of Lazard et al. [Theor. Comput. Sci. {\bf 770} (2019), 88--94] and, for any given constant $r$, we provide a $2$-tree which does not admit a planar straight-line drawing with a ratio bounded by $r$. When the ratio is restricted to adjacent edges only, we prove that any $2$-tree admits a planar straight-line drawing whose edge-length ratio is at most $4 + \varepsilon$ for any arbitrarily small $\varepsilon > 0$, hence the upper bound on the local edge-length ratio of partial $2$-trees is $4$.

Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View

Autoři
Hušek, R.; Knop, D.; Masařík, T.
Rok
2020
Publikováno
15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2020. p. 16:1-16:18. ISSN 1868-8969. ISBN 978-3-95977-172-6.
Typ
Stať ve sborníku
Anotace
In the Steiner Tree problem, we are given an edge-weighted undirected graph G = (V,E) and a set of terminals R ⊆ V. The task is to find a connected subgraph of G containing R and minimizing the sum of weights of its edges. Steiner Tree is well known to be NP-complete and is undoubtedly one of the most studied problems in (applied) computer science. We observe that many approximation algorithms for Steiner Tree follow a similar scheme (meta-algorithm) and perform (exhaustively) a similar routine which we call star contraction. Here, by a star contraction, we mean finding a star-like subgraph in (the metric closure of) the input graph minimizing the ratio of its weight to the number of contained terminals minus one; and contract. It is not hard to see that the well-known MST-approximation seeks the best star to contract among those containing two terminals only. Zelikovsky’s approximation algorithm follows a similar workflow, finding the best star among those containing three terminals. We perform an empirical study of star contractions with the relaxed condition on the number of terminals in each star contraction motivated by a recent result of Dvořák et al. [Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices, STACS 2018]. Furthermore, we propose two improvements of Zelikovsky’s 11/6-approximation algorithm and we empirically confirm that the quality of the solution returned by any of these is better than the one returned by the former algorithm. However, such an improvement is exchanged for a slower running time (up to a multiplicative factor of the number of terminals).

Recognizing Proper Tree-Graphs

Autoři
Chaplick, S.; Golovach, P.A.; Hartmann, T.A.; Knop, D.
Rok
2020
Publikováno
15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2020. p. 8:1-8:15. ISSN 1868-8969. ISBN 978-3-95977-172-6.
Typ
Stať ve sborníku
Anotace
We investigate the parameterized complexity of the recognition problem for the proper H-graphs. The H-graphs are the intersection graphs of connected subgraphs of a subdivision of a multigraph H, and the properness means that the containment relationship between the representations of the vertices is forbidden. The class of H-graphs was introduced as a natural (parameterized) generalization of interval and circular-arc graphs by Biró, Hujter, and Tuza in 1992, and the proper H-graphs were introduced by Chaplick et al. in WADS 2019 as a generalization of proper interval and circular-arc graphs. For these graph classes, H may be seen as a structural parameter reflecting the distance of a graph to a (proper) interval graph, and as such gained attention as a structural parameter in the design of efficient algorithms. We show the following results. - For a tree T with t nodes, it can be decided in 2^{𝒪(t² log t)} ⋅ n³ time, whether an n-vertex graph G is a proper T-graph. For yes-instances, our algorithm outputs a proper T-representation. This proves that the recognition problem for proper H-graphs, where H required to be a tree, is fixed-parameter tractable when parameterized by the size of T. Previously only NP-completeness was known. - Contrasting to the first result, we prove that if H is not constrained to be a tree, then the recognition problem becomes much harder. Namely, we show that there is a multigraph H with 4 vertices and 5 edges such that it is NP-complete to decide whether G is a proper H-graph.

Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters

Autoři
Bentert, M.; Heeger, K.; Knop, D.
Rok
2020
Publikováno
31st International Symposium on Algorithms and Computation (ISAAC 2020). Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2020. p. 36:1-36:14. ISSN 1868-8969. ISBN 978-3-95977-173-3.
Typ
Stať ve sborníku
Anotace
In the presented paper, we study the Length-Bounded Cut problem for special graph classes as well as from a parameterized-complexity viewpoint. Here, we are given a graph G, two vertices s and t, and positive integers β and λ. The task is to find a set F of edges of size at most β such that every s-t-path of length at most λ in G contains some edge in F. Bazgan et al. [Networks, 2019] conjectured that Length-Bounded Cut admits a polynomial-time algorithm if the input graph G is a proper interval graph. We confirm this conjecture by providing a dynamic-programming based polynomial-time algorithm. Moreover, we strengthen the W[1]-hardness result of Dvořák and Knop [Algorithmica, 2018] for Length-Bounded Cut parameterized by pathwidth. Our reduction is shorter, and the target of the reduction has stronger structural properties. Consequently, we give W[1]-hardness for the combined parameter pathwidth and maximum degree of the input graph. Finally, we prove that Length-Bounded Cut is W[1]-hard for the feedback vertex number. Both our hardness results complement known XP algorithms.

Multidimensional Stable Roommates with Master List

Autoři
Bredereck, R.; Heeger, K.; Knop, D.; Niedermeier, R.
Rok
2020
Publikováno
Web and Internet Economics - 16th International Conference, WINE 2020, Beijing, China, December 7-11, 2020, Proceedings. Cham: Springer, 2020. p. 59-73. ISBN 978-3-030-64945-6.
Typ
Stať ve sborníku
Anotace
Since the early days of research in algorithms and complexity, the computation of stable matchings is a core topic. While in the classic setting the goal is to match up two agents (either from different “gender” (this is Stable Marriage) or “unrestricted” (this is Stable Roommates)), Knuth [1976] triggered the study of three- or multidimensional cases. Here, we focus on the study of Multidimensional Stable Roommates, known to be 𝖭𝖯 -hard since the early 1990’s. Many 𝖭𝖯 -hardness results, however, rely on very general input instances that do not occur in at least some of the specific application scenarios. With the quest for identifying islands of tractability, we look at the case of master lists. Here, as natural in applications where agents express their preferences based on “objective” scores, one roughly speaking assumes that all agent preferences are “derived from” a central master list, implying that the individual agent preferences shall be similar. Master lists have been frequently studied in the two-dimensional (classic) stable matching case, but seemingly almost never for the multidimensional case. This work, also relying on methods from parameterized algorithm design and complexity analysis, performs a first systematic study of Multidimensional Stable Roommates under the assumption of master lists.

Voting and Bribing in Single-Exponential Time

Autoři
Knop, D.; Koutecký, M.; Mnich, M.
Rok
2020
Publikováno
ACM TRANSACTIONS ON ECONOMICS AND COMPUTATION. 2020, 8(3), 12:1-12:28. ISSN 2167-8375.
Typ
Článek
Anotace
We introduce a general problem about bribery in voting systems. In the R-Multi-Bribery problem, the goal is to bribe a set of voters at minimum cost such that a desired candidate is a winner in the perturbed election under the voting rule R. Voters assign prices for withdrawing their vote, for swapping the positions of two consecutive candidates in their preference order, and for perturbing their approval count to favour candidates. As our main result, we show that R-Multi-Bribery is fixed-parameter tractable parameterized by the number of candidates |C| with only a single-exponential dependence on |C|, for many natural voting rules R, including all natural scoring protocols, maximin rule, Bucklin rule, Fallback rule, SP-AV, and any C1 rule. The vast majority of previous work done in the setting of few candidates proceeds by grouping voters into at most |C|! types by their preference, constructing an integer linear program with |C|!2 variables, and solving it by Lenstra's algorithm in time |C|!|C|!2, hence double-exponential in |C|. Note that it is not possible to encode a large number of different voter costs in this way and still obtain a fixed-parameter algorithm, as that would increase the number of voter types and hence the dimension. These two obstacles of double-exponential complexity and restricted costs have been formulated as "Challenges #1 and #2"of the "Nine Research Challenges in Computational Social Choice"by Bredereck et al. Hence, our result resolves the parameterized complexity of R-Swap-Bribery for the aforementioned voting rules plus Kemeny's rule, and for all rules except Kemeny brings the dependence on |C| down to single-exponential. The engine behind our progress is the use of a new integer linear programming formulation, using so-called "n-fold integer programming."Since its format is quite rigid, we introduce "extended n-fold IP,"which allows many useful modeling tricks. Then, we model R-Multi-Bribery as an extended n-fold IP and ...

Graph Isomorphism Restricted by Lists

Autoři
Klavík, P.; Knop, D.; Zeman, P.
Rok
2020
Publikováno
Graph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Leeds, UK, June 24-26, 2020, Revised Selected Papers. Berlin: Springer-Verlag, 2020. p. 106-118. Lecture Notes in Computer Science. vol. 12301. ISSN 0302-9743. ISBN 978-3-030-60439-4.
Typ
Stať ve sborníku
Anotace
The complexity of graph isomorphism (GraphIso) is a famous problem in computer science. For graphs G and H, it asks whether they are the same up to a relabeling of vertices. In 1981, Lubiw proved that list restricted graph isomorphism (ListIso) is NP-complete: for each u∈ V(G), we are given a list L(u) ⊆ V(H) of possible images of u. After 35 years, we revive the study of this problem and consider which results for GraphIso can be modified to solve ListIso. We prove: 1) Under certain conditions, GI-completeness of a class of graphs implies NP-completeness of ListIso. 2) Several combinatorial algorithms for GraphIso can be modified to solve ListIso: for trees, planar graphs, interval graphs, circle graphs, permutation graphs, and bounded treewidth graphs. 3) ListIso is NP-complete for cubic colored graphs with sizes of color classes bounded by 8.

Combinatorial n-fold integer programming and applications

Autoři
Knop, D.; Koutecký, M.; Mnich, M.
Rok
2020
Publikováno
Mathematical Programming. 2020, 2020(184), 1-34. ISSN 0025-5610.
Typ
Článek
Anotace
Many fundamental NP-hard problems can be formulated as integer linear programs (ILPs). A famous algorithm by Lenstra solves ILPs in time that is exponential only in the dimension of the program, and polynomial in the size of the ILP. That algorithm became a ubiquitous tool in the design of fixed-parameter algorithms for NP-hard problems, where one wishes to isolate the hardness of a problem by some parameter. However, in many cases using Lenstra’s algorithm has two drawbacks: First, the run time of the resulting algorithms is often double-exponential in the parameter, and second, an ILP formulation in small dimension cannot easily express problems involving many different costs. Inspired by the work of Hemmecke et al. (Math Program 137(1–2, Ser. A):325–341, 2013), we develop a single-exponential algorithm for so-called combinatorial n-fold integer programs, which are remarkably similar to prior ILP formulations for various problems, but unlike them, also allow variable dimension. We then apply our algorithm to many relevant problems like Closest String, Swap Bribery, Weighted Set Multicover, and several others, and obtain exponential speedups in the dependence on the respective parameters, the input size, or both. Unlike Lenstra’s algorithm, which is essentially a bounded search tree algorithm, our result uses the technique of augmenting steps. At its heart is a deep result stating that in combinatorial n-fold IPs, existence of an augmenting step implies existence of a “local” augmenting step, which can be found using dynamic programming. Our results provide an important insight into many problems by showing that they exhibit this phenomenon, and highlights the importance of augmentation techniques.

Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints

Autoři
Knop, D.; Pilipczuk, M.; Wrochna, M.
Rok
2020
Publikováno
ACM Transactions on Computation Theory. 2020, 12(3), 19:1-19:19. ISSN 1942-3454.
Typ
Článek
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 ℓ columns, x is a vector of ℓ variables, and b is a vector of k integers, we ask whether there exists x ∈ N ℓ 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 A∞, the largest absolute value of an entry in A, are small. Papadimitriou was the first to give a fixed-parameter algorithm for ILP Feasibility under parameterization by the number of constraints that runs in time ((A∞ + b∞) ⋅ k)O(k2). This was very recently improved by Eisenbrand and Weismantel, who used the Steinitz lemma to design an algorithm with running time (kA∞)O(k) ⋅ log b∞, which was subsequently refined by Jansen and Rohwedder to O( kA∞)k ⋅ log ( A∞ + b∞) ⋅ log A∞. 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 2o(k log k) ⋅ (ℓ + b∞)o(k) would contradict the exponential time hypothesis. This improves previous non-tight lower bounds of Fomin et al. 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 Koutecký et al. that ILP Feasibility can be solved in time A∞2O(tdD(A)) ⋅ (k + ℓ + log b∞)O(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 22o(tdD(A)) ⋅ (k + ℓ)O(1) would contradict the exponential time hypothesis.

Fine-Grained View on Bribery for Group Identification

Autoři
Boehmer, N.; Bredereck, R.; Knop, D.; Luo, J.
Rok
2020
Publikováno
Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, 2020. p. 67-73. ISBN 978-0-9992411-6-5.
Typ
Stať ve sborníku
Anotace
Given a set of individuals qualifying or disqualifying each other, group identification is the task of identifying a socially qualified subgroup of individuals. Social qualification depends on the specific rule used to aggregate individual qualifications. The bribery problem in this context asks how many agents need to change their qualifications in order to change the outcome. Complementing previous results showing polynomial-time solvability or NP-hardness of bribery for various social rules in the constructive (aiming at making specific individuals socially qualified) or destructive (aiming at making specific individuals socially disqualified) setting, we provide a comprehensive picture of the parameterized computational complexity landscape. Conceptually, we also consider a more fine-grained concept of bribery cost, where we ask how many single qualifications need to be changed, and a more general bribery goal that combines the constructive and destructive setting.

Adapting Stable Matchings to Evolving Preferences

Autoři
Bredereck, R.; Chen, J.; Knop, D.; Luo, J.; Niedermeier, R.
Rok
2020
Publikováno
Proceedings of the AAAI Conference on Artificial Intelligence. Menlo Park: AAAI Press, 2020. p. 1830-1837. ISSN 2159-5399. ISBN 978-1-57735-835-0.
Typ
Stať ve sborníku
Anotace
Adaptivity to changing environments and constraints is key to success in modern society. We address this by proposing “incrementalized versions” of Stable Marriage and Stable Roommates. That is, we try to answer the following question: for both problems, what is the computational cost of adapting an existing stable matching after some of the preferences of the agents have changed. While doing so, we also model the constraint that the new stable matching shall be not too different from the old one. After formalizing these incremental versions, we provide a fairly comprehensive picture of the computational complexity landscape of Incremental Stable Marriage and Incremental Stable Roommates. To this end, we exploit the parameters “degree of change” both in the input (difference between old and new preference profile) and in the output (difference between old and new stable matching). We obtain both hardness and tractability results, in particular showing a fixed-parameter tractability result with respect to the parameter “distance between old and new stable matching”.

Parameterized Algorithms for Finding a Collective Set of Items

Autoři
Bredereck, R.; Faliszewski, P.; Kaczmarczyk, A.; Knop, D.; Niedermeier, R.
Rok
2020
Publikováno
Proceedings of the AAAI Conference on Artificial Intelligence. Menlo Park: AAAI Press, 2020. p. 1838-1845. ISSN 2159-5399. ISBN 978-1-57735-835-0.
Typ
Stať ve sborníku
Anotace
We extend the work of Skowron et al. (AIJ, 2016) by considering the parameterized complexity of the following problem. We are given a set of items and a set of agents, where each agent assigns an integer utility value to each item. The goal is to find a set of k items that these agents would collectively use. For each such collective set of items, each agent provides a score that can be described using an OWA (ordered weighted average) operator and we seek a set with the highest total score. We focus on the parameterization by the number of agents and we find numerous fixed-parameter tractability results (however, we also find some W[1]-hardness results). It turns out that most of our algorithms even apply to the setting where each agent has an integer weight.

The Clever Shopper Problem

Autoři
Bulteau, L.; Hermelin, D.; Knop, D.; Labarre, A.; Vialette, S.
Rok
2020
Publikováno
Theory of Computing Systems. 2020, 64(1), 17-34. ISSN 1432-4350.
Typ
Článek
Anotace
We investigate a variant of the so-called Internet Shopping problem introduced by Blazewicz et al. (Appl. Math. Comput. Sci. 20, 385–390, 2010), where a customer wants to buy a list of products at the lowest possible total cost from shops which offer discounts when purchases exceed a certain threshold. Although the problem is NP-hard, we provide exact algorithms for several cases, e.g. when each shop sells only two items, and an FPT algorithm for the number of items, or for the number of shops when all prices are equal. We complement each result with hardness proofs in order to draw a tight boundary between tractable and intractable cases. Finally, we give an approximation algorithm and hardness results for the problem of maximising the sum of discounts.

Partitioning graphs into induced subgraphs

Autoři
Rok
2020
Publikováno
Discrete Applied Mathematics. 2020, 272 31-42. ISSN 0166-218X.
Typ
Článek
Anotace
We study the Partition into H problem from the parameterized complexity point of view. In the Partition into H problem the task is to partition the vertices of a graph G into sets V_1,...,V_r such that the graph H is isomorphic to the subgraph of G induced by each set V_i for i =1,...,r. The pattern graph H is fixed. For the parameterization we consider three distinct structural parameters of the graph G - namely the tree-width, the neighborhood diversity, and the modular-width. For the parameterization by the neighborhood diversity we obtain an FPT algorithm for every graph H. For the parameterization by the tree-width we obtain an FPT algorithm for every connected graph H, thus resolving an open question of Gajarský et al. (2013). Finally, for the parameterization by the modular-width we derive an FPT algorithm for every prime graph H.

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

Autoři
Bredereck, R.; Kaczmarczyk, A.; Knop, D.; 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.; Dvořák, P.; Valla, T.
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

Autoři
Blažej, V.; Křišťan, J.; Valla, T.
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
Chaplick, S.; Fomin, F.V.; Golovach, P.A.; Knop, D.; 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
Chitnis, R.; Feldmann, A.; Suchý, O.
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

Autoři
Červený, R.; Suchý, O.
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
Eiben, E.; Ganian, R.; Knop, D.; 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
Eiben, E.; Ganian, R.; Knop, D.; 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
Eiben, E.; Knop, D.; Panolan, F.; Suchý, O.
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

Autoři
Malík, J.; Suchý, O.; Valla, T.
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
Altmanová, K.; Knop, D.; 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.

Integer Programming in Parameterized Complexity: Three Miniatures

Autoři
Gavenčiak, T.; Knop, D.; 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.

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

Autoři
van Bevern, R.; Fluschnik, T.; Mertzios, G.B.; Molter, H.; Sorge, M.; Suchý, O.
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
Chen, J.; Molter, H.; Sorge, M.; Suchý, O.
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
Dvořák, P.; Knop, D.; 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.

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