Search

Your search keyword '"Pilipczuk, Marcin"' showing total 20 results
Start Over Author "Pilipczuk, Marcin" Publisher association for computing machinery (acm)
20 results on '"Pilipczuk, Marcin"'

4. Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

Author

Sub Algorithms and Complexity, Algorithms and Complexity, Cygan, Marek, Nederlof, Jesper, Pilipczuk, Marcin, Pilipczuk, Michal, van Rooij, Johan, Wojtaszczyk, J.O., Sub Algorithms and Complexity, Algorithms and Complexity, Cygan, Marek, Nederlof, Jesper, Pilipczuk, Marcin, Pilipczuk, Michal, van Rooij, Johan, and Wojtaszczyk, J.O.

Published
2022

8. 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
Full Text
View/download PDF

14. 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

Catalog

Books, media, physical & digital resources
See catalog results