Arrow Research search

Author name cluster

Pawel Rzazewski

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers
1 author row

Possible papers

10

ECAI Conference 2025 Conference Paper

On Approximate MMS Allocations on Restricted Graph Classes

  • Václav Blazej
  • Michal Debski
  • Zbigniew Lonc
  • Marta Piecyk
  • Pawel Rzazewski

We study the problem of fair division of a set of indivisible goods with connectivity constraints. Specifically, we assume that the goods are represented as vertices of a connected graph, and sets of goods allocated to the agents are connected subgraphs of this graph. We focus on the widely-studied maximin share criterion of fairness. It has been shown that an allocation satisfying this criterion may not exist even without connectivity constraints, i. e. , if the graph of goods is complete. In view of this, it is natural to seek approximate allocations that guarantee each agent a connected bundle of goods with value at least a constant fraction of the maximin share value to the agent. It is known that for some classes of graphs, such as complete graphs, cycles, and d-claw-free graphs for any fixed d, such approximate allocations indeed exist. However, it is an open problem whether they exist for the class of all graphs. In this paper, we continue the systematic study of the existence of approximate allocations on restricted graph classes. In particular, we show that such allocations exist for several well-studied classes, including block graphs, cacti, complete multipartite graphs, and split graphs.

Details

STOC Conference 2024 Conference Paper

Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time

  • Peter Gartland
  • Daniel Lokshtanov
  • Tomás Masarík
  • Marcin Pilipczuk
  • Michal Pilipczuk
  • Pawel Rzazewski

We show that the Maximum Weight Independent Set problem (MWIS) can be solved in quasi-polynomial time on H -free graphs (graphs excluding a fixed graph H as an induced subgraph) for every H whose every connected component is a path or a subdivided claw (i.e., a tree with at most three leaves). This completes the dichotomy of the complexity of MWIS in F -free graphs for any finite set F of graphs into NP-hard cases and cases solvable in quasi-polynomial time, and corroborates the conjecture that the cases not known to be NP-hard are actually polynomial-time solvable. The key graph-theoretic ingredient in our result is as follows. Fix an integer t ≥ 1. Let S t , t , t be the graph created from three paths on t edges by identifying one endpoint of each path into a single vertex. We show that, given a graph G , one can in polynomial time find either an induced S t , t , t in G , or a balanced separator consisting of O (log| V ( G )|) vertex neighborhoods in G , or an extended strip decomposition of G (a decomposition almost as useful for recursion for MWIS as a partition into connected components) with each particle of weight multiplicatively smaller than the weight of G . This is a strengthening of a result of Majewski, Masařík, Novotná, Okrasa, Pilipczuk, Rzążewski, and Sokołowski [Transactions on Computation Theory ‍2024] which provided such an extended strip decomposition only after the deletion of O (log| V ( G )|) vertex neighborhoods. To reach the final result, we employ an involved branching strategy that relies on the structural lemma presented above.

Details

MFCS Conference 2024 Conference Paper

Minimal Obstructions to C₅-Coloring in Hereditary Graph Classes

  • Jan Goedgebeur
  • Jorik Jooken
  • Karolina Okrasa
  • Pawel Rzazewski
  • Oliver Schaudt

For graphs G and H, an H-coloring of G is an edge-preserving mapping from V(G) to V(H). Note that if H is the triangle, then H-colorings are equivalent to 3-colorings. In this paper we are interested in the case that H is the five-vertex cycle C₅. A minimal obstruction to C₅-coloring is a graph that does not have a C₅-coloring, but every proper induced subgraph thereof has a C₅-coloring. In this paper we are interested in minimal obstructions to C₅-coloring in F-free graphs, i. e. , graphs that exclude some fixed graph F as an induced subgraph. Let P_t denote the path on t vertices, and let S_{a, b, c} denote the graph obtained from paths P_{a+1}, P_{b+1}, P_{c+1} by identifying one of their endvertices. We show that there is only a finite number of minimal obstructions to C₅-coloring among F-free graphs, where F ∈ {P₈, S_{2, 2, 1}, S_{3, 1, 1}} and explicitly determine all such obstructions. This extends the results of Kamiński and Pstrucha [Discr. Appl. Math. 261, 2019] who proved that there is only a finite number of P₇-free minimal obstructions to C₅-coloring, and of Dębski et al. [ISAAC 2022 Proc. ] who showed that the triangle is the unique S_{2, 1, 1}-free minimal obstruction to C₅-coloring. We complement our results with a construction of an infinite family of minimal obstructions to C₅-coloring, which are simultaneously P_{13}-free and S_{2, 2, 2}-free. We also discuss infinite families of F-free minimal obstructions to H-coloring for other graphs H.

Details

MFCS Conference 2021 Conference Paper

Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs

  • Giacomo Paesani
  • Daniël Paulusma
  • Pawel Rzazewski

We prove new complexity results for Feedback Vertex Set and Even Cycle Transversal on H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. In particular, we prove that both problems are polynomial-time solvable for sP₃-free graphs for every integer s ≥ 1; here, the graph sP₃ denotes the disjoint union of s paths on three vertices. Our results show that both problems exhibit the same behaviour on H-free graphs (subject to some open cases). This is in part explained by a new general algorithm we design for finding in a graph G a largest induced subgraph whose blocks belong to some finite class C of graphs. We also compare our results with the state-of-the-art results for the Odd Cycle Transversal problem, which is known to behave differently on H-free graphs.

Details

SODA Conference 2021 Conference Paper

Induced subgraphs of bounded treewidth and the container method

  • Tara Abrishami
  • Maria Chudnovsky
  • Marcin Pilipczuk
  • Pawel Rzazewski
  • Paul D. Seymour

A hole in a graph is an induced cycle of length at least 4. A hole is long if its length is at least 5. By P t we denote a path on t vertices. In this paper we give polynomial-time algorithms for the following problems: the M aximum W eight I ndependent S et problem in long-hole-free graphs, and the F eedback V ertex S et problem in P 5 -free graphs. Each of the above results resolves a corresponding long-standing open problem. An extended C 5 is a five-vertex hole with an additional vertex adjacent to one or two consecutive vertices of the hole. Let be the class of graphs excluding an extended C 5 and holes of length at least 6 as induced subgraphs; contains all long-hole-free graphs and all P 5 -free graphs. We show that, given an n -vertex graph G ∊ with vertex weights and an integer k, one can in time find a maximum-weight induced subgraph of G of treewidth less than k. This implies both aforementioned results. To achieve this goal, we extend the framework of potential maximal cliques (PMCs) to containers. Developed by Bouchitté and Todinca [SIAM J. Comput. 2001] and extended by Fomin, Todinca, and Villanger [SIAM J. Comput. 2015], this framework allows to solve high variety of tasks, including finding a maximum-weight induced subgraph of treewidth less than k for fixed k, in time polynomial in the size of the graph and the number of potential maximal cliques. Further developments, tailored to solve the M aximum W eight I ndependent S et problem within this framework (e. g. , for P 5 -free [SODA 2014] or P 6 -free graphs [SODA 2019]), enumerate only a specifically chosen subset of all PMCs of a graph. In all aforementioned works, the final step is an involved dynamic programming algorithm whose state space is based on the considered list of PMCs. Here we modify the dynamic programming algorithm and show that it is sufficient to consider only a container for each potential maximal clique: a superset of the maximal clique that intersects the sought solution only in the vertices of the potential maximal clique. This strengthening of the framework not only allows us to obtain our main result, but also leads to significant simplifications of reasonings in previous papers.

Details