46 results on '"Leeuwen, Erik Jan van"'
Search Results
2. On the Complexity of the Normalized Cut Problem on H-Free Graph Classes
- Author
-
Nieboer, Thomas, Leeuwen, Erik Jan van (Thesis Advisor), Nieboer, Thomas, and Leeuwen, Erik Jan van (Thesis Advisor)
- Abstract
The Normalized Cut problem is a graph partitioning problem that is known to be NP-complete in general. Therefore, we look into the complexity of the Normalized Cut problem on certain H-free graph classes. H-free graphs are those which do not contain any graph of H as an induced subgraph, for any fixed set of graphs H. We show that the Normalized Cut problem is NP-complete on claw-free, split, and complete graphs. Furthermore, we show that the Normalized Cut problem with unweighted edges is strongly NP-complete in general. On the other hand, we show that the partition with minimum normalized cut value has two connected components and use this property to construct polynomial-time algorithms on certain H-free graph classes. We show that we can solve the Normalized Cut problem on forests in linear time and on outerplanar graphs in quadratic time. Furthermore, we show that we can solve the Normalized Cut problem with unweighted edges on cactus and cluster graphs in linear time. Lastly, we observe that there exists an O(log(n))-approximation algorithm for another graph partitioning problem to which we can reduce the Normalized Cut problem. Therefore, we have an O(log(n))- approximation algorithm for the Normalized Cut problem.
- Published
- 2023
3. Parameterized Complexity Of Defensive Alliances
- Author
-
Horn, Beowulf, Leeuwen, Erik Jan van (Thesis Advisor), Horn, Beowulf, and Leeuwen, Erik Jan van (Thesis Advisor)
- Abstract
A Defensive Alliance in a graph is a subset of the vertices where each vertex in the alliance has more neighbours in the alliance, than outside it. They were originally introduced to model military alliances, but the concept has application in areas such as modelling communities and also fault tolerant computing. Finding small Defensive Alliances is known to be a NP-Complete problem, even in restrictive graph classes such as planar graphs. The difficulty of finding small Defensive Alliances provides the motivation to look at the parameterised complexity of the problem, which in the literature is documented only for a small number of parameters such as Solution Size, Vertex Cover and Neighbourhood Diversity. Further, a restricted set of variants were considered in the literature, with limited practical work done in finding alliances. This thesis endeavored to address these limitations by studying the parameterised complexity of variants of Defensive Alliance, considers new parameters for Defensive Alliance and conducts computational experiments using implementations of some of the algorithms discussed in the thesis. For the variants, the general results involve several novel variants, such as one that generalises the number of neighbours required for each vertex, several that force larger components of the alliance to depend on sets of constraints, vertex and edge weighted variants. For these, whether or not it was possible to extend the existing algorithms to the variants is discussed. Results are given for several new parameters, including Modular Width and Distance to Clique, for Defensive Alliance, along with minor results covering the use of multiple parameters. Further, a previously studied problem called Globally Minimal Defensive Alliance is shown to be in para-NP when parameterised by Solution Size. Finally, experimental results for a variety of exact algorithms and heuristics are discussed.
- Published
- 2023
4. The Multiplicative Weights Method in Quantum Computing
- Author
-
Henstra, Freek, Leeuwen, Erik Jan van (Thesis Advisor), Henstra, Freek, and Leeuwen, Erik Jan van (Thesis Advisor)
- Abstract
The multiplicative weights method is a meta-algorithm: a general template for a large variety of algorithms. Algorithms with this structure have been independently developed across many fields. We explore the usage of the multiplicative weights method in machine learning, linear programs and semidefinite programs, as well as how these algorithms can be improved upon using quantum computers. In machine learning, the multiplicative weights method is used for boosting algorithms, which can create a strong learner through repeated calls of a weak learner. Linear programs can be approximately solved by first converting them to zero-sum games and then running two simultaneous instances of the multiplicative weights method. We developed an algorithm for solving semidefinite programs with a similar approach, but it is outperformed by existing algorithms.
- Published
- 2023
5. Few induced disjoint paths for H-free graphs
- Author
-
Martin, Barnaby, Paulusma, Daniël, Smith, Siani, Leeuwen, Erik Jan van, Sub Algorithms and Complexity, Algorithms and Complexity, Sub Algorithms and Complexity, and Algorithms and Complexity
- Subjects
FOS: Computer and information sciences ,General Computer Science ,Discrete Mathematics (cs.DM) ,H-free graph ,Induced disjoint paths ,Computational Complexity (cs.CC) ,Theoretical Computer Science ,Computer Science - Computational Complexity ,Computer Science - Data Structures and Algorithms ,FOS: Mathematics ,Complexity dichotomy ,Mathematics - Combinatorics ,Data Structures and Algorithms (cs.DS) ,Combinatorics (math.CO) ,Computer Science - Discrete Mathematics ,Computer Science(all) - Abstract
Paths $P^1,\ldots,P^k$ in a graph $G=(V,E)$ are mutually induced if any two distinct $P^i$ and $P^j$ have neither common vertices nor adjacent vertices. For a fixed integer $k$, the $k$-Induced Disjoint Paths problem is to decide if a graph $G$ with $k$ pairs of specified vertices $(s_i,t_i)$ contains $k$ mutually induced paths $P^i$ such that each $P^i$ starts from $s_i$ and ends at $t_i$. Whereas the non-induced version is well-known to be polynomial-time solvable for every fixed integer $k$, a classical result from the literature states that even $2$-Induced Disjoint Paths is NP-complete. We prove new complexity results for $k$-Induced Disjoint Paths if the input is restricted to $H$-free graphs, that is, graphs without a fixed graph $H$ as an induced subgraph. We compare our results with a complexity dichotomy for Induced Disjoint Paths, the variant where $k$ is part of the input.
- Published
- 2023
6. Parameterized Complexity of Streaming Diameter and Connectivity Problems
- Author
-
Oostveen, Jelle J., Leeuwen, Erik Jan van, Dell, Holger, Nederlof, Jesper, Sub Algorithms and Complexity, and Algorithms and Complexity
- Subjects
Connectivity ,Diameter ,Disjointness ,Parameter ,Permutation ,Vertex Cover ,Stream ,Complexity ,Streaming ,Graphs - Abstract
We initiate the investigation of the parameterized complexity of Diameter and Connectivity in the streaming paradigm. On the positive end, we show that knowing a vertex cover of size k allows for algorithms in the Adjacency List (AL) streaming model whose number of passes is constant and memory is O(log n) for any fixed k. Underlying these algorithms is a method to execute a breadth-first search in O(k) passes and O(klog n) bits of memory. On the negative end, we show that many other parameters lead to lower bounds in the AL model, where Ω(n/p) bits of memory is needed for any p-pass algorithm even for constant parameter values. In particular, this holds for graphs with a known modulator (deletion set) of constant size to a graph that has no induced subgraph isomorphic to a fixed graph H, for most H. For some cases, we can also show one-pass, Ω(nlog n) bits of memory lower bounds. We also prove a much stronger Ω(n2/p) lower bound for Diameter on bipartite graphs. Finally, using the insights we developed into streaming parameterized graph exploration algorithms, we show a new streaming kernelization algorithm for computing a vertex cover of size k. This yields a kernel of 2k vertices (with O(k2) edges) produced as a stream in poly(k) passes and only O(klog n) bits of memory.
- Published
- 2022
7. Induced Disjoint Paths in AT-free graphs
- Author
-
Sub Algorithms and Complexity, Algorithms and Complexity, Golovach, Petr A., Paulusma, Daniël, Leeuwen, Erik Jan van, Sub Algorithms and Complexity, Algorithms and Complexity, Golovach, Petr A., Paulusma, Daniël, and Leeuwen, Erik Jan van
- Published
- 2022
8. Disjoint paths and connected subgraphs for H-free graphs
- Author
-
Sub Algorithms and Complexity, Algorithms and Complexity, Kern, Walter, Martin, Barnaby, Paulusma, Daniël, Smith, Siani, Leeuwen, Erik Jan van, Sub Algorithms and Complexity, Algorithms and Complexity, Kern, Walter, Martin, Barnaby, Paulusma, Daniël, Smith, Siani, and Leeuwen, Erik Jan van
- Published
- 2022
9. Using State Evaluation and Artificial Neural Networks to solve the Firefighter Problem
- Author
-
Lambooij, Nikè, Leeuwen, Erik Jan van (Thesis Advisor), Lambooij, Nikè, and Leeuwen, Erik Jan van (Thesis Advisor)
- Abstract
The Firefighter Problem (FFP) on graphs is a model for fighting the spread of a fire through a city. At each time step d nodes can be defended from the fire, before the fire spreads to all undefended nodes adjacent to a burning node. In this thesis we investigate the application of State Evaluation to this problem, creating an ANN called SEANN for this purpose. We also describe a second neural network, called CLANN that solves FFP more directly by classifying which node should be protected at the current time step. To solve the FFP we created several solvers that use some form of State Evaluation, and we compare these to the optimal solution found by solving an ILP model and to a greedy algorithm in case of trees. Our experiments show that State Evaluation works very well for FFP, especially a Greedy State Evaluation algorithm that uses a Greedy Look-ahead algorithm to evaluate potential future states. The CLANN network, however, performs worse than basic greedy heuristics.
- Published
- 2022
10. Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs
- Author
-
Sub Algorithms and Complexity, Algorithms and Complexity, Martin, Barnaby, Paulusma, Daniël, Smith, Siani, Leeuwen, Erik Jan van, Sub Algorithms and Complexity, Algorithms and Complexity, Martin, Barnaby, Paulusma, Daniël, Smith, Siani, and Leeuwen, Erik Jan van
- Published
- 2022
11. Upper bounding rainbow connection number by forest number.
- Author
-
Sub Algorithms and Complexity, Algorithms and Complexity, Chandran, L. Sunil, Issac, Davis, Lauri, Juho, Leeuwen, Erik Jan van, Sub Algorithms and Complexity, Algorithms and Complexity, Chandran, L. Sunil, Issac, Davis, Lauri, Juho, and Leeuwen, Erik Jan van
- Published
- 2022
12. Parameterized Complexity of Streaming Diameter and Connectivity Problems
- Author
-
Sub Algorithms and Complexity, Algorithms and Complexity, Oostveen, Jelle J., Leeuwen, Erik Jan van, Dell, Holger, Nederlof, Jesper, Sub Algorithms and Complexity, Algorithms and Complexity, Oostveen, Jelle J., Leeuwen, Erik Jan van, Dell, Holger, and Nederlof, Jesper
- Published
- 2022
13. Disjoint Paths and Connected Subgraphs for H-Free Graphs
- Author
-
Kern, Walter, Martin, Barnaby, Paulusma, Daniël, Smith, Siani, Leeuwen, Erik Jan van, Flocchini, Paola, Moura, Lucia, Sub Algorithms and Complexity, and Algorithms and Complexity
- Subjects
Theoretical Computer Science ,Computer Science(all) - Abstract
The well-known Disjoint Paths problem is to decide if a graph contains k pairwise disjoint paths, each connecting a different terminal pair from a set of k distinct pairs. We determine, with an exception of two cases, the complexity of the Disjoint Paths problem for H-free graphs. If k is fixed, we obtain the k -Disjoint Paths problem, which is known to be polynomial-time solvable on the class of all graphs for every k≥ 1. The latter does no longer hold if we need to connect vertices from terminal sets instead of terminal pairs. We completely classify the complexity of k -Disjoint Connected Subgraphs for H-free graphs, and give the same almost-complete classification for Disjoint Connected Subgraphs for H-free graphs as for Disjoint Paths.
- Published
- 2021
14. Bitmap Compression Techniques for Large Graph Treewidth Computation
- Author
-
Munnichs, Jasper, Leeuwen, Erik Jan van (Thesis Advisor), Munnichs, Jasper, and Leeuwen, Erik Jan van (Thesis Advisor)
- Abstract
In this thesis we investigate whether bitmap compression techniques could be useful data structures to represent vertex sets, for treewidth algorithms on large graphs. We consider bitmap compression techniques Roaring Bitmap and EWAH, and compare them with two more commonly used graph data structures: the bitmap and the array of integers. We investigate the behaviour of the data structures in two experiments. In the first, we investigate their computation time and memory consumption of typical vertex sets in the computation of separated components. In the second, we compare their performance on the Minimal Minimum Degree algorithm. We find that the array of integers representation performs best. However, as typical vertex sets that the data structures have to deal with get denser and more diverse, we observe that Roaring Bitmap starts to perform better.
- Published
- 2021
15. A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
- Author
-
Sub Algorithmic Systems begr. 01/07/2016, Sub Algorithms and Complexity, Algorithms, Jansen, Bart M. P., Pilipczuk, Marcin, Leeuwen, Erik Jan van, Sub Algorithmic Systems begr. 01/07/2016, Sub Algorithms and Complexity, Algorithms, Jansen, Bart M. P., Pilipczuk, Marcin, and Leeuwen, Erik Jan van
- Published
- 2021
16. Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs.
- Author
-
Sub Algorithms and Complexity, Algorithms and Complexity, Novotná, Jana, Okrasa, Karolina, Pilipczuk, Michal, Rzazewski, Pawel, Leeuwen, Erik Jan van, Walczak, Bartosz, Sub Algorithms and Complexity, Algorithms and Complexity, Novotná, Jana, Okrasa, Karolina, Pilipczuk, Michal, Rzazewski, Pawel, Leeuwen, Erik Jan van, and Walczak, Bartosz
- Published
- 2021
17. Disjoint Paths and Connected Subgraphs for H-Free Graphs.
- Author
-
Sub Algorithms and Complexity, Algorithms and Complexity, Kern, Walter, Martin, Barnaby, Paulusma, Daniël, Smith, Siani, Leeuwen, Erik Jan van, Flocchini, Paola, Moura, Lucia, Sub Algorithms and Complexity, Algorithms and Complexity, Kern, Walter, Martin, Barnaby, Paulusma, Daniël, Smith, Siani, Leeuwen, Erik Jan van, Flocchini, Paola, and Moura, Lucia
- Published
- 2021
18. Algorithms for the rainbow vertex coloring problem on graph classes
- Author
-
Sub Algorithms and Complexity, Sub Algemeen Math. Inst, Algorithms and Complexity, Lima, Paloma T., Leeuwen, Erik Jan van, Wegen, Marieke van der, Sub Algorithms and Complexity, Sub Algemeen Math. Inst, Algorithms and Complexity, Lima, Paloma T., Leeuwen, Erik Jan van, and Wegen, Marieke van der
- Published
- 2021
19. Induced Disjoint Paths in AT-free graphs
- Author
-
Golovach, Petr A., Paulusma, Daniël, Leeuwen, Erik Jan van, Sub Algorithms and Complexity, Algorithms and Complexity, Sub Algorithms and Complexity, and Algorithms and Complexity
- Subjects
FOS: Computer and information sciences ,Co-bipartite graph ,Discrete Mathematics (cs.DM) ,General Computer Science ,Induced topological minor ,Computer Networks and Communications ,Minor (linear algebra) ,0102 computer and information sciences ,Disjoint sets ,Computational Complexity (cs.CC) ,01 natural sciences ,W[1]-hardness ,Polynomial-time algorithm ,Theoretical Computer Science ,Combinatorics ,Computer Science - Data Structures and Algorithms ,FOS: Mathematics ,Mathematics - Combinatorics ,Data Structures and Algorithms (cs.DS) ,Disjoint paths ,0101 mathematics ,Time complexity ,Mathematics ,Applied Mathematics ,010102 general mathematics ,k-in-a-Path ,16. Peace & justice ,Graph ,AT-free graph ,k-in-a-Tree ,Computer Science - Computational Complexity ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Combinatorics (math.CO) ,Computer Science - Discrete Mathematics - Abstract
Paths $P_1,\ldots,P_k$ in a graph $G=(V,E)$ are mutually induced if any two distinct $P_i$ and $P_j$ have neither common vertices nor adjacent vertices (except perhaps their end-vertices). The Induced Disjoint Paths problem is to decide if a graph $G$ with $k$ pairs of specified vertices $(s_i,t_i)$ contains $k$ mutually induced paths $P_i$ such that each $P_i$ connects $s_i$ and $t_i$. This is a classical graph problem that is NP-complete even for $k=2$. We study it for AT-free graphs. Unlike its subclasses of permutation graphs and cocomparability graphs, the class of AT-free graphs has no geometric intersection model. However, by a new, structural analysis of the behaviour of Induced Disjoint Paths for AT-free graphs, we prove that it can be solved in polynomial time for AT-free graphs even when $k$ is part of the input. This is in contrast to the situation for other well-known graph classes, such as planar graphs, claw-free graphs, or more recently, (theta,wheel)-free graphs, for which such a result only holds if $k$ is fixed. As a consequence of our main result, the problem of deciding if a given AT-free graph contains a fixed graph $H$ as an induced topological minor admits a polynomial-time algorithm. In addition, we show that such an algorithm is essentially optimal by proving that the problem is W[1]-hard with parameter $|V_H|$, even on a subclass of AT-free graph, namely cobipartite graphs. We also show that the problems $k$-in-a-Path and $k$-in-a-Tree are polynomial-time solvable on AT-free graphs even if $k$ is part of the input. These problems are to test if a graph has an induced path or induced tree, respectively, spanning $k$ given vertices., An extended abstract of this paper appeared in the proceedings of SWAT 2012
- Published
- 2022
20. Quasi-Polynomial Time Approximation Schemes for Packing and Covering Problems in Planar Graphs
- Author
-
Pilipczuk, Michal, Leeuwen, Erik Jan van, Wiese, Andreas, Azar, Yossi, Bast, Hannah, Herman, Grzegorz, Sub Algorithms and Complexity, Algorithms and Complexity, Sub Algorithms and Complexity, and Algorithms and Complexity
- Subjects
FOS: Computer and information sciences ,General Computer Science ,Minimum weight ,0102 computer and information sciences ,02 engineering and technology ,Disjoint sets ,Quasi-polynomial ,01 natural sciences ,Combinatorics ,Geometric set cover ,symbols.namesake ,Computer Science - Data Structures and Algorithms ,0202 electrical engineering, electronic engineering, information engineering ,QPTAS ,Data Structures and Algorithms (cs.DS) ,Voronoi diagram ,Mathematics ,Approximation schemes ,000 Computer science, knowledge, general works ,Applied Mathematics ,Multiplicative function ,Covering problems ,Planar graphs ,planar graphs ,Computer Science Applications ,Vertex (geometry) ,Planar graph ,010201 computation theory & mathematics ,68W25 (Approximation algorithms) ,Independent set of objects ,Independent set ,Computer Science ,symbols ,020201 artificial intelligence & image processing - Abstract
We consider two optimization problems in planar graphs. In Maximum Weight Independent Set of Objects we are given a graph $G$ and a family $\mathcal{D}$ of objects, each being a connected subgraph of $G$ with a prescribed weight, and the task is to find a maximum-weight subfamily of $\mathcal{D}$ consisting of pairwise disjoint objects. In Minimum Weight Distance Set Cover we are given an edge-weighted graph $G$, two sets $\mathcal{D},\mathcal{C}$ of vertices of $G$, where vertices of $\mathcal{D}$ have prescribed weights, and a nonnegative radius $r$. The task is to find a minimum-weight subset of $\mathcal{D}$ such that every vertex of $\mathcal{C}$ is at distance at most $r$ from some selected vertex. Via simple reductions, these two problems generalize a number of geometric optimization tasks, notably Maximum Weight Independent Set for polygons in the plane and Weighted Geometric Set Cover for unit disks and unit squares. We present quasi-polynomial time approximation schemes (QPTASs) for both of the above problems in planar graphs: given an accuracy parameter $\epsilon>0$ we can compute a solution whose weight is within multiplicative factor of $(1+\epsilon)$ from the optimum in time $2^{\mathrm{poly}(1/\epsilon,\log |\mathcal{D}|)}\cdot n^{\mathcal{O}(1)}$, where $n$ is the number of vertices of the input graph. Our main technical contribution is to transfer the techniques used for recursive approximation schemes for geometric problems due to Adamaszek, Har-Peled, and Wiese to the setting of planar graphs. In particular, this yields a purely combinatorial viewpoint on these methods., Comment: 31 pages, 5 figures, accepted at ESA 2018
- Published
- 2020
21. Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices
- Author
-
Nederlof, Jesper, Fomin, Fedor V., Kratsch, Stefan, Leeuwen, Erik Jan van, Sub Algorithms and Complexity, and Algorithms and Complexity
- Abstract
We survey a number of recent results that relate the fine-grained complexity of several NP-Hard problems with the rank of certain matrices. The main technical theme is that for a wide variety of Divide & Conquer algorithms, structural insights on associated partial solutions matrices may directly lead to speedups.
- Published
- 2020
22. Disjoint paths and connected subgraphs for H-free graphs
- Author
-
Kern, Walter, Martin, Barnaby, Paulusma, Daniël, Smith, Siani, Leeuwen, Erik Jan van, Sub Algorithms and Complexity, Algorithms and Complexity, Sub Algorithms and Complexity, and Algorithms and Complexity
- Subjects
FOS: Computer and information sciences ,Class (set theory) ,Discrete Mathematics (cs.DM) ,General Computer Science ,H-free graph ,Disjoint sets ,Computational Complexity (cs.CC) ,Graph ,Theoretical Computer Science ,Combinatorics ,Set (abstract data type) ,Computer Science - Computational Complexity ,Terminal (electronics) ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,Computer Science - Data Structures and Algorithms ,FOS: Mathematics ,Complexity dichotomy ,Mathematics - Combinatorics ,Data Structures and Algorithms (cs.DS) ,Combinatorics (math.CO) ,Disjoint paths ,Computer Science - Discrete Mathematics ,Mathematics ,MathematicsofComputing_DISCRETEMATHEMATICS ,Computer Science(all) - Abstract
The well-known Disjoint Paths problem is to decide if a graph contains k pairwise disjoint paths, each connecting a different terminal pair from a set of k distinct vertex pairs. We determine, with an exception of two cases, the complexity of the Disjoint Paths problem for H-free graphs. If k is fixed, we obtain the k-Disjoint Paths problem, which is known to be polynomial-time solvable on the class of all graphs for every k ≥ 1. The latter does no longer hold if we need to connect vertices from terminal sets instead of terminal pairs. We completely classify the complexity of k-Disjoint Connected Subgraphs for H-free graphs, and give the same almost-complete classification for Disjoint Connected Subgraphs for H-free graphs as for Disjoint Paths. Moreover, we give exact algorithms for Disjoint Paths and Disjoint Connected Subgraphs on graphs with n vertices and m edges that have running times of O(2nn 2 k) and O(3n km), respectively.
- Published
- 2022
23. Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective
- Author
-
Sub Algorithms and Complexity, Algorithms and Complexity, Bodlaender, H.L., Brettell, Nick, Johnson, Matthew, Paesani, Giacomo, Paulusma, Daniel, Leeuwen, Erik Jan van, Sub Algorithms and Complexity, Algorithms and Complexity, Bodlaender, H.L., Brettell, Nick, Johnson, Matthew, Paesani, Giacomo, Paulusma, Daniel, and Leeuwen, Erik Jan van
- Published
- 2020
24. Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices
- Author
-
Sub Algorithms and Complexity, Algorithms and Complexity, Nederlof, Jesper, Fomin, Fedor V., Kratsch, Stefan, Leeuwen, Erik Jan van, Sub Algorithms and Complexity, Algorithms and Complexity, Nederlof, Jesper, Fomin, Fedor V., Kratsch, Stefan, and Leeuwen, Erik Jan van
- Published
- 2020
25. Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices
- Author
-
Algorithms and Complexity, Sub Algorithms and Complexity, Fomin, Fedor V., Kratsch, Stefan, Leeuwen, Erik Jan van, Nederlof, Jesper, Algorithms and Complexity, Sub Algorithms and Complexity, Fomin, Fedor V., Kratsch, Stefan, Leeuwen, Erik Jan van, and Nederlof, Jesper
- Published
- 2020
26. Polynomial kernels for deletion to classes of acyclic digraphs
- Author
-
Mnich, Matthias, Leeuwen, Erik Jan van, Mnich, Matthias, and Leeuwen, Erik Jan van
- Abstract
We consider the problem to find a set X of vertices (or arcs) with |X| <= k in a given digraph G such that D = G-X is an acyclic digraph. In its generality, this is DIRECTED FEEDBACK VERTEX SET or DIRECTED FEEDBACK ARC SET respectively. The existence of a polynomial kernel for these problems is a notorious open problem in the field of kernelization, and little progress has been made. In this paper, we consider both deletion problems with an additional restriction on D, namely that D must be an out-forest, an out-tree, or a (directed) pumpkin. Our main results show that for each of these three restrictions the vertex deletion problem remains NP-hard, but we can obtain a kernel with k^{O(1)} vertices on general digraphs G. We also show that, in contrast to the vertex deletion problem, the arc deletion problem with each of the above restrictions can be solved in polynomial time.
- Published
- 2020
27. Independence and Efficient Domination on P 6 -free Graphs
- Author
-
Lokshtanov, Daniel, Pilipczuk, Marcin, Leeuwen, Erik Jan van, Sub Algorithms and Complexity, and Algorithms and Complexity
- Subjects
Computational complexity theory ,010102 general mathematics ,Induced subgraph ,0102 computer and information sciences ,Independence ,efficient domination ,01 natural sciences ,Graph ,Vertex (geometry) ,Combinatorics ,Mathematics (miscellaneous) ,010201 computation theory & mathematics ,Dominating set ,Independent set ,(quasi) polynomial-time algorithms ,P-6-free graphs ,Pairwise comparison ,0101 mathematics ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
In the M aximum W eight I ndependent S et problem, the input is a graph G , every vertex has a non-negative integer weight, and the task is to find a set S of pairwise nonadjacent vertices, maximizing the total weight of the vertices in S . We give an n O (log 2 n ) time algorithm for this problem on graphs excluding the path P 6 on 6 vertices as an induced subgraph. Currently, there is no constant k known for which M aximum W eight I ndependent S et on P k -free graphs becomes NP-hard, and our result implies that if such a k exists, then k > 6 unless all problems in NP can be decided in quasi-polynomial time. Using the combinatorial tools that we develop for this algorithm, we also give a polynomial-time algorithm for M aximum W eight E fficient D ominating S et on P 6 -free graphs. In this problem, the input is a graph G , every vertex has an integer weight, and the objective is to find a set S of maximum weight such that every vertex in G has exactly one vertex in S in its closed neighborhood or to determine that no such set exists. Prior to our work, the class of P 6 -free graphs was the only class of graphs defined by a single forbidden induced subgraph on which the computational complexity of M aximum W eight E fficient D ominating S et was unknown.
- Published
- 2017
28. Nearly ETH-tight Algorithms for Planar Steiner Tree with Terminals on Few Faces
- Author
-
Kisfaludi-Bak, Sándor, primary, Nederlof, Jesper, additional, and Leeuwen, Erik Jan van, additional
- Published
- 2020
- Full Text
- View/download PDF
29. Nearly ETH-tight algorithms for Planar Steiner Tree with Terminals on Few Faces
- Author
-
Kisfaludi-Bak, Sándor, Nederlof, Jesper, Leeuwen, Erik Jan van, Sub Algorithms and Complexity, and Algorithms and Complexity
- Abstract
The Steiner Tree problem is one of the most fundamental NP-complete problems as it models many network design problems. Recall that an instance of this problem consists of a graph with edge weights, and a subset of vertices (often called terminals); the goal is to find a subtree of the graph of minimum total weight that connects all terminals. A seminal paper by Erickson et al. [Math. Oper. Res., 1987] considers instances where the underlying graph is planar and all terminals can be covered by the boundary of k faces. Erickson et al. show that the problem can be solved by an algorithm using nO(k) time and nO(k) space, where n denotes the number of vertices of the input graph. In the past 30 years there has been no significant improvement of this algorithm, despite several efforts. In this work, we give an algorithm for Planar Steiner Tree with running time using only polynomial space. Furthermore, we show the running time of our algorithm is almost tight: we prove that there is no algorithm for Planar Steiner Tree for any computable function f, unless the Exponential Time Hypothesis fails. Read More: https://epubs.siam.org/doi/10.1137/1.9781611975482.63
- Published
- 2019
30. Nearly ETH-tight algorithms for Planar Steiner Tree with Terminals on Few Faces
- Author
-
Sub Algorithms and Complexity, Algorithms and Complexity, Kisfaludi-Bak, Sándor, Nederlof, Jesper, Leeuwen, Erik Jan van, Sub Algorithms and Complexity, Algorithms and Complexity, Kisfaludi-Bak, Sándor, Nederlof, Jesper, and Leeuwen, Erik Jan van
- Published
- 2019
31. Algorithms and Bounds for Very Strong Rainbow Coloring
- Author
-
Chandran, L. Sunil, Das, Anita, Issac, Davis, Leeuwen, Erik Jan van, Bender, Michael A., Farach-Colton, Martin, Mosteiro, Miguel A., Sub Algorithms and Complexity, and Algorithms and Complexity
- Abstract
A well-studied coloring problem is to assign colors to the edges of a graph G so that, for every pair of vertices, all edges of at least one shortest path between them receive different colors. The minimum number of colors necessary in such a coloring is the strong rainbow connection number ( src(G) ) of the graph. When proving upper bounds on src(G) , it is natural to prove that a coloring exists where, for every shortest path between every pair of vertices in the graph, all edges of the path receive different colors. Therefore, we introduce and formally define this more restricted edge coloring number, which we call very strong rainbow connection number ( vsrc(G) ). In this paper, we give upper bounds on vsrc(G) for several graph classes, some of which are tight. These immediately imply new upper bounds on src(G) for these classes, showing that the study of vsrc(G) enables meaningful progress on bounding src(G) . Then we study the complexity of the problem to compute vsrc(G) , particularly for graphs of bounded treewidth, and show this is an interesting problem in its own right. We prove that vsrc(G) can be computed in polynomial time on cactus graphs; in contrast, this question is still open for src(G) . We also observe that deciding whether vsrc(G)=k is fixed-parameter tractable in k and the treewidth of G. Finally, on general graphs, we prove that there is no polynomial-time algorithm to decide whether vsrc(G)≤3 nor to approximate vsrc(G) within a factor n1−ε , unless P=NP .
- Published
- 2018
32. Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs
- Author
-
Heggernes, Pinar, Issac, Davis, Lauri, Juho, Lima, Paloma T., Leeuwen, Erik Jan van, Potapov, Igor, Spirakis, Paul, Worrell, James, Sub Algorithms and Complexity, and Algorithms and Complexity
- Subjects
graph classes ,Rainbow coloring ,approximation algorithms ,polynomial-time algorithms - Abstract
Given a graph with colors on its vertices, a path is called a rainbow vertex path if all its internal vertices have distinct colors. We say that the graph is rainbow vertex-connected if there is a rainbow vertex path between every pair of its vertices. We study the problem of deciding whether the vertices of a given graph can be colored with at most k colors so that the graph becomes rainbow vertex-connected. Although edge-colorings have been studied extensively under similar constraints, there are significantly fewer results on the vertex variant that we consider. In particular, its complexity on structured graph classes was explicitly posed as an open question. We show that the problem remains NP-complete even on bipartite apex graphs and on split graphs. The former can be seen as a first step in the direction of studying the complexity of rainbow coloring on sparse graphs, an open problem which has attracted attention but limited progress. We also give hardness of approximation results for both bipartite and split graphs. To complement the negative results, we show that bipartite permutation graphs, interval graphs, and block graphs can be rainbow vertex-connected optimally in polynomial time.
- Published
- 2018
33. Solving Partition Problems Almost Always Requires Pushing Many Vertices Around
- Author
-
Kanj, Iyad A., Komusiewicz, Christian, Sorge, Manuel, Leeuwen, Erik Jan van, Azar, Yossi, Bast, Hannah, Herman, Grzegorz, Sub Algorithms and Complexity, and Algorithms and Complexity
- Abstract
A fundamental graph problem is to recognize whether the vertex set of a graph G can be bipartitioned into sets A and B such that G[A] and G[B] satisfy properties ΠA and ΠB, respectively. This so-called (ΠA, ΠB)-Recognition problem generalizes amongst others the recognition of 3-colorable, bipartite, split, and monopolar graphs. A powerful algorithmic technique that can be used to obtain fixed-parameter algorithms for many cases of (ΠA, ΠB)-Recognition, as well as several other problems, is the pushing process. For bipartition problems, the process starts with an “almost correct” bipartition (A0 , B0 ), and pushes appropriate vertices from A0 to B0 and vice versa to eventually arrive at a correct bipartition. In this paper, we study whether (ΠA, ΠB)-Recognition problems for which the pushing process yields fixed-parameter algorithms also admit polynomial problem kernels. In our study, we focus on the first level above triviality, where ΠA is the set of P3-free graphs (disjoint unions of cliques, or cluster graphs), the parameter is the number of clusters in the cluster graph G[A], and ΠB is characterized by a set H of connected forbidden induced subgraphs. We prove that, under the assumption that NP 6⊆ coNP/poly, (ΠA, ΠB)-Recognition admits a polynomial kernel if and only if H contains a graph of order at most 2. In both the kernelization and the lower bound results, we make crucial use of the pushing process.
- Published
- 2018
34. Quasi-Polynomial Time Approximation Schemes for Packing and Covering Problems in Planar Graphs
- Author
-
Pilipczuk, Michal, Leeuwen, Erik Jan van, Wiese, Andreas, Azar, Yossi, Bast, Hannah, Herman, Grzegorz, Sub Algorithms and Complexity, and Algorithms and Complexity
- Subjects
QPTAS ,Voronoi diagram ,planar graphs - Abstract
We consider two optimization problems in planar graphs. In {Maximum Weight Independent Set of Objects} we are given a graph G and a family D of {objects}, each being a connected subgraph of G with a prescribed weight, and the task is to find a maximum-weight subfamily of D consisting of pairwise disjoint objects. In {Minimum Weight Distance Set Cover} we are given an edge-weighted graph G, two sets D,C of vertices of G, where vertices of D have prescribed weights, and a nonnegative radius r. The task is to find a minimum-weight subset of D such that every vertex of C is at distance at most r from some selected vertex. Via simple reductions, these two problems generalize a number of geometric optimization tasks, notably {Maximum Weight Independent Set} for polygons in the plane and {Weighted Geometric Set Cover} for unit disks and unit squares. We present {quasi-polynomial time approximation schemes} (QPTASs) for both of the above problems in planar graphs: given an accuracy parameter epsilon>0 we can compute a solution whose weight is within multiplicative factor of (1+epsilon) from the optimum in time 2^{poly(1/epsilon,log |D|)}* n^{O(1)}, where n is the number of vertices of the input graph. Our main technical contribution is to transfer the techniques used for recursive approximation schemes for geometric problems due to Adamaszek, Har-Peled, and Wiese [Adamaszek and Wiese, 2013; Adamaszek and Wiese, 2014; Sariel Har-Peled, 2014] to the setting of planar graphs. In particular, this yields a purely combinatorial viewpoint on these methods.
- Published
- 2018
35. Domination When the Stars Are Out
- Author
-
Hermelin, Danny, primary, Mnich, Matthias, additional, Leeuwen, Erik Jan Van, additional, and Woeginger, Gerhard, additional
- Published
- 2019
- Full Text
- View/download PDF
36. Independence and efficient domination on P6-free graphs
- Author
-
Sub Algorithms and Complexity, Algorithms and Complexity, Lokshtanov, Daniel, Pilipczuk, Marcin, Leeuwen, Erik Jan van, Sub Algorithms and Complexity, Algorithms and Complexity, Lokshtanov, Daniel, Pilipczuk, Marcin, and Leeuwen, Erik Jan van
- Published
- 2018
37. Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
- Author
-
Sub Algorithms and Complexity, Algorithms and Complexity, Pilipczuk, Marcin, Pilipczuk, Michal, Sankowski, Piotr, Leeuwen, Erik Jan van, Sub Algorithms and Complexity, Algorithms and Complexity, Pilipczuk, Marcin, Pilipczuk, Michal, Sankowski, Piotr, and Leeuwen, Erik Jan van
- Published
- 2018
38. Quasi-Polynomial Time Approximation Schemes for Packing and Covering Problems in Planar Graphs
- Author
-
Sub Algorithms and Complexity, Algorithms and Complexity, Pilipczuk, Michal, Leeuwen, Erik Jan van, Wiese, Andreas, Azar, Yossi, Bast, Hannah, Herman, Grzegorz, Sub Algorithms and Complexity, Algorithms and Complexity, Pilipczuk, Michal, Leeuwen, Erik Jan van, Wiese, Andreas, Azar, Yossi, Bast, Hannah, and Herman, Grzegorz
- Published
- 2018
39. Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs
- Author
-
Sub Algorithms and Complexity, Algorithms and Complexity, Heggernes, Pinar, Issac, Davis, Lauri, Juho, Lima, Paloma T., Leeuwen, Erik Jan van, Potapov, Igor, Spirakis, Paul, Worrell, James, Sub Algorithms and Complexity, Algorithms and Complexity, Heggernes, Pinar, Issac, Davis, Lauri, Juho, Lima, Paloma T., Leeuwen, Erik Jan van, Potapov, Igor, Spirakis, Paul, and Worrell, James
- Published
- 2018
40. Solving Partition Problems Almost Always Requires Pushing Many Vertices Around
- Author
-
Sub Algorithms and Complexity, Algorithms and Complexity, Kanj, Iyad A., Komusiewicz, Christian, Sorge, Manuel, Leeuwen, Erik Jan van, Azar, Yossi, Bast, Hannah, Herman, Grzegorz, Sub Algorithms and Complexity, Algorithms and Complexity, Kanj, Iyad A., Komusiewicz, Christian, Sorge, Manuel, Leeuwen, Erik Jan van, Azar, Yossi, Bast, Hannah, and Herman, Grzegorz
- Published
- 2018
41. Algorithms and Bounds for Very Strong Rainbow Coloring
- Author
-
Sub Algorithms and Complexity, Algorithms and Complexity, Chandran, L. Sunil, Das, Anita, Issac, Davis, Leeuwen, Erik Jan van, Bender, Michael A., Farach-Colton, Martin, Mosteiro, Miguel A., Sub Algorithms and Complexity, Algorithms and Complexity, Chandran, L. Sunil, Das, Anita, Issac, Davis, Leeuwen, Erik Jan van, Bender, Michael A., Farach-Colton, Martin, and Mosteiro, Miguel A.
- Published
- 2018
42. Fast dynamic programming on graph decompositions
- Author
-
van Rooij, Johan M.M., Bodlaender, Hans L., Leeuwen, Erik Jan van, Rossmanith, Peter, Vatshelle, Martin, van Rooij, Johan M.M., Bodlaender, Hans L., Leeuwen, Erik Jan van, Rossmanith, Peter, and Vatshelle, Martin
- Abstract
In this paper, we consider tree decompositions, branch decompositions, and clique decompositions. We improve the running time of dynamic programming algorithms on these graph decompositions for a large number of problems as a function of the treewidth, branchwidth, or cliquewidth, respectively. On tree decompositions of width $k$, we improve the running time for Dominating Set to $O(3^k)$. We generalise this result to $[\rho,\sigma]$-domination problems with finite or cofinite $\rho$ and $\sigma$. For these problems, we give $O(s^k)$-time algorithms, where $s$ is the number of `states' a vertex can have in a standard dynamic programming algorithm for such a problems. Furthermore, we give an $O(2^k)$-time algorithm for counting the number of perfect matchings in a graph, and generalise this to $O(2^k)$-time algorithms for many clique covering, packing, and partitioning problems. On branch decompositions of width $k$, we give an $O(3^{\frac{\omega}{2}k})$-time algorithm for Dominating Set, an $O(2^{\frac{\omega}{2}k})$-time algorithm for counting the number of perfect matchings, and $O(s^{\frac{\omega}{2}k})$-time algorithms for $[\rho,\sigma]$-domination problems involving $s$ states with finite or cofinite $\rho$ and $\sigma$. Finally, on clique decompositions of width $k$, we give $O(4^k)$-time algorithms for Dominating Set, Independent Dominating Set, and Total Dominating Set. The main techniques used in this paper are a generalisation of fast subset convolution, as introduced by Bj\"orklund et al., now applied in the setting of graph decompositions and augmented such that multiple states and multiple ranks can be used. Recently, Lokshtanov et al. have shown that some of the algorithms obtained in this paper have running times in which the base in the exponents is optimal, unless the Strong Exponential-Time Hypothesis fails.
- Published
- 2018
43. Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
- Author
-
Pilipczuk, Marcin, primary, Pilipczuk, Michał, additional, Sankowski, Piotr, additional, and Leeuwen, Erik Jan Van, additional
- Published
- 2018
- Full Text
- View/download PDF
44. Independence and Efficient Domination on $P_6$-free Graphs
- Author
-
Lokshtanov, Daniel, Pilipczuk, Marcin, Leeuwen, Erik Jan van, Sub Algorithms and Complexity, and Algorithms and Complexity
- Subjects
FOS: Computer and information sciences ,(quasi) polynomial-time algorithms ,Computer Science - Data Structures and Algorithms ,P-6-free graphs ,Data Structures and Algorithms (cs.DS) ,Independence ,efficient domination ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
In the Independent set problem, the input is a graph $G$, every vertex has a non-negative integer weight, and the task is to find a set $S$ of pairwise non-adjacent vertices, maximizing the total weight of the vertices in $S$. We give an $n^{O (\log^2 n)}$ time algorithm for this problem on graphs excluding the path $P_6$ on $6$ vertices as an induced subgraph. Currently, there is no constant $k$ known for which Independent Set on $P_{k}$-free graphs becomes NP-complete, and our result implies that if such a $k$ exists, then $k > 6$ unless all problems in NP can be decided in (quasi)polynomial time. Using the combinatorial tools that we develop for the above algorithm, we also give a polynomial-time algorithm for Efficient Dominating Set on $P_6$-free graphs. In this problem, the input is a graph $G$, every vertex has an integer weight, and the objective is to find a set $S$ of maximum weight such that every vertex in $G$ has exactly one vertex in $S$ in its closed neighborhood, or to determine that no such set exists. Prior to our work, the class of $P_6$-free graphs was the only class of graphs defined by a single forbidden induced subgraph on which the computational complexity of Efficient Dominating Set was unknown., v2: added reference to independent work arXiv:1508.07733
- Published
- 2015
- Full Text
- View/download PDF
45. Network Sparsification for {Steiner} Problems on Planar and Bounded-Genus Graphs
- Author
-
Pilipczuk, Marcin, Pilipczuk, Michal, Sankowski, Piotr, Leeuwen, Erik Jan van, Sub Algorithms and Complexity, Algorithms and Complexity, Sub Algorithms and Complexity, and Algorithms and Complexity
- Subjects
FOS: Computer and information sciences ,Parameterized complexity ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Steiner tree problem ,Combinatorics ,symbols.namesake ,Mathematics (miscellaneous) ,Polynomial kernel ,Genus (mathematics) ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,Computer Science - Data Structures and Algorithms ,0202 electrical engineering, electronic engineering, information engineering ,Data Structures and Algorithms (cs.DS) ,QA ,Computer Science::Data Structures and Algorithms ,Time complexity ,Mathematics ,Discrete mathematics ,Graph theory ,Data structure ,Tree (graph theory) ,Bidimensionality ,Planar graph ,010201 computation theory & mathematics ,Kernelization ,Bounded function ,symbols ,020201 artificial intelligence & image processing ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
We propose polynomial-time algorithms that sparsify planar and bounded-genus graphs while preserving optimal or near-optimal solutions to Steiner problems. Our main contribution is a polynomial-time algorithm that, given an unweighted undirected graph G embedded on a surface of genus g and a designated face f bounded by a simple cycle of length k , uncovers a set F ⊆ E ( G ) of size polynomial in g and k that contains an optimal Steiner tree for any set of terminals that is a subset of the vertices of f . We apply this general theorem to prove that: — Given an unweighted graph G embedded on a surface of genus g and a terminal set S ⊆ V ( G ), one can in polynomial time find a set F ⊆ E ( G ) that contains an optimal Steiner tree T for S and that has size polynomial in g and | E ( T )|. — An analogous result holds for an optimal Steiner forest for a set S of terminal pairs. — Given an unweighted planar graph G and a terminal set S ⊆ V ( G ), one can in polynomial time find a set F ⊆ E ( G ) that contains an optimal (edge) multiway cut C separating S (i.e., a cutset that intersects any path with endpoints in different terminals from S ) and that has size polynomial in | C |. In the language of parameterized complexity, these results imply the first polynomial kernels for S teiner T ree and S teiner F orest on planar and bounded-genus graphs (parameterized by the size of the tree and forest, respectively) and for (E dge ) M ultiway C ut on planar graphs (parameterized by the size of the cutset). Additionally, we obtain a weighted variant of our main contribution: a polynomial-time algorithm that, given an undirected plane graph G with positive edge weights, a designated face f bounded by a simple cycle of weight w ( f ), and an accuracy parameter ε > 0, uncovers a set F ⊆ E ( G ) of total weight at most poly(ε -1 ) w ( f ) that, for any set of terminal pairs that lie on f , contains a Steiner forest within additive error ε w ( f ) from the optimal Steiner forest.
- Published
- 2014
46. Independence and Efficient Domination on P6-free Graphs
- Author
-
Lokshtanov, Daniel, primary, Pilipczuk, Marcin, additional, and Leeuwen, Erik Jan van, additional
- Published
- 2015
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.