Arrow Research search

Author name cluster

Tomasz Krawczyk

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.

5 papers
2 author rows

Possible papers

5

MFCS Conference 2025 Conference Paper

A Note on the Complexity of Defensive Domination

  • Steven Chaplick
  • Grzegorz Gutowski
  • Tomasz Krawczyk

In a graph G, a k-attack A is any set of at most k vertices and 𝓁-defense D is a set of at most 𝓁 vertices. We say that defense D counters attack A if each a ∈ A can be matched to a distinct defender d ∈ D with a equal to d or a adjacent to d in G. In the defensive domination problem, we are interested in deciding, for a graph G and positive integers k and 𝓁 given on input, if there exists an 𝓁-defense that counters every possible k-attack on G. Defensive domination is a natural resource allocation problem and can be used to model network robustness and security, disaster response strategies, and redundancy designs. The defensive domination problem is naturally in the complexity class Σ^𝖯₂. The problem was known to be NP-hard in general, and polynomial-time algorithms were found for some restricted graph classes. In this note, we prove that the defensive domination problem is Σ^𝖯₂-complete. We also introduce a natural variant of the defensive domination problem in which the defense is allowed to be a multiset of vertices. This variant is also Σ^𝖯₂-complete, but we show that it admits a polynomial-time algorithm in the class of interval graphs. A similar result was known for the original setting in the class of proper interval graphs.

Details

MFCS Conference 2023 Conference Paper

Recognizing H-Graphs - Beyond Circular-Arc Graphs

  • Deniz Agaoglu Çagirici
  • Onur Çagirici
  • Jan Derbisz
  • Tim A. Hartmann
  • Petr Hlinený
  • Jan Kratochvíl
  • Tomasz Krawczyk
  • Peter Zeman 0001

In 1992 Biró, Hujter and Tuza introduced, for every fixed connected graph H, the class of H-graphs, defined as the intersection graphs of connected subgraphs of some subdivision of H. Such classes of graphs are related to many known graph classes: for example, K₂-graphs coincide with interval graphs, K₃-graphs with circular-arc graphs, the union of T-graphs, where T ranges over all trees, coincides with chordal graphs. Recently, quite a lot of research has been devoted to understanding the tractability border for various computational problems, such as recognition or isomorphism testing, in classes of H-graphs for different graphs H. In this work we undertake this research topic, focusing on the recognition problem. Chaplick, Töpfer, Voborník, and Zeman showed an XP-algorithm testing whether a given graph is a T-graph, where the parameter is the size of the tree T. In particular, for every fixed tree T the recognition of T-graphs can be solved in polynomial time. Tucker showed a polynomial time algorithm recognizing K₃-graphs (circular-arc graphs). On the other hand, Chaplick et al. showed also that for every fixed graph H containing two distinct cycles sharing an edge, the recognition of H-graphs is NP-hard. The main two results of this work narrow the gap between the NP-hard and 𝖯 cases of H-graph recognition. First, we show that the recognition of H-graphs is NP-hard when H contains two distinct cycles. On the other hand, we show a polynomial-time algorithm recognizing L-graphs, where L is a graph containing a cycle and an edge attached to it (which we call lollipop graphs). Our work leaves open the recognition problems of M-graphs for every unicyclic graph M different from a cycle and a lollipop.

Details

FOCS Conference 2010 Conference Paper

The Sub-exponential Upper Bound for On-Line Chain Partitioning

  • Bartlomiej Bosek
  • Tomasz Krawczyk

The main question in the on-line chain partitioning problem is to determine whether there exists an algorithm that partitions on-line posets of width at most w into polynomial number of chains see Trotter's chapter Partially ordered sets in the Handbook of Combinatorics. So far the best known on-line algorithm of Kierstead used at most (5 ω - 1)/4 chains; on the other hand Szemeredi proved that any on-line algorithm requires at least (ω+1/2) chains. These results were obtained in the early eighties and since then no progress in the general case has been done. We provide an on-line algorithm that partitions orders of width ω into at most ω 16 log ω chains. This yields the first subexponential upper bound for on-line chain partitioning problem.

Details

TCS Journal 2003 Journal Article

Semiretracts—a counterexample and some results

  • Wit Foryś
  • Tomasz Krawczyk
  • James A. Anderson

In the paper (Theoret. Comput. Sci. 237 (2000)) Anderson present a theorem which characterizes any semiretract S by means of two retracts R α and R ω. The first part of the paper contains a counterexample for this characterization. Then some results are presented which finally lead to the theorem which determines for a given semiretract S the minimal number of retracts R 1, …, R m such that the equality S=⋂i=1 mRi holds.

Details DOI
v2026.09.13