Source author record

Irina Mustata

Irina Mustata appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.CO Computational Complexity Computational Geometry Discrete Mathematics math.LO

Catalog footprint

What is connected

3works

5topics

3close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2021arXiv

What Makes the Recognition Problem Hard for Classes Related to Segment and String graphs?

We explore what could make recognition of particular intersection-defined classes hard. We focus mainly on unit grid intersection graphs (UGIGs), i.e., intersection graphs of unit-length axis-aligned segments and grid intersection graphs (GIGs, which are defined like UGIGs without unit-length restriction) and string graphs, intersection graphs of arc-connected curves in a plane. We show that the explored graph classes are NP-hard to recognized even when restricted on graphs with arbitrarily large girth, i.e., length of a shortest cycle. As well, we show that the recognition of these classes remains hard even for graphs with restricted degree (4, 5 and 8 depending on a particular class). For UGIGs we present structural results on the size of a possible representation, too.

preprint2016arXiv

The Complexity of the Partial Order Dimension Problem - Closing the Gap

The dimension of a partial order $P$ is the minimum number of linear orders whose intersection is $P$. There are efficient algorithms to test if a partial order has dimension at most $2$. In 1982 Yannakakis showed that for $k\geq 3$ to test if a partial order has dimension $\leq k$ is NP-complete. The height of a partial order $P$ is the maximum size of a chain in $P$. Yannakakis also showed that for $k\geq 4$ to test if a partial order of height $2$ has dimension $\leq k$ is NP-complete. The complexity of deciding whether an order of height $2$ has dimension $3$ was left open. This question became one of the best known open problems in dimension theory for partial orders. We show that the problem is NP-complete. Technically we show that the decision problem (3DH2) for dimension is equivalent to deciding for the existence of bipartite triangle containment representations (BTCon). This problem then allows a reduction from a class of planar satisfiability problems (P-3-CON-3-SAT(4)) which is known to be NP-hard.

preprint2013arXiv

On a game on graphs

We start with the well-known game below: Two players hold a sheet of paper to their forehead on which a positive integer is written. The numbers are consecutive and each player can only see the number of the other one. In each time step, they either say nothing or tell what number they have. Both of them will eventually figure out their number after a certain amount of time. The game is rather cooperative than competitive, and employs the notions of common knowledge and mutual knowledge. We generalize this game to arbitrary (directed and non-directed) simple graphs and try to establish for which graphs one or both of them will figure out the solution, and how long they do need to find it. We give a complete answer for the case of two players, even if they are both allowed to discuss before the start of the game.