Zobrazeno 1 - 10
of 66
pro vyhledávání: '"Marcin Wrochna"'
Publikováno v:
LICS
2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
Logic in Computer Science
2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
Logic in Computer Science
We study polynomial-time approximation schemes (PTASes) for constraint satisfaction problems (CSPs) such as Maximum Independent Set or Minimum Vertex Cover on sparse graph classes. Baker's approach gives a PTAS on planar graphs, excluded-minor classe
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5d49dd27463fb6719fb7a53e478c7dce
https://doi.org/10.1145/3569956
https://doi.org/10.1145/3569956
Publikováno v:
SIAM Journal on Computing, 2023, Vol.52(1), pp.38-79 [Peer Reviewed Journal]
The approximate graph colouring problem, whose complexity is unresolved in most cases, concerns finding a $c$-colouring of a graph that is promised to be $k$-colourable, where $c\geq k$. This problem naturally generalises to promise graph homomorphis
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::81826098fb7df1fc0bd25b4f8cbea8e3
https://doi.org/10.1137/20m1378223
https://doi.org/10.1137/20m1378223
Publikováno v:
SIAM Journal on Computing
In the field of constraint satisfaction problems (CSPs), promise CSPs are an exciting new direction of study. In a promise CSP, each constraint comes in two forms: “strict” and “weak,” and in the associated decision problem one must distingui
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d2ef7bd851261eeeae3c4a5f1352f882
https://doi.org/10.1137/20m1312745
https://doi.org/10.1137/20m1312745
Autor:
Sebastian Ordyniak, Michał Pilipczuk, Dušan Knop, Marcin Wrochna, Robert Ganian, Eduard Eiben
Publikováno v:
Integer Programming and Combinatorial Optimization-20th International Conference, IPCO 2019, Ann Arbor, MI, USA, May 22-24, 2019, Proceedings
Lecture Notes in Computer Science
Lecture Notes in Computer Science-Integer Programming and Combinatorial Optimization
Integer Programming and Combinatorial Optimization ISBN: 9783030179526
IPCO
Lecture Notes in Computer Science
Lecture Notes in Computer Science-Integer Programming and Combinatorial Optimization
Integer Programming and Combinatorial Optimization ISBN: 9783030179526
IPCO
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-
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1ff64a6ea1497a19690478cf9057051d
http://arxiv.org/abs/2012.00079
http://arxiv.org/abs/2012.00079
Autor:
Marcin Wrochna
Publikováno v:
Journal of Computer and System Sciences. 93:1-10
We show that several reconfiguration problems known to be PSPACE-complete remain so even when limited to graphs of bounded bandwidth (and hence pathwidth and treewidth). The essential step is noticing the similarity to very limited string rewriting s
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c289f1ed45d84c5fbb10bbc7679027c7
https://doi.org/10.1016/j.jcss.2017.11.003
https://doi.org/10.1016/j.jcss.2017.11.003
Autor:
Michał Pilipczuk, Marcin Wrochna
Publikováno v:
ACM Transactions on Computation Theory. 9:1-36
Dynamic programming on path and tree decompositions of graphs is a technique that is ubiquitous in the field of parameterized and exponential-time algorithms. However, one of its drawbacks is that the space usage is exponential in the decomposition's
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b2274887e56c4103e0607ef8c6e531c2
https://doi.org/10.1145/3154856
https://doi.org/10.1145/3154856
Publikováno v:
Algorithmica. 81:917-966
In the Edge Bipartization problem one is given an undirected graph G and an integer k, and the question is whether k edges can be deleted from G so that it becomes bipartite. Guo et al. (J Comput Syst Sci 72(8):1386–1396, 2006) proposed an algorith
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::8e43df8a957d0ab248b9802efa715cab
https://doi.org/10.1007/s00453-017-0319-z
https://doi.org/10.1007/s00453-017-0319-z
Autor:
Marcin Wrochna
Publikováno v:
Journal of Combinatorial Theory, Series B. 122:479-507
A graph K is square-free if it contains no four-cycle as a subgraph. A graph K is multiplicative if GxH -> K implies G -> K or H -> K, for all graphs G,H. Here GxH is the tensor (or categorical) graph product and G -> K denotes the existence of a gra
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e8ca4e41b9cbf5e90291fcfb8a80a959
https://doi.org/10.1016/j.jctb.2016.07.007
https://doi.org/10.1016/j.jctb.2016.07.007
Publikováno v:
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)
Scopus-Elsevier
Scopus-Elsevier
We identify a sufficient condition, treewidth-pliability, that gives a polynomial-time approximation scheme (PTAS) for a large class of Max-2-CSPs parametrised by the class of allowed constraint graphs (with arbitrary constraints on an unbounded alph
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::87f0497f77e07a02b3ae009dc3918cea
http://arxiv.org/abs/1911.03204
http://arxiv.org/abs/1911.03204
Publikováno v:
ACM Transactions on Computation Theory
While 3-SAT is NP-hard, 2-SAT is solvable in polynomial time. Austrin, Guruswami, and H\r{a}stad roved a result known as "$(2+\varepsilon)$-SAT is NP-hard" [FOCS'14/SICOMP'17]. They showed that the problem of distinguishing k-CNF formulas that are g-
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0d6c0c6ed944ac4bf461e9343957eca5