123gjweq2's blog

A question about a problem
By 123gjweq2, 3 months ago, In English

For this problem: https://codeforces.net/contest/1981/problem/D, in the case where $$$m$$$ is even, why is it true that the longest path with unique edges (but not necessarily unique vertices) happens when you remove $$$\frac{m}{2} - 1$$$ edges? I get that there is then a Eulerian path in the graph because it has two nodes with an odd degree, but how can we be sure that there isn't a path with more unique edges in the original graph without any removals?

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I thought it was really intuitive but now that iam trying to prove it I actually can't seem to do it To simplify the problem given a complete graph remove the min number of edges so there exists an eulerian path

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Also: why is it always optimal for the maximum path to be a Eulerian path of a complete graph with some number of edges removed? Why can't we add in a few extra edges and find that one of the pathways in that graph, while not being a Eulerian path, has more edges?

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      That's what we are trying to do we are trying to find the max number of edges we can traverse so we just start from the abs max and see the min number of edges to remove before its a good path yea they still exist theoretically but to compute the eulerian path we need to actually know what edges we need

      → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        I am still a bit confused. Let's say we have a complete graph with $$$m$$$ nodes where $$$m$$$ is even. Then we remove edges from $$$(2, 3)$$$, $$$(4, 5) \cdots (m - 2, m - 1)$$$. That is going to be $$$\frac{m}{2} - 1$$$ edges gone. Just for the sake of brevity, the complete graph is $$$G_l$$$ and the altered graph is $$$G_s$$$. Now $$$G_s$$$ certainly has an Eulerian path, but how can we be sure that $$$G_l$$$ doesn't have a path with more unique edges (where all edges are unique) than $$$G_s$$$'s Eulerian path, even if the path in $$$G_l$$$ isn't Eulerian (which it isn't)?

        Is it the case that you can find the maximum path with unique edges in a graph just by removing the least number of edges so that the graph contains an Eulerian path?

        → Reply
        • »
          »
          »
          »
          »
          3 months ago, # ^ |
          ← Rev. 3   Vote: I like it +3 Vote: I do not like it

          An eulerian path isn't the path with the maximum number of unique edges it is the path that doesn't cross the same edge twice so Let's define a path that doesn't cross the same edge twice as an eulerian path then we are interested in the maximum length eulerian path the thing left to prove here is why is the maximum eulerian path length is the one after removing m/2 — 1 edges I feel like iam starting to build a formal proof that I will write when iam certain of it

          edit : maybe iam not fully getting your pov so if u have any questions feel free to ask them

          → Reply
          • »
            »
            »
            »
            »
            »
            3 months ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            If I am not mistaken, an Eulerian path is a path that travels through each edge exactly once in some graph. An Eulerian path only exists in a graph where all nodes have an even number of edges or two nodes have an odd number of edges.

            From my understanding of the editorial, each edge must be unique, and we must minimize the number of nodes we use to have $$$n - 1$$$ unique edges that form a path. We make a complete graph with $$$m$$$ nodes, and try to find the maximum path in that graph that does not contain repeated edges. The case for odd $$$m$$$ is straightforward, because each edge has an even number of degrees, therefore an Eulerian path in that graph contains every edge exactly once.

            The case for even $$$m$$$ confuses me. I am confused as to why removing $$$\frac{m}{2} - 1$$$ edges and then finding an Eulerian path from this altered graph is optimal. I am under the impression that the optimal answer doesn't necessarily have to be an Eulerian path, right? All it has to be is the longest path that contains unique edges.

            I guess my question is: why is the longest path with unique edges for even $$$m$$$ coincidental with the Eulerian path in the graph after removing edges $$$(2, 3)$$$, $$$(4, 5) \cdots (m - 2, m - 1)$$$? Why is there not a better non-Eulerian-path answer in the graph without any edges removed?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 months ago, # ^ |
              ← Rev. 2   Vote: I like it 0 Vote: I do not like it

              oh iam pretty sure we are misunderstanding each other so lets agree on this thing , if we just have some value N we have a complete graph of N vertices now our main objective is to turn this complete graph into an eulerian path this is all we are trying to do , to rephrase it alittle bit we are trying to choose the maximum subset size of edges from that complete graph there are some subsets that simply dont form an eulerian path therefore invalid so we are only interested in the maximum size one now u are saying why not leave the graph as it is and find a longer path that contains more nodes ? so again isnt this path just a subset of this graph ? why not remove all edges outside this subset as its not gonne change the answer and again the author claims that the largest subset of that graph that forms an eulerian path is the graph — (m / 2 — 1) edges

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                3 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Ohhhh shit that clears it up. Thanks.

                → Reply