5
$\begingroup$

Let $k$ vertices in a graph be given. Some pairs of vertices are connected by an edge, each edge is labeled either $\{1,2\}$, $\{1,3\}$, or $\{2,3\}$. We can circle some of the numbers on the edges (circling both numbers on an edge is allowed). If an edge is $\{1,2\}$, some vertex adjacent to it must be adjacent to a circled $1$ and a circled $2$ (the same endpoint must satisfy both constraints). A similar requirement holds for $\{1,3\}$ and $\{2,3\}$ edges. Is it true that for any graph and labels, it is sufficient to circle at most $\lceil 3k/2\rceil$ numbers?

For instance, if $k = 3$ and the three edges have label $\{1,2\}$, $\{1,3\}$, $\{2,3\}$, then it suffices to circle the first $1$, the first $3$, and the second $2$. But for larger $k$ (such as $k = 6$), it becomes difficult to find a direct strategy.

The question was posted on MathOverflow but with no answer. I would be interested in an answer for $k=6$ already, as it seems difficult to do by brute force.

[Note: The answer below by Steven is based on a wrong understanding of the question.]

$\endgroup$

1 Answer 1

2
$\begingroup$

Since you say that both numbers of an edge can be circled at the same time, this means that different numbers don't have "interfering" choices. That is, look at the graph $G$ as being a multigraph: for each edge labeled $\{x,y\}$ in the original, replace it by 2 parallel edges (one labeled $x$ and one labeled $y$). Then the problem splits naturally in three independent subproblems: one for each subgraph of $G$ consisting of all edges labeled $x$ ($x \in \{1,2,3\})$.

The problem that we need to solve in each of these subgraphs is: choosing the the minimal subset of edges such that each edge is incident to a chosen edge. Let $C(G)$ be the size of such a minimum set.
It is easy to see that any maximal matching of $G$ suffices. (Since it is maximal, any remaining edge is adjacent to one of the edges in the matching.) It is also easy to see that a matching can be at most half as large as the number of vertices.

In total we have $C(G) \leq M(G) \leq \lfloor \frac{|V(G)|}{2}\rfloor $, where $M$ is the matching number. Doing the same 'procedure' for the three subgraphs yields a solution for the original problem with at most $3 \cdot \lfloor \frac{|V(G)|}{2}\rfloor$ circled numbers.

Since any maximal matching suffices for your upper bound, you can find them with any greedy algorithm. If you want the minimum amount of circled numbers, you need a minimum maximal matching for each of the three subgraphs. It appears that no polynomial-time algorithms is known for finding this.

$\endgroup$
8
  • $\begingroup$ "Then the problem splits naturally in three independent subproblems" - No, you cannot split the problem like that. This is because of the condition "some vertex adjacent to it must be adjacent to a circled $1$ and a circled $2$", where this must be a single vertex. $\endgroup$
    – user336268
    May 16, 2023 at 7:13
  • 1
    $\begingroup$ In that case, I would advice you to maybe give a more formal definition of the problem, with all constraints and options being clear. $\endgroup$
    – Steven
    May 16, 2023 at 7:24
  • $\begingroup$ The problem is already formal and clear. I was just pointing out why your solution does not work. $\endgroup$
    – user336268
    May 16, 2023 at 8:33
  • 1
    $\begingroup$ Well, apparently it wasn't clear enough for me. Also, I had to go to comments in your crosspost to see that circling both numbers of an edge is allowed. If I delete this answer then someone else might misinterpret it again. $\endgroup$
    – Steven
    May 16, 2023 at 15:38
  • 1
    $\begingroup$ @Karo I think there's another source of confusion: the same vertex must satisfy both constraints for an edge. (I edited to include this, but you should of course feel free to change the wording if you do not like mine.) $\endgroup$ May 17, 2023 at 19:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .